论文部分内容阅读
XML(eXtensible Markup Language)即可扩展的标记语言，是一套定义语义标记的规则，是Internet环境中跨平台的技术，其目的在于定义计算机和人都能方便识别的数据类型。随着信息技术的迅猛发展，XML已经被广泛地应用到数字图书馆、银行数据交换、电子商务、搜索引擎软件等领域，这使得XML数据成为关系数据之后新的主流数据形式。 随着XML应用的不断深入，如何简化XML数据的查询成为近来人们普遍关注的问题。XML结构化查询与XML关键字查询成为XML数据库新的技术发展方向。XML结构化查询一般要求用户掌握查询语言的相关语法机制和所查询文档的数据组织结构，这对于普通用户来说非常困难。而XML关键字查询只需要用户提交一些关键字信息，而无需掌握相关语法和数据组织结构，这大大方便了普通用户的使用。因此，本文研究的重点是XML关键字查询模式。 XML关键字查询中最紧致片段的定义以及高效的编码方法决定了XML关键字查询的性能和准确率，因此，XML关键字查询的核心问题是最紧致片段的定义以及XML数据的编码。 现有的求解XML关键字查询算法大多是以SLCA为语义，通常大量地进行LCA的计算，这需要反复地比较Dewey编码，而比较两个Dewey编码大小的时间复杂度为O(n)，同时会造成公共祖先的重复访问，导致算法的性能下降。 因此，针对以上不足，本文的主要工作包括以下两个方面: 1.根据LTR(Level-Traverse)编码并结合ELCA语义，设计出自底向上逐层求解结果集的查询算法，提高了XML关键字查询的检索效率和准确度。 2.按照树的前序遍历顺序给每一个节点分配一个唯一的ID值，并根据ID倒排列表求出所有关键字的CA节点，最终求出SLCA结果集。实验证明该算法有效地提高了XML关键字查询的时间性能。