XML数据查询处理技术的研究

论文摘要

由于其良好的可扩展性和灵活性,XML已经成为Web上数据表示和交换的标准,在各种应用中出现大量的XML形式的数据。作为一种半结构化数据,XML数据的高效处理带来了新的挑战。XML数据管理已经成为数据管理中一个重要的研究领域。XML数据管理中一个重要问题是如何对XML数据进行高效的查询处理。本文以XML数据的高效查询处理为目标,研究了树结构XML文档、图结构XML文档、XML数据流和基于XML的信息集成系统中的查询处理,主要研究成果如下:(1)提出了一整套支持树结构XML文档上路径查询高效处理的方法。具体的,提出树结构XML文档的磁盘存储结构。该存储结构有效地结合了结构索引、基于编码的连接操作以及树的遍历操作,支持复杂路径查询的高效处理。基于这种存储结构,提出了多种查询操作的实现方法。针对带有复杂结构和值约束的路径查询,提出了代价模型和基于代价模型的查询优化策略。实验结果表明这种查询处理方法有着很高的效率和可扩展性,查询优化策略可以快速有效地生成查询计划。(2)在图结构XML文档的查询处理方面,提出了子图查询和拓扑查询的处理方法。具体的,对DAG上的可达编码进行了扩展,使之能够支持有圈的图,并且提出了有效支持子图查询的编码存储方法。基于这种存储方法,提出了子图查询处理策略。这种策略能够高效地处理形式为一般图、包含可达关系的子图查询,经过简单的扩展,可以用来处理同时包含可达关系和连接关系的子图查询。实验结果表明本文提出策略能够高效地处理子图查询。提出了一种图结构XML文档上的新型查询―拓扑查询,并且给出了拓扑查询的高效处理算法。(3)在XML数据流的查询处理方面,首次提出了XML数据流上聚集查询的问题,对其给出了精确定义并提出了高效查询处理算法,既支持复杂的XPath表达式,又适用于多种类型的XML聚集,并且可用于基于SAX的XML文档上的聚集查询处理。分析和实验结果表明本文的提出算法具有很高的效率和可扩展性。(4)在基于XML的信息集成方面,本文对结果传输、返回结果合并与数据源选择这三个关键技术问题进行了研究。具体的,提出了两种对作为结果返回的XML数据片段进行缩减的策略。提出了基于XML的信息集成系统中XML数据片段的连接操作,用来描述多种情况下XML数据片段的连接,对这些连接操作提出了高效的实现算法。提出了用于数据源选择的索引结构,能够同时对数据源中值的信息和结构信息进行概要,从而为具有复杂结构和值约束的查询进行数据源选择。还提出了两种索引缩减策略。基于压缩和非压缩的索引结构,分别提出了有效的数据源选择方法。实验结果表明这种数据源选择方法有很好的精度和效率,索引缩减策略能够在不过多损失数据源选择性能的情况下有效地缩减索引。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 研究的目的和意义
• 1.2 国内外研究现状
• 1.2.1 树模型XML查询处理的研究
• 1.2.2 图模型XML文档查询处理的研究
• 1.2.3 XML数据流查询处理的研究
• 1.2.4 基于XML信息集成以及相关技术的研究
• 1.2.5 存在的问题
• 1.3 本文主要研究工作
• 1.3.1 主要研究内容
• 1.3.2 主要研究成果
• 1.4 本文主要章节安排
• 第2章 树结构XML文档查询处理技术
• 2.1 问题的提出
• 2.2 树结构XML文档的存储方法
• 2.2.1 基于磁盘的F&B索引部分
• 2.2.2 源文档部分、区间编码部分与值部分
• 2.3 树结构XML文档的查询操作算法
• 2.3.1 基本查询操作
• 2.3.2 基于树搜索的路径查询处理策略
• 2.4 树结构XML文档的查询优化方法
• 2.4.1 查询计划的形式
• 2.4.2 代价模型
• 2.4.3 查询计划的生成
• 2.5 实验
• 2.5.1 实验配置
• 2.5.2 查询计划质量
• 2.5.3 查询优化时间
• 2.5.4 变化系统参数
• 2.5.5 和其他系统的比较
• 2.6 本章小结
• 第3章 图结构XML文档查询处理技术
• 3.1 问题的提出
• 3.2 图结构XML文档的存储方法
• 3.2.1 图结构XML文档的编码方法
• 3.2.2 编码的存储方法
• 3.2.3 实验
• 3.3 图结构XML文档上子图查询处理算法
• 3.3.1 子图查询的定义
• 3.3.2 特殊子图查询的处理算法
• 3.3.3 形式为一般DAG的子图查询处理算法
• 3.3.4 有圈的子图查询处理算法
• 3.3.5 带有邻接关系子图查询的处理
• 3.3.6 实验
• 3.4 图结构XML文档上拓扑查询处理算法
• 3.4.1 拓扑查询的定义
• 3.4.2 拓扑查询处理算法
• 3.4.3 实验
• 3.5 本章小结
• 第4章 XML数据流查询处理技术
• 4.1 问题的提出
• 4.2 XML数据流上聚集查询的处理
• 4.2.1 XML数据流上聚集查询的定义
• 4.2.2 XML数据流上聚集查询处理算法
• 4.2.3 实验结果
• 4.3 本章小结
• 第5章 基于XML的分布式信息集成系统中的查询处理方法
• 5.1 问题的提出
• 5.2 基于XML的分布式信息集成系统中结果的缩减
• 5.2.1 缩减策略
• 5.2.2 实验
• 5.3 用于接收结果的连接算法
• 5.3.1 双数据源的连接算法
• 5.3.2 多个数据源的多路连接算法
• 5.3.3 实验
• 5.4 XML数据源选择算法
• 5.4.1 数据源选择的数据结构
• 5.4.2 数据源选择策略
• 5.4.3 树结构索引上选择数据源的策略
• 5.4.4 实验
• 5.5 本章小结
• 结论
• 参考文献
• 附录
• 攻读博士学位期间发表的学术论文
• 致谢
• 图表索引
• List of Figures and Tables
• 个人简历