基于元表的XML可查询压缩方法

摘要

随着XML应用的普及，XML成为了信息交换和编码的主流格式和事实标准。日益增长的以XML形式来表示的数据给数据的管理提出了更高的需求，其中，最突出的当属XML自身半结构化、自描述性等特性引发的数据冗余问题。因此，XML数据压缩技术成为解决XML重复结构和重复数据的一种有效途径。
　　 很多应用场合都需要XML查询的处理，但目前大多数XML压缩方法为追求高压缩率，在压缩过程中破坏了XML文档结构与数据项之间的对应关系，导致XML文档压缩后不支持对压缩文档的查询。即使将压缩数据完全解压后也无法恢复原XML文档，也就不能支持查询处理功能，因此，研究XML可查询压缩方法势在必行。
　　 论文以高效处理XML简单路径查询为目标，研究了多种支持XML快速处理导航式路径查询的索引技术，分析了现有索引的优缺点，提出了改进的索引结构更新并予以实现，主要研究内容如下:
　　 首先，针对树形结构索引构造代价过大问题，提出了一种非树形的元表及结构统计表结合的索引结构，该索引创建仅需扫描一次XML文档，构建过程中完成对XML重复路径及重复数据的简化工作，索引创建后的XML文档精简至相同路径下不存在重复标签。
　　 其次，在对目前支持动态更新的数据编码方式进行透彻剖析的基础上，提出一个适合部分元表、结构统计表频繁更新的方案，其更新规则能很好解决节点插入、删除、修改等情况，该方案同时保证原有索引节点结构信息不受影响，降低了索引更新的开销。
　　 最后，针对查询路径过于冗长导致的查询语句合法性验证时间代价过大问题，提出了简单路径优化策略，该策略依据XML文档实际结构特征，将满足条件的路径表达式简化，从而降低数据查询导致的访问索引结构的代价。
　　 实验结果表明，论文给出的支持查询的XML压缩方法可行，且同经典的XML可查询压缩算法XGrind具有可比性。较好满足XML压缩技术中对数据更新、非完全解压数据查询的支持等需求。

目录

封面

声明

摘要

第一章 绪论

1．1 研究背景及意义

1．2 国内外研究现状

1．2．1 不支持查询的XML数据压缩技术

1．2．2 支持查询的XML数据压缩技术

1．3 本文的主要工作和目标

1．4 本文组织结构

第二章 相关技术基础

2．1 XML简介

2．1．1 XML数据模型

2．2 XML数据解析

2．2．1 DOM解析器

2．2．2 SAX解析器

2．3 XML数据索引

2．3．1 基于路径的XML索引

2．3．2 基于结点等价类的XML索引

2．4 XML数据编

2．4．1 区间编码

2．4．2 位向量编码

2．4．3 前缀编码

2．4．4 支持动态插入的编码

2．5 XML查询语言

2．5．1 XPath查询语言

2．5．2 XQuery查询语言

2．6 本章小结

第三章 基于元表的可查询方法

3．1 问题的提出

3．2 基于元表的XML可查询方法

3．2．1 MTQC的结构

3．2．2 MTQC处理流程

3．3 相关定义

3．3．1 元表的定义

3．3．2 结构统计表的定义

3．3．3 元表、结构统计表的构建

3．4 数据压缩处理

3．5 查询处理算法

3．6 实验及性能测试

3．6．1 实验环境及实验数据

3．6．2 实验结果及分析

3．7 本章小结

第四章 基于MTQC的索引局部更新策略

4．1 问题提出

4．2 索引结构更新策略

4．2．1 基本思想

4．2．2 相关数据结构

4．2．3 更新具体实现

4．2．4 XML简单路径表达式优化

4．3 算法理论分析

4．3．1 算法复杂度分析

4．3．2 算法适用性理论分析

4．4 实验及性能测试

4．4．1 实验环境及实验数据

4．4．2 实验结果及分析

4．5 本章小结

第五章 总结及未来工作

5．1 本文总结

5．2 工作展望

致谢

攻硕期间从事的科研工作及取得的研究成果

参考文献