标签劣质的XML数据上的查询处理

摘要

随着各组织间数据交换的与日俱增，作为Web上数据存储和交换格式事实标准的XML变得越来越重要，但是不正确数据、不一致数据、不精确数据等XML中的劣质数据给XML上的有效查询处理带来了挑战。研究在包含劣质数据的XML上直接进行查询，对 XML的研究与推广具有重要意义。由于twig查询具有重要的研究意义，针对劣质标签，本文研究标签劣质XML数据上twig查询的处理算法及其优化算法。
　　利用XML的内容与结构信息，本文提出了标签劣质XML数据上的查询处理算法。为了对文档实施必要的预处理以支持查询处理算法的高效执行，本文将整个查询处理算法划分为线下的文档处理和线上的查询处理。本文的算法首先利用文档和查询中标签的内容以及文档中各标签间的父子等关系求得每个标签的拼写相近标签、松弛标签、同义标签等相似标签。然后，利用这些相似标签，定义了相似查询及其相似距离，并定义了支持查询处理高效执行的三种操作。利用这三种操作，采用以空间换时间的方式，提出了在XML文档中求出与原查询相似的所有查询结果，并按照与原查询相似程度由大到小的顺序返回结果的高效算法。通过实验验证了该查询算法的有效性和效率。
　　针对上述方法中存在的不够高效之处，本文提出了上述算法的两点优化思想，以及它们的实现方法——文档处理优化和查询处理优化。文档处理优化利用文档处理程序遍历XML文档中所有路径的性质，提前生成文档中所有标签的串联信息；利用该串联信息，查询处理优化对查询中所有标签间的串联关系进行判断，以尽早过滤掉不可能产生结果的标签。本文用了大量的实验验证了这两个优化方法的效率，并对这些实验的结果做了深入的分析。

目录

标签劣质的XML数据上的查询处理

Query Processing on XML Data with Dirty Tags

摘 要

Abstract

目 录

第1章 绪论

1.1 研究背景及研究意义

1.2 国内外研究现状

1.2.1 XML数据上查询处理的研究

1.2.2 劣质数据上查询处理的研究

1.2.3 数据松弛

1.3 本文的主要研究工作

1.4 本文的结构

第2章 标签劣质XML文档的处理方法

2.1 数据表示

2.2 文档处理方法

2.2.1 拼写相近标签的定义及计算

2.2.2 松弛标签的定义及计算

2.2.3 同义标签的定义及计算

2.3 文档处理的效率实验

2.4 本章小结

第3章 标签劣质XML数据上的twig查询处理

3.1 相似查询与相似距离

3.2 合并、串联、连接操作

3.3 标签劣质XML上的twig查询处理算法

3.4 查询处理的效率及有效性实验

3.4.1 τ值固定时人工构造的查询的效率实验

3.4.2 τ值改变时人工构造的查询的效率实验

3.4.3 τ值改变时随机查询的效率实验

3.4.4 查询处理算法的有效性实验

3.5 本章小结

第4章 标签劣质XML数据上twig查询的优化

4.1 引言

4.2 优化方法

4.2.1 文档处理优化

4.2.2 查询处理优化

4.3 标签劣质XML上twig查询优化方法的效率实验

4.3.1 预处理与τ值固定时查询的效率对比实验

4.3.2 τ值固定时人工构造的查询的效率实验

4.3.3 τ值改变时人工构造的查询的效率实验

4.3.4 τ值改变时随机查询的效率实验

4.4 本章小结

结 论

参考文献

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

哈尔滨工业大学硕士学位论文原创性声明

哈尔滨工业大学硕士学位论文使用授权书

致 谢