对大信息量XML文档查询方法的研究

摘要

Web技术的飞速发展使得全球信息的传递和共享日益增多,而XML技术的出现则正是为了有效应对上述问题。XML己经逐渐成为Internet上数据的表示标准和交换工具,它为数据库的应用开辟了一个崭新的领域,然而由于XML数据的半结构化特性以及XML数据所特有的路径表达式查询方式不同于现有的关系数据库查询,使得关系数据库系统对XML数据的管理功能受到极大限制。XML数据的一个明显特征是其数据冗余较大,无论采用那种模式来存储XML数据,都必须面对XML数据冗余较大这一特点。冗余既造成了存储空间的浪费,又增加了查询处理的I/O时间,从而降低了效率。目前,减小XML文档大小的一种有效的方法就是压缩,但是压缩后的XML文档需要解压后才能对其进行验证、查询等操作,这在某些应用中时间或者空间代价过高(如手持设备或者接收压缩XML文档的服务器等),所以如何在有效压缩XML文档的同时能够在压缩后的文档上进行查询等操作就成为基于XML的数据交换中需要解决的一个问题。针对XML数据的半结构化特征,本文考虑分别从XML的文本和结构特征上来消除冗余数据。对XML文本的冗余,结合了BWT方法,并用实验说明了它对于压缩后的文本查询的高效性。针对XML文档的结构特征,分析了当前结构连接的不足,提出并证明了基于双亲-孩子关系和祖先-后裔关系的连接表达式中,存在重复的结构连接路径。提出了ESL方法,通过该法,得到的结构索引比原始数据明显要小的多。最后,本文提出了处理XML查询的一个模型,其中的压缩模块用的就是上述技术,并对实现该模型作了初步的探讨。

目录

摘要

Abstract

1 绪论

1.1 选题背景与意义

1.2 国内外研究现状

1.3 论文结构组织

2 背景知识

2.1 数据压缩及发展现状

2.1.1 模型

2.1.2 编码

2.2 XML 概述

2.2.1 XML 内容

2.2.2 XML 的特点和应用范围

2.3 本章小节

3 压缩文本搜索

3.1 全文文本压缩技术

3.2 BWT 技术

3.2.1 BWT 轮换

3.2.2 辅助数组

3.3 算术编码

3.4 Boyer-Moore 算法

3.5 BWT-Boyer-Moore 压缩域搜索算法

3.6 本章小节

4 XML 模型和查询方法

4.1 XML 模型

4.1.1 OEM 模型

4.1.2 DOM 模型

4.1.3 XML 文档类型定义

4.2 XML 查询技术

4.2.1 Xquery

4.2.2 Xpath

4.3 XML 查询方法

4.4 本章小节

5 基于 XML 的索引技术

5.1 一种改进的路径索引

5.1.1 路径查找算法

5.1.2 利用高频路径产生索引机制

5.1.3 扩展的倒排文档

5.2 一种高效的结构连接方法

5.2.1 XML 数据模型及数据模式

5.2.2 结构索引

5.2.3 倒排表

5.2.4 结构连接算法

5.2.5 连接路径表达式

5.3 本章小节

6 基于 XML 压缩文档的查询

6.1 XML 压缩文档研究现状

6.1.1 几种压缩工具的比较

6.2 基于 XML 文档的一种查询模型

6.3 本章小节

7 结束语

致谢

参考文献

附录

攻读硕士学位期间发表的论文情况