基于下推自动机的XML数据流递归查询处理技术研究

摘要

传感器数据处理、金融证券管理、Internet流量监控、Web使用日志及电话呼叫记录的在线分析等新型应用领域对数据的管理与分析提出了新的要求，数据流及其相关技术已成为当前数据处理领域的研究热点之一。近年来，XML语言已成为互联网上信息表示和数据交换的重要标准，随着Web服务和个性化信息订阅等应用的蓬勃发展，越来越多的信息以XML的格式通过网络被发布和交换。在这些应用中，XML数据是以流的形式不断地快速到达，因此XML数据流的管理和分析成为当前数据流研究领域中的一个重要热点。 随着XML应用的深入，具有不同递归深度的XML数据流广泛出现，当具有子孙轴(//)和谓词([])结构特征的XPath对它进行查询时，将会发生多重匹配的情况，从而会产生大量的匹配模式。传统算法的关注点主要集中在XML数据流上执行海量的XPath查询，无法适应当前新的情况，因此有效地实现XML数据流递归查询成为当前迫切需要解决的问题。 本文结合XML数据流处理的特点，分析和研究了目前解决XML数据流上查询处理的方法和实现机制，根据XPath语法规则，即任意一个XPath路径表达式都可转化成一个上下文无关文法，根据自动机理论，提出了基于下推自动机技术的处理方法。该方法通过将XPath各类位置步转化成对应的处理模块，由这些模块构建成自上而下的树状查询模型，有效地实现XML数据流递归查询。 最后对本文涉及的系统进行了性能测试，实验结果表明自动机技术可以有效地解决XML数据流的递归查询问题，而且提出的方法在性能上要优于传统方法。

目录

文摘

英文文摘

声明

引 言

1绪论

1.1 XML的概念及特点

1.2 XML与相关技术

1.3 XML语言的研究领域

1.4 XML数据流的应用兴起

1.5 XML数据流研究现状

1.5.1过滤算法

1.5.2查询算法

1.6主要工作及组织结构

2背景知识

2.1 XML数据管理技术

2.1.1 XML文档数据库查询

2.1.2 XML数据流查询

2.2 XML数据流

2.2.1 XML文档

2.2.2 XML数据流及递归性

2.2.3 XML数据流处理特点

2.3 XML分析器

2.3.1 DOM

2.3.2 SAX

2.3.3 SAX与DOM的对比

2.4 XML查询规范

2.4.1 XPath

2.4.2XQuery

2.5形式语言与自动机

2.5.1上下文无关文法

2.5.2下推自动机

2.5本章小结

3带谓词的XPath递归查询处理

3.1带谓词的递归查询问题

3.2基于自动机的XPath查询模型

3.2.1有限状态自动机

3.2.2非确定的有穷自动机

3.2.3确定的有穷自动机

3.2.4下推自动机

3.3基于下推自动机的XPath查询处理方法

3.3.1数据流处理模型

3.3.2解决问题的基本思想

3.3.3 XPath位置步的模块化

3.3.4树状查询模型的构建

3.4本章小结

4基于下推自动机的XPath查询处理的设计与实现

4.1 SAX事件流类型

4.2查询模型的主要数据结构

4.3查询模型的查询处理过程

4.4本章小结

5实验测试和结果分析

5.1实验环境

5.2系统界面简介

5.3测试结果及分析

5.4本章小结

总结与展望

参考文献

在学研究成果

致 谢