基于序列化的高效XML查询算法

论文摘要

由于可扩展标记语言（eXtensible Markup Language,XML）具有结构简单、自表达、可扩展性强等诸多优点,近几年越来越多的企业和互联网应用使用XML作为数据表示、数据存储和数据交换的格式。在所有XML相关的应用中,如何进行XML数据上的查询处理则是工业界和学术界最为关注的课题之一。特别是如何回答海量XML文档上的结构化查询（Structured Query）请求,一直是研究的热点问题。现有的很多查询算法,都是通过分解-连接（Split-Join）操作的方式,把复杂的结构查询拆成若干个简单路径查询分别处理,并把中间结果连接起来得到最终结果的方法。但是,这类方法往往效率不高,主要原因在于复杂查询拆成多个简单路径查询,分别处理这些简单路径查询所得到的中间结果集往往较大,多个集合的连接操作更是需要耗费大量的时间,所以连接操作往往成为整个查询系统的性能瓶颈。虽然通过设计一些索引结构和堆栈操作,能够有效地提高连接操作的性能,但无法从根本上解决结构连接（Structured Join）的性能瓶颈问题。基于序列化的查询方法从彻底避免连接操作的目的出发,通过把XML文档和结构化查询请求转换成符合特定格式的序列,并且通过序列匹配的方式来回答结构化查询,从而把复杂的结构查询作为一个整体进行处理,避免连接操作,提高了系统的查询性能。然而,由于XML文档的半结构数据特性和序列的一维数据特性之间的不兼容性,现有基于序列化的查询系统往往不能达到最优的性能。本文提出了一种新的基于序列化的XML查询算法——LEO方法,该方法通过深入分析序列化方法中的几个基本问题,提出了两个重要的概念:灵活地序列化XML文档和灵活地进行查询序列匹配的策略。首先,在序列化过程中,本文提出了一种灵活的序列化策略,该策略通过对文档进行适当的编码,以支持对所得LEO序列中的元素进行任意排列的操作,从而可以按照文档集中各元素出现的频率对序列元素进行排列,使得所得各序列之间具有最长的共有前缀,以缩小所建立的trie-树索引的空间耗费。本文提出了一种泛化编码技术,通过对文档集进行适当地预处理并建立一棵超树,以扩展范围编码得到序列化步骤中必须的三元组编码。泛化编码技术是LEO序列化步骤中最关键的一个部分。其次,对于查询过程中的序列匹配算法,本文提出了一种灵活的匹配策略,该策略摒弃现有序列化方法中自左至右的匹配顺序,而是根据查询序列中各元素的选择度决定匹配的顺序,从而解除了序列顺序和匹配顺序的耦合性。在此基础上,我们通过预处理查询请求,制定最优的查询计划（Query Plan）,保证整个查询过程中的搜索空间达到最小,最终取得最优的查询性能。通过以上两种新的文档序列化策略和查询序列匹配算法,本文提出的LEO方法能够高效地处理各种查询。通过实验比较,在不同的标准数据集上对多种查询请求进行测试,LEO序列化方法比现有的其它序列化方法在查询时间和磁盘I/O操作上都有了很大的性能提高;而同样地,在比较多个序列化的索引结构时,LEO方法中所建立的索引结构也具有最优的空间性能。另外,与其他非序列化的基于磁盘的XML索引方法相比,本文提出的索引和查询也都有更优的表现。总之,实验结果验证了本文提出的LEO序列化方法具有更高的查询性能和更好的索引空间性能。

论文目录

• 摘要
• ABSTRACT
• 图目录
• 表目录
• 第一章 绪论
• §1.1 研究背景
• §1.2 本文的研究内容和贡献
• §1.3 论文结构
• 第二章 相关知识
• §2.1 XML文档以及XML树
• §2.2 XML结构化查询及应用场景
• §2.3 基于序列化的查询方法
• §2.3.1 ViST方法
• §2.3.2 PRIX方法
• +方法'>§2.3.3 ViST⁺方法
• §2.4 序列化方法的问题及其解决方案
• §2.4.1 影响序列化方法性能的主要因素
• §2.4.2 本文的解决方案
• §2.5 本章小结
• 第三章 序列化过程及索引技术
• §3.1 XML查询系统的框架
• §3.2 一种新的序列化策略
• §3.2.1 序列化步骤的前提要求
• §3.2.2 编码技术
• §3.3 建立索引结构
• §3.3.1 trie-树的建立和编码
• §3.3.2 基于磁盘的索引
• §3.4 本章小结
• 第四章 泛化编码技术
• §4.1 编码方法的影响
• §4.2 超树和最小超树
• §4.3 构建超树算法
• §4.3.1 近似算法
• §4.3.2 一个完整的序列化例子
• §4.4 本章小结
• 第五章 查询匹配算法
• §5.1 一种灵活的序列匹配策略
• §5.2 查询计划
• §5.2.1 匹配顺序的影响
• §5.2.2 查询计划的定义
• §5.2.3 时空复杂性分析
• §5.3 通配符的处理
• §5.4 本章小结
• 第六章 实验结果与分析
• §6.1 实验环境
• §6.2 实验结果与分析
• §6.2.1 与基于序列化的方法比较
• §6.2.2 与其他基于磁盘的索引系统比较
• §6.2.3 索引的空间性能比较
• §6.3 本章小结
• 第七章 总结
• 参考文献
• 附录
• 攻读硕士学位期间参与的科研项目
• 已发表或录用的论文
• 参加的学术活动
• 致谢