基于小枝模式的XML数据查询处理技术研究

论文摘要

XML作为Intnet上一种数据表示和交换的实际标准,正被广泛接受和采用。随着XML的不断普及,XML数据的管理和查询问题也越来越引起国内外研究学者的重视。在XML数据库中,小枝模式查询是XML查询处理的核心操作,它对于提高查询效率是很有意义的。过去几年来,已经提出了许多小枝模式匹配算法:如TwigStack、TJFast以及最近提出的TwigList和Twig2Stack算法等。这些算法在处理只有祖先后代关系且输出所有结点的查询时效率很高,但是对于带有父子关系或者只有少数输出结点的查询,这些算法的查询效率并不高。本文对XML路径查询处理中的尚存在难点问题进行了深入的研究,并且针对目前算法存在的不足之处,提出了两种高效的非归并小枝模式匹配算法TwigNM和TwigPC。本文主要的贡献如下:1、针对只有少数输出结点的问题:(1).提出了一种更一般化的小枝模式,它具有普遍的适用性,更加符合大多数查询语言标准。(2).提出了两个高效的非归并小枝模式匹配算法,TwigNM算法及其扩展算法TwigNME,这两个算法使用了简单的栈数据结构,可以跳过大量的无扩展结点,避免产生大量的中间结果,也不需要归并,在处理只有祖先后裔关系的查询时效率很高。但是在处理父子关系时,算法的效率仍会受到很大的影响。(3).在TwigNM实验系统上实现了TwigNM、TwigNME、TwigStack和TwigList四个算法。通过与典型的算法TwigStack以及当前最新的算法TwigList算法做比较,结果显示在只有祖先后裔关系且带有返回结点的查询中,本文提出的两个算法的查询效率比其它两个效率高出很多。2、针对有父子边的问题:(1).为了进一步提高有父子关系查询的处理效率,将zhang编码进行了扩展。(2).提出了一种新的数据结构——队列栈,它是由共享存储空间的队列和栈两种数据结构组成的,其结构简单,易于操作。(3).提出了一种非归并的TwigPC算法,该算法使用了队列栈和扩展队列两种数据结构,避免了产生大量的中间结果,也不需要归并,在处理有父子边的查询时效率很高,同时也能较好地处理带有返回结点的查询。(4).在实验系统上实现了TwigPC、TwigStackList和TwigList三个算法。通过比较,结果表明在处理有父子关系的查询中,新算法TwigPC的查询效率比其它两个算法的效率高很多。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 研究背景
• 1.2 国内外研究现状
• 1.3 研究动机
• 1.4 本文主要工作
• 1.5 本文组织
• 第二章 背景知识
• 2.1 XML数据模型
• 2.2 Xpath和XQuery查询语言
• 2.3 小枝模式
• 2.4 XML文档编码方法
• 2.5 索引技术
• 2.6 查询处理算法
• 2.6.1 结构连接算法
• 2.6.2 基于路径字符串的查询处理算法
• 2.6.3 小枝模式匹配算法
• 2.7 小结
• 第三章 基于非归并的匹配算法TwigNM
• 3.1 问题提出
• 3.2 相关概念和定义
• 3.3 查询匹配算法TwigNM
• 3.3.1 数据结构
• 3.3.2 算法思想
• 3.3.3 算法描述
• 3.3.4 扩展算法TwigNME
• 3.4 算法分析
• 3.4.1 算法正确性分析
• 3.4.2 算法复杂度分析
• 3.5 小结
• 第四章 基于P-C关系的匹配算法TwigPC
• 4.1 问题提出
• 4.2 相关概念和定义
• 4.3 查询匹配算法TwigPC
• 4.3.1 数据结构
• 4.3.2 算法思想
• 4.3.3 算法描述
• 4.3.4 带有返回结点查询的处理
• 4.4 算法分析
• 4.4.1 算法复杂度分析
• 4.4.2 算法适用范围分析
• 4.5 小结
• 第五章 实验结果
• 5.1 实验系统设计
• 5.2 XML文档数据集
• 5.3 实验结果及分析
• 5.3.1 TwigNM算法实验结果及分析
• 5.3.2 TwigPC算法实验结果及分析
• 5.4 小结
• 第六章 总结与将来的工作
• 参考文献
• 致谢
• 发表文章目录
• 个人简况