基于结构摘要思想的时态XML索引方案

论文摘要

随着网络和信息技术的发展,XML(Extensible Markup Language)已逐步成为互联网上数据表示和数据交换的一种新的标准。可以预见,将来XML会成为Web信息交换的统一标准。通常,随着时间推移,我们会对XML文档进行一些修改。之后,我们希望快速对文档历史信息进行查询。在这样的应用背景下,如何在XML文档中表达时间相关的数据,跟踪历史信息,和恢复文档在以前任意时刻的状态的研究中受到越来越多的关注。对XML(包括时态XML和非时态XML)数据建立有效的索引,是左右XML数据处理性能的重要因素。在非时态XML索引研究领域,研究成果较多,索引总体上可以分为节点记录类索引和结构摘要类索引。而时态XML索引的研究才刚刚开始。虽然一些文献提出模型和索引算法,但大多基于对版本信息的维护,尤其对于版本间数据查询处理效率较低。同时,由于时态XML文档中包含时间信息,文档更新较为复杂,这就对索引更新提出了更高的要求。重新建立索引结构,重新对节点编码将严重影响索引的效率。本文针对时态XML文档特点,提出一种新的时态XML索引方案,TF&B索引。从索引结构、查询算法和更新维护算法三个方面对该索引进行介绍。本文的主要工作在于:1.论文对TF&B索引的结构进行详细介绍,给出了构建算法。2.论文根据时态XML查询表达式的特点,将其分为四大类进行算法研究,最后给出查询比较的实验数据。通过分析比较,证明了该索引具有较好的性能。3.论文从时态XML文档片段增加、删除和更新方面,对TF&B索引的更新算法进行讨论。本文工作的意义是给出了有效索引时态XML文档的一套完整方案,具体体现在以下方面:在时态XML文档模型设计上,本文采用的模型只保存不同时刻节点之间的关联关系,而不是保存某些时刻的快照,从而解决了分散在不同版本间的数据查询问题。在节点编码设计上,本文采用预留编码空间的方法,使得文档更新时,不需进行重新编码。在查询算法设计上,通过等价类划分和聚簇存储,减少了树遍历和磁盘读取次数。在维护算法设计上,使用增量更新的方式,避免了文档更新时索引的重建。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 课题研究背景
• 1.1.1 XML文档图和XPath查询
• 1.1.2 时态XML文档
• 1.1.3 TXPath
• 1.2 XML索引研究现状
• 1.2.1 非时态XML索引研究现状
• 1.2.2 时态XML索引研究现状
• 1.3 本文的主要工作
• 1.4 本文的组织结构
• 第二章 TF&B索引模型结构
• 2.1 时态XML模型
• 2.1.1 扩展的前序编码
• 2.1.2 预留因子
• 2.1.3 时态XML文档模型编码
• 2.2 TF&B索引模型结构
• 2.2.1 索引图GTF&B
• 2.2.2 磁盘结构
• 2.2.3 PT表和T表
• 第三章 TF&B索引查询算法
• 3.1 简单路径查询
• 3.2 包含//操作符的路径查询
• 3.3 包含非时间谓词的路径查询
• 3.4 包含时态谓词的路径查询
• 3.5 实验
• 第四章 TF&B索引维护
• 4.1 增加文档片段下的TF&B索引维护
• 4.2 删除文档片段下的TF&B索引维护
• 4.3 更新文档下的TF&B索引维护
• 第五章 结束语
• 参考文献
• 致谢
• 攻读学位期间发表的学术论文目录
• 攻读学位期间参与科研项目情况
• 学位论文评阅及答辩情况表