XML结构索引技术及查询优化研究

摘要

为了实现XML的查询优化，近年来人们相继提出了很多索引技术和连接算法[12,13,14，15,16,23,24]。这些索引主要是根据边标签和元素值建立的。然而有的索引不包含所有的元素结点，因而在进行查询时许多路径仍需要检测；有的在向前或向后遍历时产生了大量的冗余数据，从而造成查询代价较大。另外，在所提出的算法中，尽管有的算法，如MPMGJN算法[23]优于标准的RDBMS连接算法，但是该算法为匹配基本的结构关系，特别是在父子关系情况下，执行了大量不必要的计算和占用了大量的I/O资源；有的算法虽然代表了结构连接算法的先进水平，如Stack-Tree-Desc[24]连接算法，但是它没有利用索引结构而是顺序浏览输入列表。这样，必然浪费I/O资源，影响连接的速度。 针对以上情况，本文做了以下几个方面的工作： ①由于采用传统的NumberingSchema方法来表示XML文件结构不便于元素更新，本文在改进的基础上提出了SparseNumberingSchema方法。与传统方法相比，其优点在于：由于在插入新结点时不需要重新计算其结点的start和end值，树结构更新效率得到提高；树的创建只需遍历一次文档，进一步地节省了建树开销；此外，它还能为索引提供一个相对持久和稳定的参考。 ②鉴于目前关于NumberingSchema存储方法的研究较为少见，本文针对SparseNumberingSchema进行研究，给出了在关系数据库中的存储方法。该存储方法不仅有利于根据start值快速建立索引，而且可以节省存储空间。 ③本文将关系数据库中B+树索引技术与SparseNumberingSchema相结合，提出了一种新的XML文件索引结构——B+树结构索引，它对XML查询中连接操作和元素定位操作的优化有着重要作用。进而，通过引入指针对该索引进行改进，提出了一种带有SiblingPointer的B+树结构索引(简称B+-SP)。利用这种索引可以克服元素查找总是从树的根部开始进行的缺陷。 ④基于B+-SP索引，本文还研究给出了Anc-Desc-B+-sp连接算法。经理论分析，其算法的时间复杂度O(|A|+log|A|)比没有采用该索引的Stack-Tree-Desc算法[24]的时间复杂度O(|A|+|D|outlist|)明显降低，因|D|≥|A|，故|D|+outlist|＞＞log|A|。经初步实验表明，本算法是一个有效、快速的连接算法。 ⑤在XML查询中，影响查询时间的另一个重要因素是对涉及的XML数据源的定位问题。为解决XML数据源的快速定位问题，本文提出了一种分布式XML数据源定位系统框架，协作式XML搜索引擎(CXSE)。CXSE通过基于站点选择搜索和对XML数据源计分等方法来缩短收集时间，来实现对XML数据源的快速、准确定位。特别地，当在XML查询中同时涉及多个XML数据源时，该并行搜索技术也能起到一定的效果。

目录

文摘

英文文摘

1绪论

1.1当前国内外研究的现状

1.2当前技术存在的问题

1.3论文的选题及其研究意义

1.4论文的研究内容及其组织

2 Sparse Numbering Schema

2.1现有的数据模型及其不足

2.2 Sparse Numbering Schema

2.3本章小结

3 Sparse Numbering Schema的存储

3.1 XML数据的存储方式

3.2关系数据库方式的存储

3.2.1映射方式的选择

3.2.2 DTD到对象模式的映射

3.2.3对象模式到数据库模式的映射

3.3 Sparse Numbering Schema的存储

3.4本章小结

4一种新的B+树结构索引

4.1现有的XML文档索引结构及其不足

4.2 B+树结构索引

4.2.1 Sparse Numbering Schema与B+树相结合

4.2.2 B+树结构索引的建立

4.2.3检索B+树结构索引的原理

4.3带有Sibling Pointer的B+树结构索引(B+-sp)

4.3.1 B+-sp的结构

4.3.2 B+-sp的更新

4.4本章小结

5基于B+-SP的连接算法

5.1现有的连接算法及其不足

5.2基于B+-SP的Anc-Desc-B+-sp连接算法

5.2.1连接元素的基本结构关系

5.2.2基于B+-SP的连接算法

5.3本章小结

6 Web上XML数据源的快速定位

6.1当前查询和搜索存在的问题

6.2协作式XML搜索引擎框架

6.3 CXSE的搜索及更新过程

6.3.1 CXSE的搜索过程

6.3.2 CXSE的更新

6.3.3 CXSE的特征

6.4本章小结

7实验

7.1实验准备

7.2 B+树结构索引和No-index算法的比较

7.3 B+-sp和B+树结构索引的比较

7.4 B+-sp和No Index算法的比较

7.5本章小结

8总结和展望

8.1小结

8.2未来的工作及研究方向

致谢

参考文献

附录1、实验所用的XML文档

附录2、所发表的文章