基于索引技术的XML查询优化研究

摘要

如今XML数据被广泛应用于不同领域，其数据和文档规模不断增大，数目不断增多，导致网络中出现了大量的具有复杂结构的XML数据。如何高效管理和查询结构复杂的XML数据是当前人们面对的一个普遍且关键的课题。在过去的十多年中，众多的研究人员和学者从不同的角度提出了各种查询优化的方法，其中利用编码的索引技术是实现查询优化最常用的重要手段之一。在查询优化设计中，充分考虑编码的索引技术，可以很好的实现对XML数据查询优化的需要。因此，结合编码与索引技术来对XML数据查询优化进行探讨，仍然是一个值得深入研究的课题。
　　 论文在二叉树遍历的编码基础上，引入二叉树的三叉链表存储结构对XML文档结点进行编码。设计出一种基于二叉树遍历XML文档编码模式。该编码模式利用二叉树的三叉链表结构来存储XML文档树的结点，用自然数作为结点的编码序号。采用该编码模式作为XML文档树结点编码，选取合适关键词作为索引项，利用二叉排序算法为XML文档建立了相关索引模型。
　　 论文在传统区间编码基础上，利用倒排表和B+树作为基本的索引组织，设计出一个由DTD结构索引、XML文档索引和内容索引组成的联合结构索引模型。其中DTD索引采用倒排表作为索引基本单位，XML文档索引采用B+树来建立，内容索引则采用倒排表。在处理的查询时，只要通过一个入口即可以找到其它索引项来完成一个综合的多种查询处理要求。
　　 理论与实验结果分析表明，论文中基于二叉树遍历的编码模式，具有存储空间小和查询效率高，且支持动态数据更新操作。以此编码建立的索引具有空间开销小、查询响应速度快和查全率高的特点;以区间编码作为文档树结点编码，建立的联合结构索引模型，处理数据查询时具有较高查询效率，能够满足多文档查询的需求并且满足了对XML文档混合型优化查询（文本查询和结构查询）等需求。

目录

声明

摘要

第一章 绪论

1．1 研究背景

1．2 国内外研究现状

1．2．1 国内外研究现状的综述

1．2．2 现存在的问题及研究重点

1．3 研究的目的及意义

1．4 论文的主要工作

1．5 论文的内容组织安排

第二章 数据存储及查询处理技术

2．1 XML数据存储技术

2．1．1 XML数据模型

2．1．2 XML数据库系统

2．2 XML路径查询处理

2．2．1 传统查询路径计算方法

2．2．2 路径查询分解与连接

2．3 XML查询语言

2．4 XML查询优化

2．4．1 查询处理过程

2．4．2 查询优化技术

2．5 本章小结

第三章 基于二叉树遍历的文档编码模式

3．1 XML树编码的相关知识

3．1．1 XML树的编码概念

3．1．2 编码分类

3．1．3 编码的依据标准

3．2 常见编码方法介绍

3．2．1 前缀编码

3．2．2 区间编码

3．2．3 二叉树编码

3．3 基于二叉树遍历的文档编码模式

3．3．1 编码的相关背景

3．3．2 基于二叉树遍历编码原理

3．3．3 XML树结点编码构造步骤描述

3．4 CSBTT编码的相关操作及算法

3．4．1 结点插入操作及算法

3．4．2 结点删除操作及算法

3．4．3 结构关系判定及辈差计算

3．4．4 实验结果及性能分析

3．5 CSBTT编码索引设计

3．5．1 索引设计的基本思路

3．5．2 索引设计算法

3．5．3 数据查询与相关算法

3．5．4 利用索引查询数据实例

3．5．5 性能分析

3．6 本章小结

第四章 联合结构的索引模型

4．1 数据索引的概论

4．1．1 相关概念介绍

4．1．2 索引的分类方法

4．1．3 索引设计应考虑的因素

4．2 经典的数据索引技术

4．2．1 基于结点记录的索引技术

4．2．2 基于路径结构的索引技术

4．2．3 基于序列的索引技术

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．2 后续工作展望

参考文献

致谢

攻读硕士学位期间完成论文情况

攻读硕士学位期间参加的科研项目情况