XML Twig查询优化研究

摘要

XML因其具有自描述性，可扩展性以及开放性等优点已经成为网络上信息表达和数据交换的事实标准。随着XML数据的不断增长，尤其是大规模XML数据的出现(如XML数据库)，对XML数据的查询正在成为学术界和工业界的研究热点。但同时由于XML文档具有的半结构的特性，使得传统的对关系数据库的查询算法对其不适用，因此如何高效地查询XML数据成为新的研究课题。 为了实现XML的查询优化，近年来人们提出了各种算法，主要有基于路径索引的树遍历、基于序列的方法以及结构连接和整体twig查询，其中整体twig查询可以避免结构连接产生大量的中间结果而具有很大的优越性，得到了广泛的研究。 本文对整体twig查询优化展开研究，主要做了以下几个方面的工作： (1)提出了DBL排序算法，用于决定叶子查询结点的处理顺序，更重要的是在构造与查询结点相关联的列表中起到过滤对查询结果没有贡献的元素的作用。 (2)提出了一种新型的整体twig查询算法TWigStackFast，它是个单阶段算法，采用Extended Dewey编码，能够处理带A-D关系、P-C关系的查询，而且是CPU和I/O最优的。IWigStackFast算法没有第二阶段的合并连接操作，因而可以消除了大量的时间和空间开销。 (3)通过把TwigStackFast算法与四个经典的twig查询算法TwigStack、HolisticTwigStack、Twig2Stack、TJFast进行实验对比后可以看出，TwigStackFast具有更优越的性能。

目录

文摘

英文文摘

声明

第一章绪论

1.1研究背景及意义

1.2国内外研究现状

1.3研究动机

1.4主要研究工作

1.5论文的组织结构

第二章XML背景知识

2.1 XML简介

2.2 XML文档模型

2.3 XML与DTD

2.4 XML查询语言

2.5 XML文档树编码

2.5.1区间编码

2.5.2前缀编码

第三章整体twig查询算法

3.1相关概念

3.1.1 twig模式查询

3.1.2 twig模式匹配

3.2已有的整体twig查询算法

3.2.1 TwigStack算法

3.2.2 HolisticTwigStack算法

3.2.3 Twig2Stack算法

3.2.4 TJFast算法

3.3本章小结

第四章一种新的整体twjg查询算法

4.1 Extended Dewey编码

4.2数据结构

4.3 DBL排序

4.4 TwigStackFast算法

4.5算法分析

4.5.1正确性分析

4.5.2时间复杂度分析

4.5.3空间复杂度分析

4.6实例说明

4.7本章小结

第五章实验分析

5.1实验数据和环境

5.2实验系统

5.3实验结果

5.3.1读取元素个数

5.3.2中间结点个数

5.3.3执行时间

5.4本章小结

第六章结论和进一步的工作

参考文献

攻读硕士学位期间发表的论文

致谢