XML查询处理技术简介 周军锋

数据组织 … XML：eXtensible Markup Language 作用：用于网络数据的表述和交换 无结构数据 XML文档 结构化数据 XML文档 …

数据组织 BOOK <Root> <BOOK> <Name> XML </Name> DB XML 2000 1999 32 20 Mike Joe Author Price Year Name <Root> <BOOK> <Name> XML </Name> <Year> 1999 </Year> <Price> 20 </Price> <Author> Joe <Author> </BOOK> <Name> DB </Name> <Year> 2000 </Year> <Price> 32 </Price> <Author> Mike <Author> </Root> BOOK Name Year Author Price XML 1999 Joe 20 Root DB 2000 Mike 32 …

XPath: //BOOK[/Name=“XML”] 结构化查询 Root BOOK BOOK … Name Year Price Author Name Year Price Author XML 1999 20 Joe DB 2000 32 Mike BOOK Name XML // / XPath: //BOOK[/Name=“XML”] 问题： 已知文档结构 掌握相关的查询语言 大量高效算法

Partial 查询 Motivation schema or structure knowledge is not fully available Heterogeneous data Schema evolution

Partial 查询 name author book title // name author book title publisher XML John Q1 // name author book title publisher price Addison Academic XML 46.95 DB 9.99 John location Beijing Washington name author John location Beijing book title publisher price Addison Academic XML 46.95 DB 9.99 Washington Root book title XML name author John Q2 //

Partial 查询 ≡ ≡ name author book title // name author book title // XML John Q1 Q2 // name author book title XML John Q3 // ≡ book title XML name author John // ≡ Q4

Partial 查询 与结构化查询相比 使用灵活 求解麻烦 用户无需了解所有具体的结构信息

存在的问题 没有根的查询 P-C边的处理 语义还不够丰富

基于关键字的查询处理 Q：XML,1999 好处： 用户无需了解结构信息 用户无需学习相关的查询语言 问题： Root BOOK BOOK … Name Year Price Author Name Year Price Author XML 1999 20 Joe DB 2000 32 Mike Q：XML,1999 好处： 用户无需了解结构信息 用户无需学习相关的查询语言 问题： 如何在用户仅仅提交关键字的情况下，返回尽可能多的高度相关的结果？

已有方法 Tree上的关键字查询 Graph上的关键字查询 LCA: Lowest Common Ancestor SLCA or MLCA: Smallest LCA or Meaningful LCA Graph上的关键字查询 包含关键字的最小连通图

LCA & S(M)LCA BOOK Q1: Year, price LCA会产生很多无用结果 BOOK Name Year Author XML 1999 Joe 20 Root DB 2000 Mike 32 … BOOK Name Year Price Author XML 1999 20 Joe DB 2000 32 Mike Q1: Year, price LCA会产生很多无用结果

LCA & S(M)LCA Q1: name, location Q1: name, location Q1: name, location Root author author books books Q1: name, location book book name name book location location publisher John title price title coauthors Linda London title price Beijing name location XML 46.95 DB authorRef DBMS 41.2 Addison Beijing Q1: name, location Q1: name, location SLCA会丢失有用结果

Motivation XML相关的信息检索技术变得越来越重要 数据 相关技术 XML仅仅是一种数据表示方式 对于有结构信息的数据，已有方法很少结合数据的结构信息来辅助关键字查询

需要重点考虑的问题 如何判断有意义的解 需要将数据的结构信息纳入考虑的范围 高效的求解方法 结果的构造：sigmod07 如何对结果进行评价

关系数据XML数据 过渡元素 实体 属性 值 AUTHOR AUTHOR-BOOK ID 1 2 Name Location John Beijing Linda London AID BID 1 2 3 过渡元素 BOOK Root ID 1 2 3 Title Price XML 46.95 DB NULL DBMS 41.2 PubID 1 NULL 实体 author author books books book publisher 属性 name book name book location location ID 1 Name location Addison Beijing publisher John title price title coauthors 值 Linda London title price Beijing name location XML 46.95 DB authorRef DBMS 41.2 Addison Beijing

什么是有意义的结果 LCA为过渡元素，其上有实体节点 Q3: title, price Q1: name, location Root Q3: title, price author author books books Q1: name, location book book name LCA为实体，关键字属于同一实体 name book location location publisher John title price title coauthors Linda London title price Beijing name location XML 46.95 DB authorRef DBMS 41.2 Addison Beijing Q1: name, location Q2: DB, Linda LCA为实体，关键字属于不同实体 LCA为实体，关键字属于不同实体

什么是有意义的结果 BOOK Q1: Year, price 没有意义的结果，根节点是过渡节点，且其上没有实体 Q1: Year, XML Name Year Author Price XML 1999 Joe 20 Root DB 2000 Mike 32 … Name Year Price Author XML 1999 20 Joe DB 2000 32 Mike BOOK Name Year Author Price XML 1999 Joe 20 Root DB 2000 Mike 32 BOOKS … Q1: Year, price 有意义的结果，尽管BOOKS是过渡节点且其上没有实体节点，由于Year是BOOK的属性，因此真正的LCA是BOOK，而BOOK是实体 Q1: Year, XML

其他问题 元素类型的确定 没有一套成熟的规则可以确认元素类型，需要继续考虑 数据库管理员进行确认 根据DTD进行判断 扫描一次文档的方式进行确认 没有一套成熟的规则可以确认元素类型，需要继续考虑

其他问题 关于Rank方法 结果的Rank 相关文献看的太少，还需要继续了解别人的工作 由于XML文档可以表示不同类型的数据，因此Rank方法也不能单一化 数据为中心：可以借鉴DB上的关键字查询的Rank方法并结合XML文档特性来制定，考虑数据的对称性 文档为中心：需要借助于其他的方法来Rank结果 结果的Rank 结果的Size，如何定义Size？ 关键字的频率，类似于IR的方式 其他问题，是否需要考虑 过渡元素 属性元素 若只考虑实体元素，结果如何？ 考虑实体之间的距离 考虑单词频率对Rank的影响 Rank的时候以实体为基础，这样不同的关键字可能对应相同的返回结果，这样的结果应该评价高一些 和已有XML关键字查询结果的Rank方法不同，已有方法考虑了所有包含关键字的叶子的影响，这里不用考虑，因为有些叶子节点可能不属于当前实体的属性 相关文献看的太少，还需要继续了解别人的工作

其他问题 查询求解 考虑IDREF边，问题变成了图上的关键字查询问题，如何提供高效算法进行求解？ 如何针对本文提出的语义构建高效索引以加速求解？ 需要继续考虑