基于lazyDFA的XML数据流查询处理及优化技术研究

论文摘要

随着金融证券管理、Internet流量监控、Web使用日志等新型应用领域对数据的管理与分析提出了新的要求,数据流及其相关技术已经成为当前数据处理领域的研究热点之一。由于XML语言已经成为互联网上信息表示和数据交换的重要标准,所以也就相应地出现了大量的XML数据流相关应用,比如基于内容的XML路由、Web服务、主动服务中的订阅和发布系统等。在这些应用系统中,XML数据是以流的形式不断地快速到达的。因此对XML数据流进行管理和分析的理论和技术又成为目前数据流研究领域中的一个热点。XML数据流处理系统都是运行在Internet环境中的,该环境下的用户是海量的,海量的用户利用XPath查询语句描述其需求,那么如何在XML数据流上执行海量的XPath查询便成为XML数据流应用中一个迫切需要解决的问题,因此本文选择该部分进行研究。本文结合XMI数据流处理中每个XML结点最多只能访问一次、处理算法具有尽可能小的空间复杂度、每个结点的处理必须具有很高的时间效率以满足实时处理需要的特点;分析和研究了目前解决XML数据流上查询处理的方法和实现机制;根据XPath语法规则,即任意一个XPath路径表达式都可转化成一个正则表达式,基于自动机理论,完成了NFA和lazyDFA的构造,实现了XPath表达式的查询处理,并为提高自动机的查询效率提出了前缀路径共享、共享NFA状态表、建立状态转移表、基于DTD语义信息和基于DTD结构信息的五种优化算法。最后对本文构造的自动机及其优化算法进行了性能测试,实验结果表明自动机技术可以有效地处理XML数据流上的海量XPath查询表达式,而且优化算法也可以有效地提高自动机的查询效率。

论文目录

• 摘要
• Abstract
• 引言
• 1 背景知识
• 1.1 XML 的起源
• 1.2 XML 的特点
• 1.3 XML 语言的研究领域
• 1.4 XML 与现有技术的结合
• 1.5 XML 数据流应用的出现
• 1.6 XML 数据流研究现状
• 1.7 本文的主要研究内容
• 2 基础理论
• 2.1 数据库管理系统与数据流管理系统
• 2.1.1 数据流管理系统与数据库管理系统的区别
• 2.1.2 数据流管理系统必须具备的功能
• 2.2 XML 数据流
• 2.2.1 XML 文档及其树型表示
• 2.2.2 XML 数据流
• 2.2.3 XML 数据流处理的特点
• 2.3 XPath 查询语言
• 2.4 文档类型定义DTD
• 2.5 SAX 解析
• 2.6 自动机技术
• 2.6.1 非确定的有穷自动机（nondeterministic finite automaton，简称NFA）
• 2.6.2 确定的有穷自动机（deterministic finite automaton，简称DFA）
• 2.6.3 NFA 转化成等价的DFA
• 3 XML 数据流上的XPath 查询处理
• 3.1 问题描述
• 3.2 解决问题的基本思想
• 3.3 基于自动机技术对XML 数据流上XPath 查询的处理
• 3.3.1 基于非确定性自动机NFA 的XPath 查询处理
• 3.3.2 基于确定性自动机DFA 的XPath 查询处理
• 3.3.3 lazyDFA 技术
• 3.4 查询优化技术
• 4 基于自动机技术的XPath 查询处理的设计与实现
• 4.1 基于非确定性自动机NFA 的查询处理
• 4.1.1 NFA 的数据结构及其实现
• 4.1.2 NFA 的构造
• 4.1.3 NFA 的查询匹配过程
• 4.2 基于惰性确定性自动机lazyDFA 的查询处理
• 4.2.1 DFA 的数据结构及其实现
• 4.2.2 lazyDFA 的构造
• 4.2.3 lazyDFA 的查询匹配过程
• 4.3 lazyDFA 的查询优化算法
• 4.3.1 前缀路径共享
• 4.3.2 共享NFA 状态表
• 4.3.3 建立状态转移表
• 4.3.4 基于DTD 语义信息的优化算法
• 4.3.5 基于DTD 结构信息的优化算法
• 5 实验测试和结果分析
• 5.1 实验环境
• 5.2 测试结果及分析
• 结论
• 参考文献
• 在学研究成果
• 致谢