摘要:针对目前XML关键字查询结果中包含了许多无意义的节点的问题，提出了一种语义相关的查询算法。由于XML文档具有半结构化和自描述的特点，通过充分利用节点间的语义相关性，提出了最小最低实体子树（SLEST）的概念，在这个概念中，关键字之间仅存在物理连接关系；为了捕获关键字之间的IDREF引用关系，提出基于最小相关实体子树（SIEST）的算法，并利用最小最低实体子树和最小相关实体子树代替最小最低公共祖先（SLCA）作为查询结果。实验结果表明，提出的算法能有效提高XML关键字查询结果的查准率。
关键词:最小最低实体子树；最小相关实体子树；XML关键字查询；XML数据库；语义相关性
中图分类号: TP311.131 文献标志码:A
�
XML keyword search algorithm based on smallest lowest entity sub.tree interrelated
�
YAO Quan.zhu, YU Xun.bin��*
School of Computer Science and Engineering, Xi’an University of Technology, Xi’an Shaanxi 710048, China
Abstract:
A query algorithm of semantic relevant is proposed in this paper, with regard to many meaningless nodes contained in the present results of XML keywords retrieval. Based on the characteristics of semi-structure and self-description of XML files, the concept of Smallest Lowest Entity Sub-Tree (SLEST), in which only physical connection exists between keywords, is put forward by making full use of semantic correlation between nodes. Based on Smallest Interrelated Entity Sub-Tree (SIEST), an algorithm, in which the result is represented by SLEST and SIEST instead of Smallest Lowest Common Ancestor (SLCA), is proposed to capture the IDREF relation between keywords. The result shows that the algorithm proposed in this paper can increase the precision ratio of XML keywords retrieval.
A query algorithm of semantic relativity was proposed in this paper, with regard to many meaningless nodes contained in the present results of XML keywords retrieval. Based on the characteristics of semi.structure and self.description of XML files, the concept of Smallest Lowest Entity Sub.Tree (SLEST), in which only physical connection exists between keywords, was put forward by making full use of semantic correlation between nodes. Based on Smallest Interrelated Entity Sub.Tree (SIEST), an algorithm, in which the result was represented by SLEST and SIEST instead of Smallest Lowest Common Ancestor (SLCA), was proposed to capture the IDREF relation between keywords. The result shows that the algorithm proposed in this paper can increase the precision of XML keyword retrieval.
�Key words:
Smallest Lowest Entity Sub.Tree (SLEST); Smallest Interrelated Entity Sub.Tree (SIEST); XML keyword query; XML database; semantic relativity
�
0 引言�
随着Internet的普及，对XML数据的查询迅速增多。因此，如何能够简单并有效地查询XML文档成为一个研究的热点。目前，在XML数据检索方面的研究集中到XML结构化查询和XML关键字查询两个方面。�
用户使用结构化查询的门槛较高，除了要了解XML文档结构，还要掌握相应的查询语言，例如，XPath或XQuery。用户需要利用这些精确的查询语言来描述自己需要的查询模式，查询系统则会根据用户描述的查询模式返回相应的查询结果。如图1，如果用户想要找到名为“Java”的书的信息，相应的查询路径表达式为“//books/book［title=“Java”］”。由于大部分互联网用户并不懂得相应的查询语言和XML文档结构，所以XML关键字查询更适合于普通用户。�
XML关键字查询由于其简单易用而受到普通用户欢迎，用户只需要提供有关的查询关键字就可以实现查询。目前，XML关键字查询大多数是以最低公共祖先(Lowest Common Ancestor，LCA)概念的改进作为查询结果，比如ELCA(Exclusive LCA)、SLCA(Smallest LCA)和MLCA(Meaningful LCA)，这类方法执行效率较高，但由于没有捕获XML文档中不同节点之间的类似于IDREF引用关系，导致查询的准确率较低。�
XML树中的实体节点和属性节点类似于关系数据库中E.R模型中的实体和属性，为了使查询关键字所对应的XML片段所携带的信息量更多，本文借鉴文献［1］中提出的实体子树的思想，并提出最小最低实体子树(Smallest Lowest Entity Sub.Tree,SLEST)的概念，最小最低实体子树很显然比单个节点所携带的信息量多，这不仅能充分表达XML文档中每个节点的语义信息，通过对同一XML树中的不同祖先节点的子节点之间的联系进行分析，更能有效地捕获不同查询关键词之间的语义信息。�
1 相关研究�
XRANK�［2］是最早考虑到XML文档的分层和超链接结构及关键词二维接近概念的XML检索系统。XRANK是以ELCA作为返回结果，ELCA节点是满足以下条件的节点集：删除了以该节点为根的子树中包含了全部关键字的更小子树后，原子树仍包含全部关键字。XRANK提出一种基于栈的算法，通过ElemRank来衡量XML元素的重要性，但XRANK不区分标签和关键字，没有考虑到关键字之间可能存在的语义信息，使得该系统会返回大量无意义的结果。�
文献［2-3］中介绍了以SLCA作为返回结果的三种主流算法Indexed Lookup Eagar(ILE)、Scan Eagar(SE)和Stack算法。Stack算法利用对各关键字节点Dewey编码的对比来确定其最小公共祖先，这需要扫描所有的节点，包括对结果不起任何作用的无效节点，在整个计算过程中，需要大量的节点编码的比较操作和编码的入栈与出栈操作，以至于会浪费大量的系统资源。ILE算法利用特殊的B+树索引来提高检索效率，在该算法中需要将全部的XML数据保存在修改过的B+树中，实现较为复杂。文献［4］中提出最小子树根节点问题的分层算法，该算法在获取了包含关键字的节点的编码集合后，通过计算对应于不同层次的编码集合的交集，可以得到对应于不同层的SLCA节点，该算法的效率比前面的算法要高，但其仍然会返回一些不满足用户查询需要的结果。�
限制LCA这类相关概念的主要因素是它不能捕获XML文档中的语义关系，比如文档内的IDREF引用关系。例如，在图1中，对于给定的一组查询关键字Q1={proceeding，book，Java}，用户是想查找书名为Java的书的出版信息。在这组查询中，以LCA为基础的一系列概念都是返回根节点dblp(0)；这是因为在这些查找过程中没有考虑文档节点间的语义关系而扩大了相关节点范围。在查找过程中，proceeding(0.0.0，0.0.1)、book(0.1.0)和Java(0.1.0.0.0)会参与计算过程。而实际上proceeding(0.0.0)节点是不需要参与计算的，因为仅仅只有proceeding(0.0.1)和book(0.1.0)之间存在引用关系。�
本文针对目前XML关键字查询中缺少对用户语义的捕获，导致返回结果准确率偏低的问题；通过存储XML文档节点间的IDREF引用关系的方法，从而达到能准确捕获用户的查询意图的目的，并在SLCA的基础上提出最小最低实体子树的概念，用最小最低实体子树(SLEST)和最小相关实体子树(Smallest Interrelated Entity Sub.Tree,SIEST)代替SLCA作为查询结果，从而保证查询结果更符合用户的查询意图，能够提高查询的准确率。