支持动态更新的XML数据编码方法研究

论文摘要

随着计算机技术和网络技术的迅猛发展,Internet成为全球信息传递和共享的最重要资源,如何利用Internet上的大量信息成为亟待解决的问题。当前,企业和个人通过网络进行数据交换变得越来越频繁,但是由于不同用户采用的数据表示方式不同,因此传统的数据模式不再适合用来表示这些数据,需要一个为大家普遍接受的数据表示方式来对网络数据的交互格式进行统一。此时,XML的出现引起了人们极大的关注,随着网络应用的快速发展,它正在成为Internet上数据表示和交换的事实标准。因此,如何有效地存储和查询XML数据,特别是其中的基于特定编码方法的存储和查询,由于其具有广泛的应用,已经成为XML数据领域中的研究热点问题之一。当前针对XML文档树的编码方法,大致可以分为两大类:基于区间的编码和基于路径的编码。基于区间的编码方法利用XML文档的有序特点,根据每一个元素结点在原XML文档中字典顺序的位置给每一个元素结点赋予一个编码;而基于路径的编码方法则是利用XML文档的嵌套特点,根据XML文档的嵌套结构,给从文档跟结点开始所能达到的每个路径和元素结点赋予一个编码。目前提出的XML数据编码方法对XML文档树的动态更新都不能提供很好的支持,本文就此进行了相关方面的研究。本文在分析比较了现有的XML数据编码方法后,提出了一种新的支持动态更新的XML数据编码方法。该编码方法能够快速准确的判断XML文档结构树中任意两个结点之间的父子、祖先/后裔以及兄弟关系,并采用可变扩展序号支持XML文档的动态更新,可有效降低XML文档的二次编码率。本文的主要工作如下:(1)对现有的区间编码、前缀编码、位向量编码和二叉树编码进行了深入的比较分析,指出了现有编码方法不能很好地支持XML文档树动态更新的不足;(2)提出了一种支持更新的XML文档编码方法,该方法在兄弟结点之间采用了扩展序号;层次较高的兄弟结点之间预留了较多的扩展序号;为每个结点保存了序号的增量,从而更好地支持了XML文档的更新。随着XML文档更新次数的增加,二次编码率将得到明显的降低;(3)详细介绍了编码过程并给出了该编码方法的实现算法;对编码的特性进行了详细介绍,给出了编码更新算法,并结合实例分类讨论了插入结点后编码的更新情况;(4)通过实验,将本文编码方法与已有编码方法进行了时间性能、空间性能、二次编码率及查询性能等方面的比较分析。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景
• 1.2 国内外研究现状
• 1.3 本文的工作
• 1.4 本文的组织结构
• 第二章 XML数据索引综述
• 2.1 索引策略
• 2.2 XML数据索引分类
• 2.2.1 结点记录类索引
• 2.2.2 结构摘要类索引
• 2.3 结点记录类XML数据索引
• 2.3.1 结点序号类索引
• 2.3.2 结点路径类索引
• 2.3.3 两种索引机制的比较
• 2.4 结构摘要类XML数据索引
• 第三章 XML文档编码方法研究
• 3.1 区间编码方法
• 3.1.1 Dietz编码
• 3.1.2 Li2Moon编码
• 3.1.3 Zhang编码
• 3.1.4 Wan编码
• 3.2 前缀编码方法
• 3.2.1 Dewey编码
• 3.2.2 前缀字符编码
• 3.3 位向量编码
• 3.4 二叉树编码
• 第四章 支持更新的XML编码方法
• 4.1 XML文档树的定义
• 4.2 编码方法及算法
• 4.3 编码结点关系判断
• 4.3.1 父子关系判断
• 4.3.2 祖先/后裔关系判断
• 4.3.3 兄弟关系判断
• 4.4 编码优点
• 4.5 编码更新算法及实例
• 4.5.1 编码更新算法
• 4.5.2 编码更新实例
• 4.6 实验结果和性能分析
• 4.6.1 时间性能分析
• 4.6.2 空间性能分析
• 4.6.3 二次编码率分析
• 4.6.4 查询性能分析
• 第五章 总结与展望
• 参考文献
• 致谢
• 攻读学位期间发表的学术论文
• 攻读学位期间参加的工作
• 学位论文评阅及答辩情况表