基于文档属性单元扩展的XML近似查询方法的研究

摘要

随着Internet技术的发展,越来越多的应用采用XML语言作为信息表示和数据交换的标准,人们对于XML数据查询技术的要求也越来越高。传统的XML查询技术对查询条件进行精确的匹配,无法反映查询者对于XML数据内容在语义上的近似要求。因此,近似查询技术被应用到了XML查询当中。由于XML文档是半结构化的数据表示形式,基于内容的XML近似查询就要在满足文档结构要求的基础上,考察内容的近似性。已有的基于内容的XML近似查询技术,从根本上讲都是把元素聚类或映射到相似语义单元中,然后构造语义模型进行近似查询。这些方法在实现上要求构造语义模型,构造过程中会带来元素的类别划分不准或者语义丢失等问题,查询代价也不容忽视。因此需要找到一种不必建立语义模型的近似查询方法。
　　 本文提出了一种基于文档属性单元扩展的XML近似查询方法。该方法提取出XML文档中的叶子结点和属性结点作为属性单元,根据属性单元的重要程度序列,对初始的查询条件扩展,利用新的查询条件对原来的XML文档进行查询。整个近似查询方法主要分成三部分:
　　 首先,在提取出的XML文档属性单元中,利用一种高效发现函数依赖关系算法,找到属性单元之间的近似函数依赖关系,根据属性单元在函数依赖关系中出现的左右部位置,求得近似候选码。选择支持度最大的候选码作为近似关键字,组成近似关键字的所有属性单元成为决定集的成员,剩下的属性单元成为依赖集的成员。
　　 然后,根据近似候选码对依赖集中属性单元的支持度,计算出每个属性单元的重要性权重,排出属性单元重要程度序列。根据排出的属性单元序列,先扩展依赖集中的属性单元,最后扩展决定集中的属性单元,保证最不重要的属性单元先扩展。
　　 最后,根据扩展后新的查询条件,对XML文档重新查询,返回结果。由于利用了XML文档数据自身的函数依赖关系,扩展后的查询会将满足核心查询条件的结果排在最前。
　　 实验测试表明,属性单元扩展的近似查询方法能够在满足查询者对文档内容的近似要求,同时在召回率和排序稳定性上也取得了较好的效果。

目录

文摘

英文文摘

第1章 绪论

1.1 研究背景

1.2 研究目的及意义

1.3 相关研究工作

1.3.1 XML结构连接查询

1.3.2 XML近似查询

1.4 本文所做工作

1.5 文章组织结构

第2章 相关理论基础

2.1 XML及其相关标准

2.1.1 XML文档及DTD

2.1.2 编码方案

2.1.3 XPath简介

2.2 XML查询技术

2.2.1 XML查询的分解

2.2.2 Twig模式结构连接算法

2.3 属性单元近似函数依赖

2.3.1 属性单元函数依赖关系

2.3.2 最小近似函数依赖

2.4 本章小结

第3章 XML文档属性单元排序方法

3.1 文档属性单元纪录

3.2 近似函数依赖关系的提取

3.2.1 数据集的带状划分

3.2.2 一致集的计算

3.2.3 最大集及其补集的计算

3.2.4 近似函数依赖左部的计算

3.3 近似候选码的求解

3.4 属性单元重要性程度排序算法

3.5 查询条件扩展程度预处理

3.6 本章小结

第4章 XML近似查询算法的设计

4.1 属性单元提取过程

4.1.1 XML简单API(SAX)

4.1.2 SAX中的重要接口和类介绍

4.1.3 XML属性单元提取过程

4.2 XML Twig模式查询算法

4.2.1 Twig问题描述

4.2.2 PathStack算法介绍

4.2.3 TwigStack算法介绍

4.3 XML扩展查询TwigAE算法

4.4 本章小结

第5章 实验测试与分析

5.1 测试平台及测试集

5.1.1 测试平台

5.1.2 实验数据

5.2 属性单元扩展过程性能测试

5.3 TwigAE算法性能测试

5.3.1 TwigAE算法与TwigStack算法结果对比

5.3.2 TwigAE算法召回率和精确率

5.3.3 文档大小对TwigAE算法性能影响

5.3.4 相似度对TwigAE算法召回率和精确率的影响

5.4 实验结论

5.5 本章小结

第6章 总结与展望

6.1 总结

6.2 展望

参考文献

致谢