基于FTContainsExpr的扩展模式树匹配技术研究

论文摘要

XML采用树形模型来表示数据,XML文档上的查询通常被表示成小枝模式。与此同时,XML文档上关键字的检索也因其直观、友好的查询接口而被广泛研究。为了更好地整合数据管理领域与信息检索领域对XML文档查询技术的研究成果,W3C提出XQuery Full-Text作为XQuery的补充。它可以对XML数据中的结构信息与文本信息进行无缝地查询。本文针对XQuery Full-Text中具有合取关键字查询语义的FTContainsExpr表达式提出了相应的扩展模式树及其模式匹配问题。扩展模式树匹配问题由于关键字包含关系的引入而呈现出问题的特殊性。我们首先针对该问题设计了基于Dewey编码的解决方案,DILPathStack算法和DeweyPathStack算法。DILPathStack算法首先计算关键字结点的SLCA,然后利用它们来指导DeweyPathStack算法对结构化路径进行匹配。SLCA的计算可以有效减少在DeweyPathStack算法执行过程中各数据流无效结点的入栈,避免了无意义的栈操作,从而使得整个匹配过程更加高效。然后,针对DILPathStack算法和DeweyPathStack算法仍然存在的弊端,我们提出了基于区间编码的、直接对所有扩展模式树普适的匹配算法ILETwigStack。它对扩展模式树进行了重构,将扩展模式树中的每个关键字结点组收缩归并为一个查询单点,以它们的SLCA数据结点流来取代原始关键字结点流,重构后的扩展模式树能够用TwigStack算法进行匹配。这种方法既降低了扩展模式树的结构复杂度又大量减少了初始数据流结点的数量。实验结果表明,在对扩展模式树的处理效率上,ILETwigStack算法均胜于DILPathStack算法和传统的TwigStack算法。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 XML基础
• 1.2 XML查询语言
• 1.2.1 XPath
• 1.2.2 XQuery
• 1.2.3 XQuery Full-Text
• 1.3 XML解析器
• 1.4 本文工作和贡献
• 1.5 文章结构
• 第二章 背景知识和相关工作
• 2.1 XML数据模型
• 2.2 经典模式树与模式匹配
• 2.3 XML编码技术
• 2.3.1 基于区间的编码
• 2.3.2 基于路径的编码
• 2.4 XML结构查询处理方法
• 2.5 XML关键字检索处理方法
• 2.6 本章小结
• 第三章 查询语义和扩展模式树匹配问题
• 3.1 FTContainsExpr表达式的查询语义
• 3.2 扩展模式树及其匹配问题
• 3.3 本章小结
• 第四章 基于Dewey编码的扩展模式树匹配算法
• 4.1 算法提出的动机
• 4.2 预备知识
• 4.3 符号定义和数据结构
• 4.4 算法伪码
• 4.5 算法解释与分析
• 4.6 算法示例
• 4.7 本章小结
• 第五章 基于区间编码的扩展模式树匹配算法
• 5.1 算法提出的动机
• 5.2 基于区间编码的LCA问题的解决方案
• 5.2.1 LCA问题、RMQ问题与LCA问题到RMQ问题的规约
• 5.2.2 RMO问题解决方案的逐步求精
• 5.3 基于区间编码的SLCA问题的解决方案
• 5.3.1 符号定义
• 5.3.2 SLCA问题的一个朴素解法
• 5.3.3 SLCA问题的一个快速算法
• 5.4 算法设计思想与伪码
• 5.5 本章小结
• 第六章 实验结果与分析
• 6.1 实验环境
• 6.2 实验结果
• 6.3 实验分析
• 6.4 本章小结
• 第七章 总结与展望
• 参考文献
• 硕士研究生期间主要工作
• 致谢