XML簇聚存储及路径选择性代价估计研究

论文摘要

随着互连网的快速发展,出现了大量的Web数据,这些Web数据多以XML文档形式出现,如何有效存储XML文档和从大量XML文档中检索有用信息,已成为数据库研究领域的一个重要研究课题。本文的研究工作主要围绕XML数据存储和查询优化展开,重点研究XML簇聚存储模型和路径选择性代价估计。首先对XML技术做了综述,分析了XML的研究现状和技术上的突破,然后重点从XML簇聚存储和查询优化两个方面做了深入的研究工作。在XML簇聚存储方面,针对DOM（文档对象模型）不能有效减少XML查询的磁盘I/O问题,提出了X-cluster簇聚存储模型,此模型根据结点划分思想将XML文档中结点结构与结点值最为“相似”的一组结点簇聚在一起,并为不同的结点值类型引入了不同的存储模型和压缩方法,解决了以往簇聚模型中人为地割裂结点结构与结点值之间的关系,簇聚误差过大的问题;在XML查询优化方面,深入研究了XML路径选择性代价估计,详细分析了基于直方图的路径选择性代价估计（HPM）方法,针对HPM方法计算效率低,选择性估计精度不高的缺点,将X-cluster簇聚大纲统计信息模型引入路径选择性代价估计中,提出了CHPM方法。该方法通过计算选择率为百分之百的结点或路径跳过不必参与直方图运算的结点或路径,减少了代价树的规模,从而提高路径选择性代价估计的效率;同时为了避免中间结果直方图某些格中的高频数据对后续直方图运算精度的影响,给出了直方图的压缩策略,通过压缩使直方图中的数据近似满足均匀分布,从而降低路径选择性估计的误差。实验表明,X-cluster簇聚大纲及基于此大纲和压缩直方图技术的XML含值谓词路径选择性代价估计方法无论是针对单谓词简单路径选择性代价估计还是多谓词复杂路径选择性代价估计,代价估计的相对误差都较低,是一种可行而有效的方法。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景及意义
• 1.1.1 课题研究背景
• 1.1.2 XML面临的挑战
• 1.1.3 课题研究意义
• 1.2 目前国内外的研究现状
• 1.3 论文的主要工作
• 1.4 论文的组织
• 第二章 Native XML数据库相关技术研究综述
• 2.1 XML相关概念
• 2.1.1 XML文档
• 2.1.2 XML数据模型
• 2.1.3 DTD与XMLSchema
• 2.2 XML数据库技术
• 2.2.1 XML数据库定义
• 2.2.2 XML数据库分类
• 2.3 XML数据库查询语言
• 2.3.1 XPath查询语言
• 2.3.2 xQuery查询语言
• 2.4 XML簇聚存储技术
• 2.4.1 存储粒度
• 2.4.2 基于模式簇聚的存储策略
• 2.5 XML查询优化技术
• 2.5.1 逻辑优化
• 2.5.2 物理优化
• 2.6 本章小结
• 第三章 构建X-cluster簇聚大纲模型
• 3.1 引言
• 3.2 X-cluster簇聚大纲数据模型
• 3.3 X-cluster簇聚大纲结点合并与误差度量
• 3.3.1 X-cluster结点合并
• 3.3.2 X-cluster误差度量
• 3.4 X-cluster簇聚大纲结点值压缩
• 3.5 X-cluster簇聚大纲构造算法
• 3.5.1 X-cluster构造算法及算法分析
• 3.6 本章小结
• 第四章 基于X-cluster簇聚大纲指导的路径选择性代价估计
• 4.1 引言
• 4.2 Extent（u）的直方图表示
• 4.3 基于直方图的路径选择性代价估计
• 4.3.1 值-位置直方图
• 4.3.2 基于直方图的路径选择性代价估计（HPM）
• 4.4 X-cluster簇聚大纲指导的路径选择性代价估计
• 4.4.1 X-cluster簇聚大纲统计信息模型
• 4.4.2 简单路径选择率计算
• 4.4.3 复杂路径选择率计算
• 4.4.4 基于压缩直方图的路径选择性代价估计（CHPM）
• 4.5 实验性能测试
• 4.5.1 选择率误差实验分析
• 4.5.2 单谓词简单路径选择性精度实验分析
• 4.5.3 多谓词复杂路径选择性精度实验分析
• 4.6 本章小结
• 第五章 总结与展望
• 参考文献
• 致谢
• 攻读学位期间主要的研究成果