原生XML数据库动态结点编码方案分析与应用的研究

摘要

随着XML相关标准的制定,Internet上出现了大量的XML文档,如何有效地管理和查询这些文档成为一个亟待解决的问题,这一问题的出现极大地促进了XML数据库技术的研究。原生XML数据库(NXD)是专为存储和管理XML文档而提出的,在NXD中的XML文档查询主要包括值查询和结构查询,其中的结构查询是XML查询的一个重要内容。判断结点之间的结构关系的主要思想是将一个复杂的查询模式分解成为若干个二元基本结构关系的集合,首先计算二元基本结构关系,然后将基本的匹配结果组合起来。在这种处理策略下,基本结构关系(包括父子关系和祖先-后代关系)的计算成为查询处理的关键操作,这种操作被称为结构连接(或包含连接)。各种索引的建立可以提高结构连接算法的效率,而XML结点编码可以方便地建立各种索引,所以XML文档结点编码方案的研究引人注目。 本文在对原生XML数据库中动态结点编码方案及其应用进行透彻剖析的基础上,重点对三种动态结点编码方案,即ORDPAYH编码、DeweyIDs编码及DLN编码进行了研究,并用C＃开发了三种编码方案的软件。然后,用十个标准的XML文档测试集对三种编码方案进行测试,根据测试结果对三种动态编码的确定性、动态性和压缩性进行了分析与比较；在此基础上,从理论上进一步对XML动态编码的性能进行了分析比较,着重分析了动态编码的压缩性。对动态编码压缩性理论分析所采用的标准是：编码K个层标识占用的存储空间S,分别对用固定长度、长度域、前缀编码及控制标记等四种方式编码K个层标识占用的存储空间S进行统计,最终归纳出关于S与K的通式。通过一系列研究,进一步验证了动态结点编码在编码时间和空间效率的高效性。最后,对动态编码方案在查询计划和查询处理模型中的应用进行了探讨。

目录

文摘

英文文摘

声明

学位论文的主要创新点

第一章引言

1.1研究背景与意义

1.2国内外研究现状

1.3本文的主要工作及内容安排

第二章XML数据库基础

2.1关于XML

2.1.1 XML简介

2.1.2 XML的特点

2.1.3 XML的应用

2.1.4 XML对整个IT行业的影响

2.1.5 XML获得广泛支持

2.2 XML文档及其格式

2.2.1 XML文档

2.2.2文档类型定义(DTD)

2.2.3 XML Schema简介

2.3相关基础理论

2.3.1 XML文档解析技术

2.3.2 XML查询语言

2.4关于XML数据库

2.4.1 XML数据库的定义

2.4.2 XML数据库的分类

2.4.3原生XML数据库介绍

2.4.4 XML数据库的发展前景

第三章 原生XML数据库动态结点编码

3.1相关XML文档结点编码研究

3.1.1位向量编码

3.1.2前缀编码

3.1.3区间编码

3.1.4二叉树编码

3.2 ORDPATH编码

3.2.1静态ORDPATH编码及其相关算法

3.2.2利用ORDPATH编码实现对XML文档树的动态更新

3.3 DewyIDs编码

3.3.1静态DeweyIDs编码及其相关算法

3.3.2动态DeweyIDs编码及其相关算法

3.4 DLN(Dynamic Level Numbering Schema)编码

3.4.1静态DLN编码及其相关算法

3.4.2动态DLN编码及其相关算法

第四章三种动态结点编码方案的性能分析

4.1理论分析

4.1.1动态结点编码的确定性分析

4.1.2动态结点编码的动态性分析

4.1.3动态结点编码的压缩性分析

4.2实验测试结果及其分析

4.2.1实验数据

4.2.2实验环境搭建

4.2.3动态的ORDPATH编码、DeweyIDs编码及DLN编码实验数据分析及比较

4.3总结

第五章动态结点编码方案的应用

5.1查询计划

5.1.1相关定义

5.1.2 XML查询计划的产生

5.2查询处理方案

5.2.1值查询处理方案

5.2.2结构查询处理方案

5.3结构连接算法

5.3.1祖先/后裔关系连接算法

5.3.2双亲/孩子关系连接算法

5.3.3之前/之后关系连接算法

5.3.4左兄弟/右兄弟关系连接算法

5.4总结

第六章结束语

参考文献

发表论文和参加科研情况说明

致谢