基于更新标识符的改进分数编码方案研究

摘要

目前，XML已经成为Web数据存储、表示和交换的重要标准。XML具有良好的可拓展性与开放性、较高的压缩比、能够保证数据的结构完整性等诸多优点，但同时它也存在冗余信息多、分支结构多等缺点。如何高效管理XML数据成为XML技术领域的研究热点，为此学者们提出了很多特定的编码方案。这些数据编码方案在很大程度上提高了XML数据的编码和管理效率，但也存在一些不足，比如查询效率不高，当XML数据频繁或者大幅度更新时需要重新编码、更新代价较大。本文就此开展相关方面的研究。
　　本文在深入分析已有编码方案的基础上，提出了一种基于更新标识符的改进分数编码方法UIFES，该编码将结点信息和路径信息分解，分别保存在不同的表中，避免记录重复的结点信息和路径信息，节省了存储空间;同时该编码将所有的结点路径保存在路径信息表中，在查询时通过路径编号来查找结点位置，避免了现有查询算法的结构连接操作，而且不受查询路径表达式长度和中间结果集规模的影响，大大提高了查询效率;最后该编码利用分数界定码和更新标志码来解决预留空间用完的情况，使得在某些特殊情况下都不需要重新编码，更新代价很小，极大地提高了编码的更新效率。
　　总结来说，本文的主要工作如下:
　　(1)深入分析了现有的XML数据编码方案，并指出了这些编码方案各自的优缺点。
　　(2)提出了一种新的XML数据编码方案，即UIFES编码。该编码综合运用了分数编码和前缀编码的优点，既能有效支持结点的动态更新，又具有较高的查询效率。与前缀编码相比，它的查询效率更高;与分数编码相比，它的动态更新性能更好。
　　(3)针对本文提出的编码方案详细说明了相关定义和实现算法;对编码的特性进行了介绍，给出了编码更新算法和查询算法，并结合实例讨论了插入新结点后编码的更新情况，详细说明了查询过程。
　　(4)通过实验对UIFES编码和其它对照组编码在静态编码效率、动态更新效率、查询效率等方面进行了分析和比较，验证了UIFES编码的有效性。
　　实验结果证明，与现有的编码方案相比，UIFES编码在静态编码效率、动态更新效率和查询效率方面都具有较大的优势。

目录

摘要

1． 绪论

1．1选题研究背景与意义

1．2 国内外研究现状

1．3 本文主要研究内容

1．4 论文结构与章节安排

2．XML编码方案分析与比较

2．1 XML简介

2．2 区间编码

2．3 前缀编码

2．4 K-分树编码

2．5 支持动态更新的编码

2．6 各种编码方案的分析与比较

2．7 本章小结

3．基于更新标识符的改进分数编码UIFES

3．1 UIFES编码相关定义

3．2 UIFES编码方法及实现算法

3．3 UIFES编码主要创新点

3．4 UIFES编码存储体系

3．5 UIFES编码的结点关系判断

3．6 UIFES编码的动态更新规则与算法

3．7 UIFES编码的查询

3．8 本章小结

4．实验结果与分析

4．1 实验准备

4．2 实验系统流程

4．3 UIFES编码的时间性能

4．4 UIFES编码动态更新性能

4．5 UIFES编码查询性能

4．6 本章小结

5．总结与展望

5．1 论文主要工作总结

5．2 下一步工作及展望

参考文献

致谢

声明