一种XML数据流查询过滤算法

摘要

近年来，XML数据流的查询处理引起了国内外学者的广泛兴趣。如何在XML数据流中有效地查询大量XPath表达式是当今研究的一个热点问题。目前，已经提出很多种在XML文档上进行XPath查询的方法，其中大部分是采用基于自动机的查询方法，它又可分为基于不确定有穷自动机(NonDeterministic FiniteAutomata)和基于确定有穷自动机(Deterministic Finite Automata)两种。除此之外，还有基于索引的以及基于谓词的查询方法。
　　对于NFA中的一个状态，同一个输入下可能发生很多个状态转移，为了查找下一个指定的状态需要花费很长的时间。然而对于DFA中的一个状态而言，同一个输入下发生了确定的状态转移，但是随着XPath查询表达式数目的增加，自动机的状态数会迅速增加，这样需要占用很多的存储空间。
　　本文对XML数据流查询处理中所存在的问题进行了比较详尽的研究，针对目前存在的XML文档处理方法的不足，构建了一种索引结构，在索引结构的基础上又提出了一种查询算法。本文的主要工作如下:
　　(1)构建了一种新颖的索引机制---XML文档的索引结构。首先从给定的XML文档中提取出文档结构，然后根据文档结构建立一个个索引节点，组成文档的索引结构。
　　(2)利用所构造的文档的索引结构，对给定的一系列XPath查询表达式进行预处理。将与索引节点匹配的查询表达式标注于对应索引节点的谓词列表框内。
　　(3)提出了一种解决线性路径查询的算法LXPF。
　　(4)通过实验将本文提出的算法跟以往所提出的算法进行比较，结果表明其有效性。

目录

摘要

第一章 绪论

1．1 研究背景与国内外研究现状

1．2 本文主要工作

1．3 本文组织结构

第二章 背景知识

2．1 XML文档与XML文档树

2．2 XML数据流

2．3 XML规范

2．3．1 文档类型定义DTD

2．3．2 XML模式XMLSchema

2．3．3 文档对象模型DOM

2．3．4 XML解析简单应用程序接口SAX

2．4 本章小结

第三章 基于XML数据流的XPath查询

3．1 XML数据流查询模型

3．2 XPath表达式

3．3 SAX解析

3．4 文档索引结构

3．4．1 XML文档结构

3．4．2 文档索引结构

3．5 本章小结

第四章 一种XML数据流查询过滤算法

4．1 线性XPath的查询过滤算法LXPF

4．2 查询更新

4．3 嵌套路径查询

4．4 算法分析

4．4．1 时间复杂度

4．4．2 空间复杂度

4．5 实验结果及性能分析

4．5．1 实验环境与数据

4．5．2 性能分析

4．6 本章小结

第五章 总结与展望

参考文献

攻读学位期间取得的研究成果

致谢

个人简况及联系方式

声明