浅谈融合关键字搜索的XML非结构化查洵

减小字体 增大字体 作者:李寅珠  来源:www.zhonghualunwen.com  发布时间:2012-09-13 15:29:39

一、XML结构在关系数据库中的存储

从XML文档到关系模式的映射方法有多种,本文采用的方法是先将XML文档解析为图结构,再用相应的关系模式存储该图结构。

XML文档被映射为一个有序的带标记的有向图。对于每个XML数据集D,都对应一个有向图GD,在GD中,D中的元素e用结点Ne表示;D中的数据值v用叶子Vv表示。若e2为e1的引用,Ne1至Ne2间为内容边,以e2的类型标注。若v为e的叶子,Ne至Vv间为内容边,用空字符串标注。若v是e1的一个属性值,Ne至Vv之间为属性边,以属性名标注。

在RDBM中,采用固定的关系模式存储XML结构的有向图,有6种存储方案:三种存储边方案和两种存储叶子值方案的组合。

边映射方法有:边表Edge(source,ordinal,name,flag,target,value),存储图中所有的边。其中source为边起点,ordinal为边序号,name为边名,flag标记边是否指向叶结点,target为边目标。二元表Bname(source,ordinal,flag,target),存储所有边名相同的边。用严格的二元模式来表示具有相同语义的父子结点关系,充分利用语义的直观性,确保查询效率。统一表用一张大表存储所有的边,相当于外连接所有的二元表。

值映射方法有:值表Vtype(id,value),为每个数据类型建立一个表。其中type为数据类型,id为叶结点。内联法把值和边存储在一张表中,相当于外连接边表和所有的值表。

文献从映射生成的数据库规模、重构XML文档所需时间、执行不同XML查询所需时间等方面对比分析,发现二元法结合内联法是最优映射方法,本实验也采用此方法。

二、支持关键字查询的RDBMS

支持关键字搜索意味着能够处理全文检索,也可借助关系数据库实现。倒排索引基本结构为:〈word,position〉,position为关键字的位置序列,因为需以元素为粒度查询,所以需记录关键字出现的元素,关键字出现在元素中的位置,以区分关键字是标签名、值、属性名或者属性的值内容。为了某些查询要求,还需限制搜索深度。由此得到倒排索引的扩展结构〈word,elID,location,depth〉。

在RDB中可以用表Contains(word,elID,location,depth)存储倒排索引,这种设计简单易行,但Contains表会非常大,每次查询都必须扫描整个表,效率很低。由于同一关键字在XML文档中可能出现多次,因而可以根据关键字将Contains表拆成小表word(elID,location,depth),缩小查询范围。可再按照元素类型二次拆分,形成word-type表。我们经常的查询请求类似于“查找成立于1999年的学院”,若在1999-year表中查找,速度很快。

三、融合关键字查询的SQL扩展

XML-QL由W3C组织提出,是查询XML文档的标准语言,其语法格式为:

WHERE(XML-pattern[ELEMENT_AS $elem_var])IN fileName,(predicate)

CONSTRUCT XML-pattern | variable;

XML-QL提供正则路径表达式来表达查询请求,为支持关键字非结构化查询,需引入CONTAINS子句(word,$E,location,depth),与倒排索引结构相对应。例如:查找成立于1999年,涉及“Computer”的所有学院的领导组成员”,查询语句如下:

WHERE 〈college〉〈year〉1999〈/year〉〈leader〉〈/leader〉ELEMENT AS $L 〈/college〉 ELEMENT AS $E IN“sample.xml”,CONTAINS(“Computer”,$E,any,3)CONSTRUCT $L

RDBM中XML数据存储在Bname表,索引存储在word-type表,若是XML结构化查询,SQL只查询Bname表;若是包含关键字的非结构化查询,SQL需把Bname表和word-type表连接查询即可,逻辑上说,被扩展的XML-QL被翻译成SQL查询。

四、实验分析

文献以包含CONTAINS子句的数量程度,将查询划分为结构化、部分结构化和非结构化。实验结果表明,部分结构化查询速度最快,而结构化查询返回的查询结果最少,最为准确。由此可见,准确的查询需要用户充分了解XML文档结构,但CONTAINS子句能协助用户更快查询。

由于没有利用模式定义(如DTD)来优化存储XML结构,所以关系表数量众多且含有大量空值;在查询时需进行大量连接操作,大大降低了效率。对于查询频率较高的关联表,可以预先连接,提高效率。也可以建立适当的索引,还可以使用近似倒排索引,位图索引技术,以及数据库压缩技术来提升查询性能。

【参考文献】

[1]D.Florescu,Ioana Manolescu等.Integrating Keyword Search into XML Query Processing.Proc.of the 9th Int.World Wide Web Conference.2000.

[2]D.Florescu,Donald Kossmann.Storing and querying XML data using an RDBMS.IEEE Data Engineering Bulletin,22(3):27-34,1999.

[3]V.Hristidis,Y.Papakonstantinou.DISCOVER:Keyword Search in Relational Databases.VLDB,2002.

Tags:全文检索

作者:李寅珠
  • 好的评价 如果您觉得此文章好,就请您
      0%(0)
  • 差的评价 如果您觉得此文章差,就请您
      0%(0)

文章评论评论内容只代表网友观点,与本站立场无关!

   评论摘要(共 0 条,得分 0 分,平均 0 分) 查看完整评论