基于XML数据库的查询优化研究

论文摘要

XML已经成为网络上信息描述和信息交换的标准。由于网络上信息的本质特性和XML数据内在的灵活性,很多用XML编码的数据都是半结构化的。随着XML应用越来越广泛,人们提出了多种XML数据的存储模型。与此同时,XML的查询优化也是数据库界研究的一个重要课题。XML数据的查询和关系数据库查询类似,都力图用简洁的查询语句高效准确的进行数据的查询。XQuery已经成为XML查询的标准语言。XQuery的处理方法分为两大类:基于核心语法的处理和基于XML代数的处理。由于XML数据中具有自描述性的模式信息,数据节点的值的类型和大小是很灵活的,不能以固定的形式来处理他们。加上其本身的嵌套结构和模式信息不全的特点,使得其结构非常复杂,对它的查询处理也很困难。XML查询表达式的计算实际上就是寻找树模式查询到文档树的映射的过程,或称之为树模式查询的匹配。一般来说,树模式查询匹配的效率是与树模式查询的规模直接相关的,树模式查询规模越大,匹配效率就越低下,则在进行树模式的查询之前,要尽可能的简化树模式的查询。结构连接操作是XML数据库查询的主要操作,如何恰当的选择结构连接顺序是XML查询优化的核心问题。因此本文对XML代数、树模式最小化查询及结构连接顺序选择技术进行了研究,实现了查询优化的目的。主要研究内容如下:1.在现有的RTA代数的基础上,通过定义操作,对原子类型数据采用简单操作,对列表采用结构递归操作,提出了XQuery到RTA代数的转换方法。然后在RTA代数的基础上,采用完全等价变换原则重写查询,提出优化原则,减少了中间连接代价。2.提出了不存在约束的树模式查询的最小化算法,该算法动态的寻找查询子树之间的覆盖关系,从而发现查询树中的冗余结点并将其删除。在不存在约束的树模式查询算法基础上,提出了存在孩子必需、后代必需、兄弟必需和子类四种约束的树模式查询最小化算法,该算法利用约束先进行膨胀操作,再进行最小化操作,最后得到规模更小但与原始查询树等价的查询树。3.对XML查询优化中各种选择连接顺序算法的研究,提出了一种优化的算法,在规模较大的XML查询中能够有效缩减搜索空间,提高了效率。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 研究目的和意义
• 1.2 XML 数据库的研究内容
• 1.2.1 XML 存储及索引
• 1.2.2 XML 查询处理及查询优化
• 1.3 国内外研究现状
• 1.3.1 XML 数据库技术
• 1.3.2 XML 查询优化
• 1.4 存在的问题
• 1.5 课题来源及研究内容
• 1.5.1 课题来源
• 1.5.2 研究内容
• 第2章 XML 基本定义及其查询语言
• 2.1 XML 数据模型
• 2.1.1 XML 特性
• 2.1.2 OEM 模型
• 2.1.3 DOM 模型
• 2.1.4 XML 模式
• 2.2 现有的XML 查询语言
• 2.2.1 LOREL 查询语言
• 2.2.2 XML-QL 查询语言
• 2.2.3 XPath 查询语言
• 2.2.4 XQuery 查询语言
• 2.3 XML 查询处理结构
• 2.4 本章小结
• 第3章 XML 代数及其查询优化
• 3.1 XML 代数
• 3.1.1 相关研究工作
• 3.1.2 XML 模型
• 3.1.3 XQuery 查询实例
• 3.1.4 RTA 代数
• 3.2 实现XQuery 到RTA 的转换
• 3.3 XML 代数查询优化
• 3.4 本章小结
• 第4章 树模式查询最小化
• 4.1 引言
• 4.2 研究现状
• 4.3 问题描述
• 4.4 无约束树模式查询最小化
• 4.5 带约束树模式查询最小化
• 4.6 本章小结
• 第5章 选择结构连接顺序
• 5.1 相关研究工作
• 5.1.1 穷举式动态规划算法
• 5.1.2 带剪枝的动态规划算法
• 5.1.3 带大幅剪枝的动态规划算法
• 5.2 子树连接算法
• 5.3 本章小结
• 结论
• 参考文献
• 攻读硕士学位期间发表的学术论文
• 致谢