发布/订阅系统中基于树自动机的XML查询技术研究

摘要

近年来,互联网技术的迅速发展和广泛应用极大地改变了分布式系统的规模。大型的分布式系统可以扩展至数百万节点,使得传统的同步紧耦合通信模型已不能满足需求。发布／订阅通信模型在时间、空间、控制流等方面完全解耦,很好地适应了大规模分布式系统的通信要求,因此成为大规模分布式环境下广泛使用的通信模型。
　　 在发布／订阅通信模型中,基于XML的发布／订阅通信模型由于其灵活性及强大的表达能力,近年来得到了学术界和工业界越来越多的关注和研究。本文以XML作为事件模型,以XPath(XML Path Language)作为订阅模型,以树自动机理论为指导,提出一种基于树自动机的XML查询技术XTAFilter(XML Filtering based on Tree Automata)来处理XML数据流的查询,并根据树自动机的特点对XML查询进行优化,进一步提高XTAFilter技术的性能。其主要工作如下:
　　 1)通过对树自动机理论的研究,依据树模式思想给出XPath与树自动机的转换算法,并基于树自动机导航实现对XML查询。
　　 2)提出一种基于树自动机的XML查询技术XTAFilter。该技术基于XPath与树自动机的转换算法,通过结构匹配和内容匹配两方面实现对XML查询,并采用hash表来存储谓词信息的方法以提高XML查询效率。
　　 3)提出一种基于树自动机的XML查询优化算法。该算法通过合并用户提交的多个订购表达式中相同的路径片段,构建共享路径树自动机,进一步提高XTAFilter技术的性能。
　　 4)搭建原型系统,给出系统架构及主要功能模块,并基于原型系统进行仿真实验。实验结果表明,基于树自动机的XML查询及优化技术减少了XML查询的匹配转发次数,提高了XML查询的效率和系统的性能。

目录

文摘

英文文摘

图片目录

图表目录

第一章 绪论

1.1 研究背景

1.2 研究目标与研究方法

1.3 主要工作

1.4 论文内容安排

第二章 发布/订阅系统的相关技术及研究现状

2.1 发布/订阅系统

2.1.1 概念模型

2.1.2 关键技术

2.1.3 主要特征

2.1.4 拓扑结构

2.2 研究现状

2.2.1 数据模型

2.2.2 匹配技术

2.2.3 路由协议

2.3 存在问题及分析

2.4 本章小结

第三章 基于树自动机的XML查询技术

3.1 问题的背景

3.2 技术路线概述

3.3 基础知识准备

3.1.1 XML

3.1.2 事件流

3.1.3 XPath

3.1.4 树自动机

3.4 模型描述

3.5 算法描述

3.6 简单实例

3.7 本章小结

第四章 基于树自动机的XML查询优化

4.1 问题的提出

4.2 传统算法比较

4.3 基于树自动机的XML查询优化算法

4.4 性能分析

4.5 本章小结

第五章 系统原型与仿真实现

5.1 系统原型

5.1.1 系统体系构架

5.1.2 系统功能模块

5.1.3 系统拓扑结构

5.2 仿真实验

5.2.1 实验过程

5.2.2 实验结果与分析

5.3 本章小结

第六章 总结与展望

6.1 总结

6.2 展望

参考文献

致谢

攻读硕士学位期间发表的论文