一种基于XML数据流查询算法的设计与实现

摘要

随着互联网的迅猛普及，网络在人们生活中所占的比重也越来越大，网络中出现大量与XML数据流有关的应用，比如网络日志、股票分析、互联网监控、数据安全管理、位置信息、电子信息查询等。以XML数据流为形式传输的数据有以下特点：数据量较大，而且不可预知；所有的数据都是在线到达，实时性高，并且无法确定其到达的顺序。显而易见，如果按照传统的数据管理方式进行处理将会非常困难而且浪费资源，因为传统的数据管理方式中的数据都是可以预知的，所有的数据都是预先存储的。近几年，研究人员已经提出很多种对于XML数据流的查询算法，如TurboXPath和StreamTX算法等。但TurboXPath已被证明在递归调用时存在潜在的隐患，StreamTX对于处理Parent-Child(PC)关系的查询时，会有很高的计算代价，在效率和灵活性上一直不能体现出令人满意的性能，所以设计一种更有效的查询算法成为了当务之急。
　　针对以上问题，提出一种XML数据流小枝匹配算法TwigPM，在处理可能具有复杂的递归、层次结构的XML数据流时能通过获取查询节点的结构关系，进行有效的剪枝操作，节省了存储数据所占用的内存空间，避免了匹配的过程中可能产生的大量中间结果。算法功能分为两部分，第一部分得到查询树各节点的结构关系（包括父亲-孩子关系和祖先-后代关系），并将不同性质的节点进行分类；第二部分是剪枝和匹配过程。对于先后到达的元素事件，根据第一部分的节点分类对进行剪枝操作，移除一定不会存在于最终结果中的节点元素，并且在每个与查询根节点对应的End事件到达时进行匹配操作，得到匹配结果。
　　根据提出的算法进行了性能测试，实验结果表明，TwigPM算法是高效的，尤其在处理存在父亲-孩子关系的查询时，能有效避免无关匹配，提高了查询效率。

目录

封面

声明

中文摘要

英文摘要

目录

1绪论

1.1 XML的背景知识

1.2 XML数据流的国内外研究现状

1.3课题的研究意义及主要研究内容

2基础理论

2.1 XML数据流管理系统与数据库管理系统的区别

2.2 XML文档的相关概念

2.3 XML数据流

2.4 XML查询规范

2.5 XML解析工具

3小枝匹配算法TwigPM的提出

3.1相关定义

3.2 TwigPM算法的匹配过程

4 算法的应用与实现

4.1 获取结构关系与剪枝操作的实例

4.2多个查询根节点的小枝匹配实例

5实验测试及结果分析

5.1试验环境

5.2测试结果及分析

结 论

参考文献

在学研究成果

致谢