基于最紧致片段XML关键字检索研究

摘要

XML(Extensible Markup Language)是被W3C基于标准的广义标记语言所创建，被用作定义语义标记。在Web服务、电子商务、数字图书馆等诸多网络相关应用领域已经成为描述数据的事实上的标准。为了方便用户从海量的XML数据中提取他们所需要的信息，许多XML数据查询算法应运而生，使得XML数据查询成为XML数据管理领域的一个热点。
　　 通常，XML数据查询算法按照查询模式描述的不同分为两类，即XML结构查询和XML关键字查询。前者多采用了正则表达式的描述方法，偏向于传统的结构化的查询方式，能够清楚的表述用户的查询意图；后者融入了信息检索领域常用的查询思想和方法，允许用户仅仅输入关键字就能够进行查询。
　　 XML结构查询算法根据精确的查询条件，能够输出理想的查询结果。然而，该算法对进行查询的用户也提出了更高的要求，即不仅要熟悉结构查询算法所采用的查询语言，而且还要了解待查询的XML文档树结构。以上要求对于绝大多数用户而言是不切实际的，而XML关键字查询很好的解决了以上的问题，所以从用户的角度出发，XML关键字查询是一种能够被广泛使用的查询方法。
　　 XML关键字查询方式中最关键的问题是如何求解包含所有关键字的最紧致片段，即SLCA(Smallest Lowest Common Ancestors)问题。目前已有许多求解算法，包括Stack、ILE、SE、LISA和LISAⅡ等。ILE和SE在与Stack的实验对比中表现得效率更高，适合需要频繁I/O操作的海量XML查询，他们仅需要顺序读取XML数据一遍；相比ILE和SE，LISA和LISAⅡ在轻量级XML查询中，无论是在理论分析上还是试验对比中都表现出了更好的性能。
　　 然而，LISA不仅需要频繁扫描节点，而且需要引入集合交操作，耗费了大量CPU周期。LISAⅡ虽然在避免不必要扫描方面改进了LISA算法，但却使用了自己独有的编码，不仅引入了编码映射，而且也使得该算法的通用性大大削弱。这两种算法即便作为一种仅在内存中执行的算法，以上缺点也影响了查询速度。
　　 本文围绕SLCA展开，本文在已有经典算法基础上对已有算法做出了改进，本文的主要贡献为：
　　 1、分析SLCA现有成熟的求解算法上的缺点并提出新的改进算法，针对LISAⅡ算法使用前序编码的扩展Dewey码，该编码具有许多冗余信息，浪费了存储空间的缺点。本文提出了一种新的基于层次编码的SLCA求解算法UBS，该算法的空间复杂度明显降低，在理论求解时间和LISAII基本相同的情况下，使用了更少的存储空间
　　 2、针对XML关键字检索的查询准确率问题，分析SLCA优缺点，在此基础上提出了有效公共祖先，也就是ESLCA的定义，该定义从元素标签内容和结构相似性等价两个方面着手判定XML关键字查询中可能存在的无效结果，并针对ESLCA在查询结果存在但返回结果为空的情况定义了XML关键字查询的结果集。最后本文通过EV-Index提出基于等价模式值索引的查询算法BVA,实验表明BVA在查询效率和查询质量上有较大的提高。

目录

文摘

英文文摘

第一章 绪论

1.1 研究背景

1.2 XML查询研究现状

1.2.1 XML结构查询研究现状

1.2.2 XML关键字查询研究现状

1.3 研究内容和主要工作

1.4 本文的组织结构

第二章 XML关键字查询

2.1 背景知识

2.1.1 XML文档树结构

2.1.2 编码方案

2.1.3 包含关键字的最小片断

2.2 基本原理

2.3 包含关键字的最小片断求解算法

2.3.1 Stack算法

2.3.2 ILE和SE算法

2.3.3 LISA和LISAⅡ算法

2.4 本章小结

第三章 基于层次编码的求解算法

3.1 背景介绍

3.2 基本思想

3.3 基于层次编码的算法描述和实例

3.3.1 UBS算法描述

3.3.2 算法实例

3.4 UBS时间复杂度分析

3.5 实验分析

3.5.1 测试数据和实验环境

3.5.2 对比实验和分析

3.6 本章小结

第四章 有效同祖先最紧致片段及其求解算法

4.1 SLCA查询分析

4.2 相关定义

4.3 基于等价值索引的查询算法

4.4 算法时间复杂度分析

4.5 本章小结

第五章 总结与展望

5.1 本文工作总结

5.2 未来工作展望

参考文献

致谢

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

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

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