基于结构化联接的XML查询模式匹配关键技术研究

摘要

这篇论文主要讨论了基于结构化联接的XML查询模式匹配的相关关键技术.提出了包含段划分的概念,并据此提出基于包含段划分的结构化联接新方法.在包含段概念的基础上,研究了联接次序选择的问题,对隐检整枝联接方法进行了扩展.对运用基于包含段的隐检整枝联接算法查询XML流数据也提出了一个解决框架.最后,对影响查询系统性能较大的XML模式树的最小化问题也进行了探讨.这篇论文首先从整树匹配和基于索引结点的模式匹配两个方面对XML查询匹配的相关研究进行了综述,为该方向的研究现状勾勒出一个较为清晰的轮廓,也为确立该文研究的意义和必要性奠定了基础.该篇论文的主要贡献有以下几个方面:●针对结构化联接所基于的三元组索引结构进行了研究,提出对索引空间结构进行包含段划分的思想,并据此对结构化联接算法进行了改进.●基于结构化联接操作的隐检整枝联接算法也是以三元组索引为基础的.我们同样将包含段划分的概念引入到这一领域中来.首先研究基于包含段划分的隐检整枝联接方法.又运用包含段划分的概念对隐检整枝匹配方法中联接次序选择的问题进行了研究.从上述两个方面对隐检整枝联接算法进行了改进.●隐检整枝联接方法有一个十分优良的特性,就是它只需要对整个XML文档顺序扫描一遍就可以生成所需的三元组索引.这一点十分适合对XML数据流的查询处理.而且,包含段划分方法又为在扫描XML数据流的同时运行隐检整枝联接算法的查询处理提供了可能.因此,这篇论文也在上述两方面的基础上,提出了一个基于包含段划分的隐检整枝联接算法查询XML数据流的处理框架.●最后,由于XML查询模式匹配方法的效率在相当大的程度上依赖于查询模式树的大小,这篇论文中也讨论了模式树的最小化问题.主要工作是将DTD约束SC扩展为ESC,并提出了一个ESC下的多项式时间的XML模式树最小化算法.

目录

摘要

第一章绪论

1.1 相关工作综述

1.1.1研究背景

1.1.2整树匹配

1.1.3基于结构化联接的匹配方法

1.1.4结论与展望

1.2本文主要贡献

第二章结构化联接相关概念

2.1引言

2.2数据模型及索引结构

2.2.1 XML文档树数据模型

2.2.2索引结构及其特点

2.3模式匹配相关概念

2.3.1模式匹配的定义

2.3.2结构化联接的定义

2.3.3基于栈的结构化联接基本结构

第三章基于包含段划分的结构化联接新方法

3.1相关工作分析

3.2现有方法及其不足

3.3基于包含段划分的输入序列索引结构特点分析

3.4基于包含段划分的结构化联接方法

3.4.1算法描述

3.4.2算法正确性证明及时空复杂度分析

3.5实验结果及分析

3.5.1实验环境

3.5.2实验结果及分析

3.6小结语

第四章基于包含段划分的隐检整枝联接方法

4.1准备知识

4.2基于包含段划分的隐检整枝联接算法

4.2.1基于包含段划分的隐检整枝联接算法TwigStack-CS

4.2.2相关的实验结果及分析

4.3基于(联接)次序选择的隐检整枝联接方法

4.3.1问题的推理

4 3.2基于联接次序选择的隐检整枝联接算法：TwigStack-CS-OS

4.3.3实验

4.4 隐检整枝联接算法对XML数据流的查询处理

4.4.1 基本知识

4.4.2查询操作框架

4.4.3主要问题讨论

第五章DTD约束下的查询模式树最小化研究

5.1简要介绍

5.2准备知识

5.3 DTD约束下的XML查询树模式的最小化

5.4树模式最小化算法

5.5结束语

第六章总结及展望

后记

发表论文清单

主要参考文献

论文独创性声明和论文使用授权声明