论文部分内容阅读
随着Internet的迅猛发展,XML已成为数据表达和数据交换的主要标准。XML数据库因此成为研究的热点。XML数据查询是XML数据库的基本功能之一,而对XML文档建立索引是提高查询效率的一个重要手段。为此,本文对纯XML数据库的索引技术进行了研究。
本文首先介绍了XML查询技术,并将索引技术的研究定位在基于路径的(即XPath表达式)查询研究上。接着,较为全面地讨论了目前主流的XML索引技术,并介绍了其原理,分析了其优劣。
前缀编码(Dewey编码)具有字典有序性,其编码算法也比较简单,不但可以很好地保存双亲-子女(P-C)和祖先-后裔(A-D)结点之间的包含关系,而且可以保存XML文档中结点之间位置关系的信息,是判断计算XML文档中任意两结点关系的有力的工具。
本文利用前缀编码这些良好的特性,以基于路径的XML索引原理为基础,以降低复杂度和提高查询效率为目标,设计了一种新型的基于Dewey编码的索引——A-DeweyIndex索引结构,同时设计并实现了基于此索引结构的查询算法。A-Dewey Index索引结构通过对文档结点编码来记录文档的结构信息,利用前缀路径(PrefixXpath)和Dewey编码信息进行匹配操作完成结构连接查询。A-Dewey Index索引结构支持含通配符“*”和后代轴“∥”的查询。
本文还基于XPath表达式查询中的小枝连接策略的思想,设计了一种新型的整体小枝模式查询策略,整体小枝模式查询可以大幅度减少普通连接算法中不必要的扫描和搜索,极大地提高XML数据查询的效率。
最后,为了验证了A-Dewey Index索引结构的有效性和性能,本文做了仿真实验。实验结果表明:基于A-Dewey Index索引结构的查询算法具有较低的时间复杂度,解决了XML文档整体小枝路径查找问题,是一种较为有效的XML索引结构。
此外,由于所有的XML文档处理都从解析开始,即需要把代表XML文档的一个无结构的字符序列转换为满足XML语法的结构化组件。因此,本文对在仿真实验过程中运用的解析技术也进行了分析。
论文在XML数据库索引技术方面做了有益的研究工作。