XML查询的并行算法研究

论文摘要

近年来,XML(Extensible Markup Language)己经成为互联网上数据发布和数据交换的事实标准。受到越来越多的关注。各行各业都在采用XML来描述本领域的信息,随着XML的普及,人们对XML文档查询的要求会越来越高。因此如何提高查询时的效率成了一个亟待解决的问题。虽然XML查询技术已经取得一些研究成果,但由于XML文档自身的特点,以及它与传统数据模型的差异,XML查询技术在理论上和实现上都还存在很多难点。本文对XML查询技术进行深入研究,对XML数据查询算法研究现状、发展以及应用进行了分析和总结,详细分析了XML查询技术;研究XML数据库的发展、功能、结构、特点和主流技术,包括传统关系型数据库的XML扩展和纯XML数据库;分析XML文档在数据库中的存储方式,提出混合型XML存储结构,支持结构化和非结构化双向转换,提高XML文档的操作效率。目前已经提出了多种查询XML数据的方法,然而随着多处理器系统和多核心处理器系统的流行,传统的XML查询方法不能充分利用多处理器和多核心处理器的优势。本文详细阐述了并行计算理论,并行计算机系统的体系结构,并根据并行计算理论和XML查询技术,设计采用分治范例和工作池相结合的并行范例。选取XML处理模型,设计并行粒度,构造并行性,提出基于树匹配算法的XML数据并行查询算法,大幅提高了共享存储器多处理器、多核心处理器系统中XML数据的查询效率,并进行性能分析。

论文目录

• 摘要
• ABSTRACT
• 第1章 绪论
• 1.1 课题背景及来源
• 1.2 本领域发展概况
• 1.3 本文研究内容
• 第2章 XML及其相关技术
• 2.1 XML 简介
• 2.2 DTD
• 2.3 XQUERY
• 2.3.1 XQuery 的模块结构
• 2.3.2 路径表达式（Path Expression）
• 2.3.3 算术表达式与布尔表达式（Arithmetic and boolean expression）
• 2.3.4 FLWR 表达式
• 2.3.5 条件表达式（Conditional Expression）
• 2.3.6 元素构造器（Element Constructor）
• 2.3.7 函数调用（Function Call）
• 2.4 本章小结
• 第3章 XML数据库
• 3.1 XML 数据库简介
• 3.2 传统关系型数据库的XML 扩展
• 3.2.1 Oracle XML DB
• 3.2.2 IBM D82 XML Extender
• 3.3 纯XML 数据库
• 3.4 XML 文档在数据库中的存储
• 3.4.1 当前数据库的XML 文档存储方式
• 3.4.2 混合型XML 存储结构
• 3.5 XML 数据库的未来
• 3.5.1 网格计算（Grid Computing）
• 3.5.2 更便捷、面向更大数据规模的自动内存管理
• 3.6 本章小结
• 第4章 共享存储器下的XML 并行算法
• 4.1 并行算法的目标和分类
• 4.1.1 并行算法的目标
• 4.1.2 并行算法的分类
• 4.2 并行模型
• 4.2.1 共享存储器多处理机模型
• 4.2.2 其它并行模型
• 4.3 并行编程模型
• 4.3.1 共享变量模型
• 4.3.2 其它并行编程模型
• 4.4 并行范例
• 4.5 本章小结
• 第5章 算法设计及实验结果分析
• 5.1 软件开发环境
• 5.2 XML 处理模型
• 5.3 树匹配算法
• 5.3.1 整树匹配算法
• 5.3.2 查询树匹配算法
• 5.4 并行粒度设计
• 5.5 并行性的构造
• 5.6 算法流程
• 5.7 试验结果分析
• 5.8 本章小结
• 结论
• 参考文献
• 攻读学位期间发表的学术论文
• 致谢