多版本XML文档的查询处理

论文摘要

XML文件版本管理最主要的目的在于有效存储连续修改的XML文件,减少存储的成本,并且能快速地获取之前的XML文件版本和提供复杂查询的功能。本文利用时间性与空间性的概念,针对XML文件,给予XML树状结构上的每个节点位置编码、层号值和版本值。根据版本值,可以直接地获取之前的XML文件版本,并且利用位置编码和层号值来维护节点之间的结构关系。 本文首先设计了新的节点编码方案和索引机制,给出管理多版本XML的解决方案,此方案允许直接取出某版本,不需要往前或往后推算。针对结构化连接,设计新的四元组索引结构。然后对结构化连接算法进行了深入的分析和研究,重点改进了Stack-Tree-Desc连接算法,在原有的基础上增加了版本信息,达到支持多版本查询的目的。最后研究了XQuery语言。讨论了XML查询数据模型,并在语义上进行扩充,使之支持多版本XML文档查询。 查询问题是XML研究中急待解决的重要共性问题。结构化连接是XML查询处理的核心操作,目前已经提出了许多结构化连接的算法,但都不支持多版本的XML文档。本文深入研究结构化连接算法,并且进行扩充,使之支持多版本的XML文档。使用新的编码方案和扩展后的算法实现了对多版本XML文档的直接查询。

论文目录

• 引言
• 第一章 绪论
• 1.1 课题背景及来源
• 1.2 国内外研究现状
• 1.2.1 国外现状及技术发展趋势
• 1.2.2 国内相关技术发展水平、现状
• 1.3 本文研究内容和目标
• 1.4 本文的组织结构
• 第二章 XML查询处理相关研究
• 2.1 XML标准体系
• 2.2 XML查询语言
• 2.2.1 XML查询的特点
• 2.2.1.1 XML查询与关系查询
• 2.2.1.2 XML查询与文本查询
• 2.2.2 XML查询语言的发展
• 2.3 XML查询研究现状
• 2.4 XML文件版本管理
• 2.5 查询处理核心操作——结构化连接
• 2.6 本章小结
• 第三章 XML文档版本控制和索引模式设计
• 3.1 XML版本管理现有方法及其不足
• 3.1.1 UBCC版本管理机制
• 3.1.2 页的有效性（PAGE USEFULNESS）
• 3.1.3 变化检测
• 3.1.4 管理 DELTAS
• 3.1.5 问题和不足
• 3.2 XML文件节点编码方案
• 3.2.1 节点编码
• 3.2.2 节点编码的优点
• 3.3 数据模型及索引结构
• 3.3.1 XML文档树数据模型
• 3.3.2 索引结构及其特点
• 3.4 XML版本管理解决方案
• 3.4.1 XML文档的版本机制
• 3.4.2 存储结构及版本获取
• 3.5 本章小结
• 第四章 XML文件版本的查询处理
• 4.1 模式匹配
• 4.1.1 模式树
• 4.1.2 查询代数树
• 4.1.3 模式匹配定义
• 4.1.4 模式树匹配
• 4.2 基于结构化连接的匹配方法
• 4.3 多版本结构化连接方法
• 4.3.1 结构化连接定义
• 4.3.2 基于栈的结构化连接基本结构
• 4.3.3 算法描述
• 4.3.4 算法正确性证明及时空复杂度分析
• 4.4 XML版本查询处理
• 4.5 实验结果及分析
• 4.5.1 实验环境
• 4.5.2 查询操作框架
• 4.5.3 实验结果及分析
• 4.6 本章小结
• 第五章 XML查询语言的扩展
• 5.1 XML数据模型
• 5.1.1 XQuERY数据模型
• 5.1.2 XQuERY查询处理过程
• 5.2 XQUERY语义扩展
• 5.2.1 类型扩展
• 5.2.2 函数扩展
• 5.3 XQUERY查询示例
• 5.5 本章小结
• 第六章 总结与展望
• 6.1 总结
• 6.2 展望
• 参考文献
• 攻读硕士学位期间公开发表的论文
• 致谢