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 II等。ILE和SE在与Stack的实验对比中表现得效率更高,适合需要频繁I／O操作的海量XML查询,他们仅需要顺序读取XML数据一遍；相比ILE和SE, LISA和LISAⅡ在轻量级XML查询中,无论是在理论分析上还是试验对比中都表现出了更好的性能。然而,LISA不仅需要频繁扫描节点,而且需要引入集合交操作,耗费了大量CPU周期。LISA II虽然在避免不必要扫描方面改进了LISA算法,但却使用了自己独有的编码,不仅引入了编码映射,而且也使得该算法的通用性大大削弱。这两种算法即便作为一种仅在内存中执行的算法,以上缺点也影响了查询速度。为此,本文提出一种轻量级的、使用XML关键字查询通用的Dewey编码的新算法,BCS (Binary Comparative Search Algorithm),即二分比较查找求解包含XML关键字的最小片段问题。该算法有效地提高了搜索效率,对于数据量较大的XML树中,搜索效率提高尤其明显。BCS无论在理论分析上还是试验对比中,都表现出了较好的性能,是一种可行的最小包含关键字片段求解算法。作为一种新的XML关键字查询算法,BCS具有查询简便快捷、普通用户使用门槛较低、用户友好等的特点,但是也会存在查准率相对于XML结构查询算法较低的XML关键字查询的先天缺陷。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 XML查询的研究背景
• 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 XML编码方案
• 2.1.2.1 前缀编码理论
• 2.1.2.2 区间编码理论
• 2.1.2.3 Dewey编码理论
• 2.1.3 包含关键字的最小片断理论
• 2.2 基本原理
• 2.3 包含关键字的最小片断求解算法
• 2.3.1 Stack算法
• 2.3.2 ILE和SE算法
• 2.3.3 LISA和LISAⅡ算法
• 2.3.3.1 LISA算法
• 2.3.3.2 扩展Dewey码理论
• 2.3.3.3 LISAⅡ算法
• 第三章 二分比较查找算法
• 3.1 提出背景
• 3.2 基本思想
• 3.3 二分比较查找算法
• 3.4 BCS算法时间复杂度
• 3.5 BCS算法正确性证明
• 3.6 实验证明
• 3.6.1 测试平台
• 3.6.2 对比实验和分析
• 第四章 总结与展望
• 4.1 本文工作总结
• 4.2 未来方向展望
• 参考文献
• 致谢
• 攻读学位期间发表的学术论文目录
• 学位论文评阅及答辩情况表