在XML数据流上的模式树匹配查询

摘要

XML以其强大的数据表达能力,事实上已经成为Internet上数据表示和交换的标准.有些XML数据只能以数据流的形式访问.所以,如何设计XML数据流查询算法,如何利用XML的文档结构来提高数据流查询的时间空间效率已成为一个重要的课题.该文就此研究和分析在XML数据流上的模式树查询匹配,并提出一个XML数据流的模式树查询系统.该系统中有三个关键算法:XML数据流编码算法、Streaming Twig Join算法和Delta Path Join算法.XML数据流编码算法改进了原有的XML元素的三元组编码方案,并提出了基于SAX事件回调机制的编码算法.Streaming Twig Join算法是对Holistic Twig Join算法在数据流处理下的改进,并能生成以路径为单位的查询匹配结果.Delta Path Join算法能以递增的方式生成最终的模式树查询匹配结果.实验证明该文所提出的XML数据流查询系统有较高的查询效率.

目录

摘要

Abstract

第一章绪论

1.1XML基础

1.2 XML和XPath

1.3 XML解析器

1.3.1 DOM

1.3.2 SAX

1.4 XML和半结构化数据

1.5 XML数据流查询现状

1.6本文剩余部分内容安排

第二章背景和相关工作

2.1模式树匹配

2.2 XML数据模型和编码方案

2.3结构化连接算法

2.4 XML索引

第三章XML数据流查询系统概述

3.1 XML数据流查询分析

3.1.1 XML数据流查询结果

3.1.2数据流的数据缓存

3.2查询框架

3.3四个数据(流)

第四章XML数据流编码方案

4.1三元组编码的问题

4.2 XML数据流的编码方案

4.3 XML数据流编码算法

4.3.1简单SAX解析器

4.3.2简要编码算法

第五章Streaming Twig Join算法

5.1Twig Join算法有关的数据结构

5.2 Twig Join算法

5.2.1 GetNext方法

5.2.2 TwigStack方法

5.3 Streaming Twig Join算法有关的数据结构

5.4 Streaming Twig Join算法

5.4.1 StreamingGetNext方法

5.4.2 StreamingTwigStack方法

5.5 Streaming Twig Join算法分析

5.5.1选择性缓存

5.5.2及时产生查询结果

第六章 Delta Path Join算法

6.1 Delta Path Join算法数据模型

6.2 Delta Path Join算法

第七章实现与理论评估

7.1调度规则

7.2与基于自动机的流处理系统的比较

第八章实验结果与分析

8.1实验设置

8.2真实的数据集

8.2.1时间效率

8.2.2内存需求

8.3人工的数据集

总结与展望

参考文献

致谢

论文独创性声明及论文使用授权声明