XML文档小枝模式匹配查询算法研究

论文摘要

由于XML具有自描述性和可扩展性等特点,能够满足WEB上对数据描述和存储的需求,因而使得XML正在成为Web上数据表示和交换的事实上的标准。随着XML格式数据的快速增长和广泛应用,对XML数据的查询、转换和存储的研究受到了广泛关注。在XML文档的查询技术研究中,基于小枝模式匹配的结构连接查询是关键的核心内容。对于XML结构查询,可以对XML文档树中的结点或边进行编码,通过编码直接判断结点之间的结构关系,而无需对原XML文档树进行遍历,从而将XML结构查询的计算转化为结构连接的计算。目前对XML文档的编码方法有区间编码、路径编码、前缀编码等。因此,随着不同编码方案的研究,各种相应的结构查询算法也提了出来。对于XML文档基于结构连接的小枝模式匹配查询,是从文档树中查找与查询模式匹配的结点,然后将查找到的匹配结果再组装成最终符合查询表达式的完整树结构。TwigStack是一个典型的关于小枝模式匹配的结构连接查询算法。它采用链栈的数据结构作为缓存,对查询节点流进行整枝计算,从而避免了无用中间结果的产生。基于此算法,又提出了一系列改进的算法。其中Twig~2Stack和TwigList算法分别采用层次关系的堆栈结构和列表结构,避免了复杂的归并过程,进一步提高了查询效率。在我们对小枝模式匹配查询的研究中,发现TwigStack算法对查询节点流在结束时的处理上存在着不足;在对TwigList算法的分析中,发现可以将XML文档的SAX解析应用于查询过程,从而避免了对XML文档进行编码,能进一步提高查询效率。本文的主要工作是:(1)提出了BSTwigStack小枝模式匹配查询算法。该算法增强了原有的TwigStack算法,给出了XML文档在查询节点流结束时的查询匹配处理策略。(2)提出了BSTwigList小枝模式匹配查询算法。针对XML文档的结构特点,在结合XML文档的基于事件的SAX解析方式的基础上,改进了TwigList算法。BSTwigList算法能够应用于节点流模式的小枝查询,在文档解析的同时可以进行模式匹配查询,避免了以往查询算法需要先对文档节点进行编码索引的步骤,使得XML文档在更新时,无需对编码文件进行重新编码和维护,从而减少了查询所需的存储空间,提高了查询效率。(3)最后通过对算法进行的实验和数据测试,给出了算法查询时间响应及性能分析图表,进一步验证了改进的查询算法的有效性。在对以上算法的研究和实现当中,本文所研究的只是XPath查询的一个片段,对于其他形式的XPath查询,仍然有待于进一步的研究;另外本文考虑的只是一种静态XML文档节点数据流的小枝模式匹配查询,而对于在网络环境下的多用户的动态数据流小枝模式匹配查询,还要加以更进一步的研究。这些将成为今后下一步研究的重点和方向。

论文目录

• 中文摘要
• ABSTRACT
• 第一章 引言
• 1.1 课题研究背景
• 1.2 国内外研究现状
• 1.3 论文的主要工作和组织结构
• 第二章 XML文档查询的相关知识
• 2.1 XML文档基本概念
• 2.1.1 XML文档及其模型
• 2.1.2 XML文档编码
• 2.2 XML文档解析
• 2.3 XML文档查询语言
• 2.4 XML文档查询技术
• 第三章 XML小枝查询算法BSTwigStack
• 3.1 相关概念和定义
• 3.2 小枝栈算法TwigStack
• 3.3 改进的小枝栈算法BSTwigStack
• 3.3.1 小枝栈算法BSTwigStack的数据结构及其函数说明
• 3.3.2 BSTwigStack算法
• 3.3.3 BSTwigStack的运行过程
• 3.3.4 BSTwigStack的算法分析
• 3.4 本章小结
• 第四章 XML小枝查询算法BSTwigList
• 4.1 概述
• 4.2 TwigList算法
• 4.2.1 TwigList算法的数据结构说明
• 4.2.2 TwigList算法
• 4.2.3 TwigList算法的运行过程
• 4.3 改进的XML数据流BSTwigList算法
• 4.3.1 BSTwigList算法说明
• 4.3.2 BSTwigList算法
• 4.3.3 BSTwigList算法的运行过程
• 4.4 本章小结
• 第五章 实验及数据测试和分析
• 5.1 实验设置
• 5.2 实验系统流程图
• 5.3 算法测试及性能比较
• 5.3.1 数据测试集
• 5.3.2 性能分析比较
• 5.4 本章小结
• 第六章 结论及工作展望
• 参考文献
• 附录
• 致谢
• 个人简况及联系方式