一种基于Dewey编码的XML小枝模式匹配方法

论文摘要

近几年来,随着数据库和网络技术的迅速发展,XML（可扩展标记语言）已成为Web上数据表示、集成和交换的标准。相比其它的标记语言,XML的格式简单、自我描述能力强,实现了内容、结构和表现三者的分离,更适合于数据表示和交换,因此XML在科学研究、电子商务等各个领域得到了广泛的使用。今天Web上已经涌现了大量的XML数据,所以如何对XML文档进行有效地查询已成为当今数据库领域的一个重要的研究课题。查询XML文档,目前国内外提出的算法主要是基于以下两种思想:第一种是路径分解法,它把将要查询的路径表达式分解成多个简单路径表达式,然后再进行匹配,最后将中间结果连接起来。这种方法不可避免地要产生许多无用的中间结果。另一种是小枝模式匹配方法,它将查询表达式用树的形式建模,称为“小枝模式”（twigpattern）,再将小枝模式到XML文档树中进行匹配,通过扫描一遍输入结点列表就可得到所有的输出结果。这种方法使得算法的I/O代价、CPU时间复杂度和空间复杂度都大大降低,从而提高了查询的效率。目前具有代表性的小枝模式匹配算法有TwigStack和TJfast等。但是,对于包含较多父子边的查询语句这些算法并不是最优的,同时这些算法的一个共同点就是它们并没有利用XML文档的路径索引。为了进一步提高小枝模式匹配算法的效率,本文利用了XML文档的路径索引JoinGuide,提出了一种新的基于Dewey编码的小枝模式匹配方法TwigJoin,主要工作如下:（1）综合区域编码和前缀编码的优点对XML文档进行了编码,对于文档中的实例结点我们使用了前缀编码方案,而对XML文档的路径索引JoinGuide使用了区域编码的方案。（2）对小枝模式匹配算法TwigStack进行了改进,先使用TwigStack算法在XML文档的索引图JoinGuide上得到预匹配结果,然后再扫描预匹配结果中的叶子实例结点序列得到所需的查询结果。（3）在理论上和TwigStack和I-XISS系统进行了详细的对比分析,说明了TwigJoin小枝模式匹配方法的优点。（4）最后构建了一个实验系统,实现了提出的小枝模式匹配方法,然后通过实验把TwigJoin同TwigStack和I-XISS进行了对比,结果表明本文提出的小枝模式匹配方法的效率有了较大的提高。今后的工作是,首先要提高TwigJoin系统中解析和建立路径索引的效率,然后再完善TwigJoin系统中的查询算法,增加TwigJoin系统中对XPath查询语言中各种轴的查询能力,以使其适应更复杂的XML数据查询语句。

论文目录

• 摘要
• ABSTRACT
• 第一章 引言
• 1.1 国内外研究现状
• 1.2 本文的主要工作
• 1.3 论文的组织结构
• 第二章 XML数据库相关知识
• 2.1 XML文档的数据模型
• 2.2 XML数据的编码方案
• 2.3 XML数据的索引
• 2.4 XML查询语言
• 2.5 XML查询算法
• 第三章 XML文档及其JoinGuide索引的关系存储
• 3.1 XML文档的编码方法
• 3.2 XML文档的索引JoinGuide
• 3.3 XML文档索引JoinGuide的逻辑结构图
• 3.4 XML文档的关系存储
• 3.5 关系存储的主要算法
• 第四章 基于Dewey编码的小枝模式匹配方法TwigJoin
• 4.1 小枝模式匹配的定义
• 4.2 XPath查询表达式的表示方法
• 4.3 小枝模式匹配方法TwigJoin
• 4.4 TwigJoin同TwigStack和I-XISS的对比分析
• 4.5 各种路径表达式的处理方法
• 4.6 主要算法
• 第五章 TwigJoin查询系统的设计与实现
• 5.1 查询系统的设计
• 5.2 查询系统的实现
• 第六章 实验与分析
• 第七章 结束语
• 参考文献
• 致谢
• 附录
• 个人简况及联系方式