基于实体的XML关键字搜索问题研究

摘要

XML(eXtensible Markup Language)即可扩展标记语言,是W3C定义的一套语义标记规范。随着网络应用的快速发展,Web上的数据成指数级增长,XML逐渐成为Internet上数据交换和描述信息的标准格式,广泛应用于数字图书馆、数据集成、Web服务等领域,这使得XML类型数据成为网络上主流数据形式,从XML数据中提取有用信息成为了当前研究的重要方向。
　　相较于XML结构化查询,XML关键字查询成为XML数据检索的重要分支。XML关键字搜索方法都是以LCA(Lowest Common Ancestor)为基础形成的。为了提高搜索质量和效率,研究人员又提出了许多查询语义,包括SLCA(SmallestLCA),MLCA(Meaningful LCA)、VLCA(Valuable LCA)等。这些查询语义及实现算法在实际应用中可能存在一些问题,如返回无意义结果、丢失有意义信息等。
　　本文考虑到一个XML文档可以看作现实世界中实体、属性、值构成的集合,这与关系数据库中ER模型相似。XML文档中不同元素代表不同信息类型,将XML文档元素进行分类,以实体作为基本查询单元来定义XML关键字搜索的查询语义,提出了最低公共实体祖先LCEA的概念,一个LCEA结点是描述现实世界完整信息单元的实体对象。在LCEA的基础上,提出了最小的最低公共实体祖先SLCEA(Small Lowest Common Entity Ancestor),为用户提供了简单易用搜索方法,解决了返回结果不完全和返回结果无意义的问题。
　　在实体概念的基础上,根据元素之间关系改进了XML关键字搜索方法,使之不仅支持明确查询,而且支持XML关键字模糊查询和高级搜索。首先根据不同实体对查询关键字进行分区,然后过滤实体分区倒排表,最后采用ILE算法计算最小最低共同实体祖先。在输出结果时,根据SLCEA不同情况分别推断出不同的输出信息。对于模糊查询处理,本文的方法能够识别和排序不同的搜索意图,并分别返回每个搜索意图的结果。最后实验验证了本文方法在搜索质量和执行效率方面的性能。

目录

文摘

英文文摘

第一章 绪论

1.1 研究背景与意义

1.2 研究现状

1.2.1 XML结构查询

1.2.2 XML关键字查询

1.3 论文的主要工作

1.4 论文组织结构

第二章 XML文档中实体及查询语义相关概念

2.1 XML文档

2.2 XML文档树

2.3 Dewey编码

2.3.1 前缀编码

2.3.2 Dewey编码

2.4 节点分类

2.5 最紧致片段LCA和SLCA

2.6 LEA和SLCEA

2.7 本章小结

第三章 基于SLCEA的XML关键字搜索方法

3.1 问题描述

3.2 XML数据组织方式

3.2.1 基于实体的Dewey码

3.2.2 数据组织方式

3.2.3 基于实体的索引

3.3 基于实体的XML关键字搜索方法

3.4 LCEA集合的算法

3.5 SLCEA集合的算法

3.6 SLCEA集合算法示例

3.7 算法复杂度分析

3.7.1 时间复杂度分析

3.7.2 空间复杂度分析

3.8 实验评估

3.9 本章小结

第四章 基于元素间关系的XML关键字搜索方法改进

4.1 问题描述

4.2 查询预处理

4.2.1 关键字分区

4.2.2 模糊关键字查询处理

4.2.3 分裂查询排序算法

4.3 倒排表过滤

4.4 SLCEA的计算

4.5 结果输出

4.5.1 识别输出信息

4.5.2 提取值

4.6 高级搜索分析

4.7 实验评估

4.7.1 索引分析

4.7.2 执行效率

4.7.3 查询质量

4.8 本章小结

第五章 总结和展望

5.1 总结

5.2 展望

参考文献

致谢

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

攻读学位期间参与科研项目情况

学位论文评阅及答辩情况表