纯XML数据库中基于索引的并行查询处理技术的研究

摘要

XML以其扩展性、结构性、平台独立性和自描述性等特性成为数据表示和交换的事实标准，越来越多的应用使用XML来存储、交换和发布信息。但是目前关系数据库并不能很好的支持XML数据。纯XML数据库应运而生，它专门用来存储和管理XML数据。越来越多的XML数据库致力于设计和开发高效的查询XML数据的系统。并行处理为大型XML文档的高效处理提供了有效的解决途径。如何在并行环境中进行查询处理优化逐渐成为研究热点。
　　首先，本文介绍了并行纯XML数据库系统的整体架构，分析了文档分片后的特点，设计了按照单枝路径对原查询进行分割的基本策略，并设计了一套代数系统。该系统使用一次一集合的方法执行并行查询。该查询代数系统中包括九种操作符，分别为定位操作符、选择操作符、与操作符、或操作符、分枝连接操作符、半连接操作符、聚类操作符、配对操作符以及构造操作符，并提出了一些优化方式。然后，本文研究了现有的XML索引技术，针对单枝查询中可能出现的三种情况，分别设计对应的索引类型，包括节点索引、路径索引以及文本索引，同时提出了基于代价估计的的查询优化算法和基于索引的结构连接算法，用于加速路径查询的处理。最后，本文对XML关键字查询进行了分析，研究了在并行XML数据库中基于SLCA语义的关键字查询，提出了SONB算法和MSOP算法。SONB算法用于在单机上执行SLCA查询，MSOP用于在并行环境中执行SLCA查询。在处理大量数据时，能够快速查询出满足条件的节点。
　　本文对以上技术进行了全面的实验评估与分析。实验结果表明，并行查询算法在并行环境下执行效果良好，索引对于加速单枝查询具有关键作用，文本提出的SONB算法和MSOP算法对于关键字查询具有较高的效率。

目录

声明

摘要

第1章 绪论

1．1 研究背景

1．2 研究现状

1．3 本文的主要研究内容

1．4 本文的组织结构

第2章 相关技术

2．1 XML文档解析器

2．1．1 SAX

2．1．2 DOM

2．2 编码方式

2．2．1 位向量编码

2．2．2 前缀编码

2．2．3 区间编码

2．3 XML文档分片技术

2．4 XML数据的索引技术

2．5 XML查询语言

2．6 关键字查询技术

2．6．1 基于栈的处理算法

2．6．2 ILE算法

2．6．3 LISA算法

2．7 本章小结

第3章 并行查询分解的研究与实现

3．1 相关工作

3．2 问题提出

3．3 PPXA的设计与实现

3．3．1 Pattern结构

3．3．2 Constructor结构

3．3．3 PPXA操作符的设计

3．3．4 PPXA的查询优化

3．3．5 PPXA操作符的执行

3．4 实验设计与结果分析

3．5 本章小结

第4章 索引管理策略

4．1 问题提出

4．2 索引类型

4．2．1 节点索引

4．2．2 路径索引

4．2．3 文本索引

4．3 索引创建算法

4．4 基于索引的查询处理

4．4．1 基于代价估计的查询优化策略

4．4．2 基于索引的结构连接算法

4．5 索引的更新

4．6 实验设计与结果分析

4．7 本章小结

第5章 关键字查询的研究与实现

5．1 问题提出

5．2 SONB算法

5．2．1 索引的存储结构

5．2．2 SLCA性质

5．2．3 算法描述

5．3 MSOP算法

5．4 实验设计与结果分析

5．5 本章小结

第6章 总结与展望

6．1 内容总结

6．2 未来展望

参考文献

致谢

攻读硕士期间发表的论文和参加的项目