一种基于后缀树的时态XML索引研究

摘要

可扩展标识语言XML(Extensible Markup Language)由于具有简单、可扩展、互操作性强、开放性强等特点，正迅速成为一种与平台无关的数据交换的标准和传输格式。目前Web应用的支撑技术大多局限于静态和快照式，但XML文档本身的结构和内容随着时间的流逝不断变化，为了使XML文档能记录一系列修改痕迹、能够表达与时间相关的数据、跟踪历史信息和恢复文档在任意历史时刻的状态，XML文档引入了“时态信息”，称之为时态XML(Temporal XML)。时态XML的出现是Web应用和数据库技术发展的必然产物，在这样的应用背景下，如何在XML文档中表达时间相关的数据，跟踪历史信息和恢复文档在任意时刻的状态的研究受到越来越多的关注，但目前在时态XML索引方面所做的工作大都无法适用于大的时态XML文档，一些索引方法的空间代价较高且查询效率不高。
　　 为了解决当前流行的时态XML索引模型空间代价高、查询大时态XML文档效率低的问题，本文提出了基于后缀树的索引模型---TXSIM，该模型分为三部分：后缀索引树、节点编码表、聚合节点链，主要思想是：首先对时态XML文档节点进行编码，存储在节点编码表中，同时把时态XML文档转化成等价的OEM树；再根据OEM树生成具有聚合节点的后缀索引树，并生成聚合节点链。后缀索引树用于时态路径的查询，聚合节点链用于时态值的查询。经实验验证，TXSIM索引模型具有较高的索引空间比，对复杂结构的时态XML文档具有较高的查询效率，并且维护代价低。
　　 本文首先介绍了XNIL及TXML模型、时态数据库、后缀树(Suffix Tree)及半结构化数据模型(OEM)，然后分析当前流行的几种索引方案并比较它们的优缺点：分析当前流行的编码方案并提出了基于素数和序列的编码方法，这种编码方法有空间占用少、维护效率高的特点：接着提出基于后缀树的时态XML索引模型一-TXSIM;最后，本文给出了TXSIM模型的更新、修改、删除的算法，并用实验证明该索引模型的有效性和可行性。

目录

文摘

英文文摘

TABLE OF CONTENTS

第一章 绪论

1.1 研究背景

1.2 国内外研究现状

1.2.1 非时态XML索引研究现状

1.2.2 时态XML索引研究现状

1.3 本文的主要工作

1.4 本文的组织结构

第二章 时态XML及编码方法

2.1 时态XML的相关概念

2.1.1 XML模型和XPath查询

2.1.2 时态XML模型和TXPath

2.1.3 时态数据库

2.2 基于素数和序列的编码方法

2.2.1 节点编码的研究现状

2.2.2 基于素数和序列的编码方法

2.2.3 编码维护方法

2.2.4 编码的效率分析

本章小结

第三章 TXSIM索引模型

3.1 节点编码表

3.2 后缀索引树

3.3 聚合节点时态排序

本章小结

第四章 TXSIM的查询、更新与实验

4.1 TXSIM索引模型的查询

4.1.1 基于时态的路径查询

4.1.2 基于时态的值查询

4.2 TXSIM索引模型的更新

4.2.1 TXSIM插入操作

4.2.2 TXSIM删除操作

4.3 实验及总结

4.3.1 TXSIM的索引空间比

4.3.2 TXSIM的查询

4.3.3 TXSIM的更新

本章小结

第五章 结束语

5.1 总结

5.2 展望

参考文献

致谢

攻读学位期间发表的学术论文目录

学位论文评阅及答辩情况表