论文部分内容阅读
XML(可扩展标签语言)已成为当前基于网络应用的数据表达、交换的标准，设计并实现针对XML数据的有效管理机制也就成为几个相关研究领域所关注的热点，例如数据库领域，Web服务，电子商务和信息检索领域等。针对XML数据查询的研究可概括为两个方向，一是延续传统数据库SQL风格的XML Query查询方式，另一种则是将传统信息检索(IR：InformationRetrieval)领域的有关技术(关键字查询，将结果进行排序等等)吸收到XML数据查询中的XML IR方式。根据查询描述的方式的不同，XML IR查询主要分为三种类型，一是扩展XML Query查询语言吸收IR特点，记作XML IR/query方式；二是直接将关键字方式拓展到XML数据上，记作XML IR/keyword方式。其中后者是本文研究的主要背景。还有一种是直接使用XML片段作为查询模式的方式，记作XML IR/fragment。实际中对它的研究非常少。
由于XML数据具有半结构化、自描述的特点，使得传统信息检索技术在XML数据上的处理有着新的特点，包括关键字查询返回的结果表现为最紧致的XML片段，结果排序(Ranking)的衡量机制必须考虑片段的结构信息等等；除此以外，如何巧妙地赋予关键字查询以结构信息，也是一个值得思考的方面，这是因为现有的XML关键字查询方式不能够表示关键字间的结构信息，而结构信息对于XML数据有着重要的意义；如何设计XML，索引结构以同时支持XMLQuery和XML关键字查询，也是一个需要妥善考虑的问题。本文针对上述问题做了深入的研究，研究工作可概括为如下三部分：
·满足给定关键字查询的XML紧致片段求解算法LJSA实际的研究通常将这个问题转化为SLCA(Smallest Lowest Common Ancestor)问题，即确定满足给定关键字的XML片段根节点。在观察到SLCA节点在XML树结构节点层上具有一定的分布规律后，本文针对SLCA问题给出了一种逐层计算SLCA节点的LISA(Layered IntersectionScan Algorithm)算法：给定对应关键字的节点集合S={S<,1>，S<,2>，…，S<,k>}(其中的k表示关键字的数目)，可通过逐层计算各层公共节点的方式得到SLCA节点。与现有的求解SLCA问题的算法相比，LISA算法完全基于获取的关键字Dewey集合，并不需要额外的复杂数据结构的支持。
·XML片段结构相似性度量的新方法KCAM由于XML数据具有半结构的特点，如何设计能够捕捉结构相似程度的方法就成为XML关键字查询需要妥善解决的问题。遗憾的是，已有的方法往往具有如下的不足：(i)要么不能够很好地分辨XML片段间的结构差异；(ii)要么虽然可以分辨结构差异但计算过程往往较为复杂。本文在观察到SLCA节点与其所辖叶节点问具有相对位置不变的特性后，提出了基于KCAM(Keyword Common Ancestor Matrix)距离的XML片段结构相似性度量方法。与其他方法相比，本文提出的KCAM能够有效地识别XML片段间更为细微的结构差别：此外，通过与其他方法的比较还揭示出该方法具有与节点相对位置及标签无关的特性。
同时，为贯彻基于KCAM方法对XML关键字查询的支持，进一步给出了嵌套关键字的查询描述方式。该方式只需要用户按照自己的意图将关键字纳入由括号分割的区域，并不需要用户输入标签信息，也就不会要求用户必须了解XML数据的组织方式。由于没有标签的限制，这种嵌套关键字查询方式也就具有了跨语言的能力一不管XML数据使用德语标签标记，还是使用英语、中文标签标记，只要XML数据的叶节点中包含所限定的关键字，就都可以成为查询的目标片段。这一点对于当下的异源XML数据处理而言有着实际的意义。
·XML复合索引结构Dew-path：同时支持XML Query查询与关键字查询当前XML数据上的查询类型主要可概括为两种：以Xpath/Xquery为代表的XML Query查询方式，和以关键字查询为代表的XML IR/keyword查询方式。由于两种类型所关注问题的不同，它们各自所采用的XML索引结构也多无相通之处，造成了如下的现象：针对关键字查询的系统不能够有效地支持XML Query查询的处理，反之亦然。如何从XML索引设计的角度避免这一不足，就成为本文关注的另一个问题。本文提出了一种简单而有效的复合索引结构Dew-path。该索引是标签路径索引方式与Dewey索引方式的混合，前者可以有效地支持以标签路径为基本模式的XML Query查询(Xpath和Xquery等)，而基于Dewey编码可以实现关键字查询的要求。