Native XML数据库的查询优化研究

论文摘要

目前,XML已经成为Internet上数据表示和交换的事实标准。随着XML格式文档的大量涌现,特别是Native XML数据库的出现,向数据库研究领域提出了前所未有的挑战。如何解决用户高效地从Native XML数据库中提取所需信息已逐渐成为一个重要的研究课题。由于传统的查询算法需要对XML数据的树型结构进行多次扫描,这在拥有大量数据的XML数据库中效率极低,不能满足复杂的处理要求,针对这一问题,本课题以XPath路径表达式为主,研究其查询优化方法,目的是在进行树模式查询之前,尽可能地对树模式进行简化,同时对其查询进行分解,在保证查询结果有效连接的前提下,把复杂查询分解为多个简单查询,从而提高查询效率。针对Native XML数据库的查询优化,本文的主要内容和贡献如下:(1)介绍XML的相关技术,比较了XML数据的存储和查询方法,针对几种方法的优缺点,本文采用XML的自然存储方式和树方式进行查询。(2)重点研究了路径表达式的处理,针对查询路径表达式自身存在的反向轴问题,为减少待处理轴的类型和实现快速估算查询代价,对反向轴进行重写。对于查询路径表达式存在的冗余结点问题,根据蕴含理论将其最小化,减小路径表达式所对应的模式树的规模,以提高匹配效率。对于复杂路径表达式存在匹配代价过大的问题,结合导航和连接算法的优点,提出将路径表达式按照某些规则进行分解。(3)最后通过技术手段,对提出的的方法进行了测试,并与几种代表性的方法进行了比较和分析,实验验证了理论的正确性和方法的有效性。

论文目录

• 摘要
• Abstract
• 第一章 前言
• 1.1 课题研究背景
• 1.2 国内外研究现状
• 1.3 课题研究内容
• 1.4 论文的组织安排
• 第二章 XML相关理论与研究
• 2.1 XML简介
• 2.1.1 XML的特点
• 2.1.2 XML的相关标准
• 2.2 XML相关术语
• 2.3 XML数据存储
• 2.4 XML数据查询
• 2.4.1 路径查询
• 2.4.2 树查询
• 2.4.3 图查询
• 2.5 本章小结
• 第三章 路径表达式及其查询优化技术
• 3.1 XPath路径表达式
• 3.1.1 定位路径
• 3.1.2 基本表达式
• 3.1.3 匹配规则
• 3.2 XML查询优化
• 3.2.1 逻辑优化
• 3.2.2 物理优化
• 3.3 结构化连接算法
• 3.3.1 包含关系的结构连接算法
• 3.3.2 文档位置关系的结构连接算法
• 3.4 导航操作算法
• 3.5 本章小结
• 第四章 路径表达式的处理
• 4.1 问题的提出
• 4.2 查询重写
• 4.3 路径表达式的最小化
• 4.3.1 相关概念
• 4.3.2 基于匹配的最小化方法
• 4.3.3 算法分析
• 4.4 路径表达式的分解
• 4.4.1 分解规则
• 4.4.2 分解算法
• 4.4.3 算法分析
• 4.5 实例分析
• 4.5.1 测试文档
• 4.5.2 逻辑匹配
• 4.5.3 物理匹配
• 4.6 本章小结
• 第五章 查询模型的设计
• 5.1 数据查询模型
• 5.1.1 模块功能分析
• 5.1.2 核心类的设计
• 5.2 实验环境
• 5.3 性能评价
• 结论
• 参考文献
• 在学校期间的研究成果
• 致谢