一种针对重复标签的XML文档索引结构及查询算法

摘要

XML（eXtensible Markup Language）作为Internet上数据表示和数据交换事实上的标准，已经得到了快速普及和广泛应用。如何对XML文档进行有效地查询也就成为如今XML研究领域的一个重要的研究课题，而在查询中引入索引方案无疑是一种行之有效的方法。近年来，针对不同的XML应用，人们已经提出了不同的索引结构，如DataGuide，1-Index，F&B和XR-Tree等，这些索引结构能够满足不同特定环境下的需求。
　　XML文档的查询通常被转化为两个结点列表之间的包含关系或文档位置关系的结构连接操作。根据XML文档结构的特点，这些列表中有些结点是能够事先判断出它们是并不参与连接操作的，因此可以先在XML文档的结构索引上进行过滤，从而减少需要处理的元素数量以提高查询算法的整体性能。已有的工作表明，可以通过在各种结构索引上执行过滤来提高查询效率。
　　本文针对XML文档树中重复标签高频出现的现象，给出一种可以高效处理这种重复标签结构的索引存储结构RS-Index，在查询算法中利用索引信息，能够快速过滤与查询无关的元素，以达到提高查询效率的目的。
　　本文的主要工作是:
　　(1)提出了一种针对重复标签的XML文档的索引结构RS-Index，并给出了相应的索引结构形成算法。
　　(2)在RS-Index的索引结构上提出了相应的过滤算法。并以该过滤算法为基础，给出了一种新的查询算法，快速找到满足查询条件的元素序列。
　　(3)构建了一个实验系统，在系统中实现了本文提出的索引结构、过滤算法和查询算法。
　　(4)把本文提出的RS-Index索引结构与其他相似的索引结构在通用的数据集上进行了较为全面的比较。
　　实验数据表明，使用该索引结构及其查询算法，对于具有大量重复标签的XML文档，可以提高查询效率。

目录

摘要

第一章 引言

1．1 国内外研究现状

1．2 本文的主要工作

1．3 论文的组织结构

第二章 XML数据库相关知识

2．1 XML基础知识

2．2 XML的查询与Xpath查询语言

2．3 XML数据的编码方案

2．4 XML数据存储

2．5 1-Index索引

2．6 小枝查询模式

第三章 RS-IndeX索引方案与形成算法

3．1 RS-Index索引方案的提出背景

3．2 RS-Index索引数据结构

3．2．1 RS-Index索引结构

3．2．2 RS-Index索引构造

3．3 RS-Index索引构造算法

第四章 基于RS-Index的查询过滤算法

4．1 过滤算法

4．2 查询算法

第五章 实验及分析

5．1 查询系统的设计

5．2 查询系统的实现

5．3 实验结果及分析

第六章 结束语

参考文献

致谢

发表文章目录

个人简况及联系方式

声明