XML索引与查询的若干关键技术研究

论文摘要

随着Internet的快速发展,XML已成为Web数据表示和交换的新标准,越来越多的信息处理系统采用XML文档作为信息存储、交换和发布的载体。与此同时,XML文档结构和用户查询需求也变得越来越复杂,包含大量引用边的图结构XML文档,以及仅包含部分路径信息和关键词的XML IR（Information Retrieval）查询变得越来越普遍,这给XML索引与查询技术提出了严峻的挑战。目前XML索引技术的研究主要集中在3个方面:一是面向XML有向树的节点记录类索引;二是面向XML有向图的结构摘要类索引（即XML结构索引）;三是XML数据与全文数据的联合索引。与节点记录类索引相比,后两类索引的研究相对薄弱,索引的整体性能还比较低,离实际应用还存在较大的距离。针对XML结构索引目前存在的主要问题:索引创建时间较长、空间开销较大、查询效率较低以及分支路径查询研究较为薄弱,本文提出了三种高效的结构索引;针对XML数据与全文数据的联合索引目前存在的主要问题:缺少XML数据与全文数据的统一索引模型以及配套的高效协同查询机制,本文提出了一种高效的基于统一索引模型的XML联合索引。本文的研究内容和创新工作主要有以下4点:（1）支持简单路径查询的半动态XML结构索引研究本文在互关联后继树（IRST）的基础上,引入一种新型的相似性约束条件——k阶相似关系,以及结构索引的相似性归并思想,提出了一种基于互关联后继树且支持简单路径查询的高效半动态结构索引——IRST（k）-index,并给出相关算法和理论证明。该索引以互关联后继树为实现方式,以k阶相似关系为相似性约束条件,能高效地查询简单路径表达式。经实验验证,与国际上同类索引相比,该索引的创建速度更快、查询效率更高、空间开销更小。（2）支持分支路径查询的半动态XML结构索引研究本文在IRST（k）-index的基础上,引入一种新型的相似性约束条件——k-l阶相似关系,以及前向、后向相似度的概念,提出了一种基于互关联后继树且支持分支路径查询的高效半动态结构索引——IRST（k,l）-index,并给出相关算法和理论证明。该索引以互关联后继树为实现方式,以k-l阶相似关系为相似性约束条件,能高效地查询分支路径表达式。经实验验证,与国际上同类索引相比,该索引的创建速度更快、查询效率更高、空间开销更小。（3）支持分支路径查询的全动态XML结构索引研究本文在M（k）-index的基础上,引入k-l阶互模拟关系以及前向、后向相似度的概念,提出了一种支持分支路径查询的高效全动态结构索引——MBF（k,l）-index,并给出相关算法和理论证明。该索引以k-l阶互模拟关系为相似性约束条件,不仅能高效地查询分支路径表达式,还能利用频繁查询路径的查询结果来监督和指导索引优化的全过程,从而有效地避免了无关索引和数据节点的过度分裂。经实验验证,与国际上同类索引相比,该索引的查询效率更高、空间开销更小。（4）XML数据与全文数据的联合索引技术研究本文在互关联后继树的基础上,提出了一种XML树型结构与全文数据的统一索引模型——基于后继模式树的互关联区间后继树,建立了一套XML文档的树型结构与文本节点的联合索引机制——XML联合索引,并给出该索引的倒向创建算法和协同查询算法。经实验验证,与国际上同类索引相比,该索引的膨胀比更小、查询效率更高。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景
• 1.2 研究现状
• 1.2.1 XML规范与数据
• 1.2.2 XML数据模型
• 1.2.3 XML查询模式
• 1.2.3.1 XML CR查询模式
• 1.2.3.2 XML IR查询模式
• 1.2.4 实现XML CR查询模式的索引技术
• 1.2.4.1 面向XML有向树的节点记录类索引
• 1.2.4.2 面向XML有向图的结构摘要类索引
• 1.2.5 实现XML IR查询模式的索引技术
• 1.3 存在的问题
• 1.4 本文的研究内容与主要贡献
• 1.5 本文的组织结构
• 第二章 支持简单路径查询的半动态XML结构索引
• 2.1 引言
• 2.2 背景知识及相关工作
• 2.2.1 XML数据模型
• 2.2.2 简单路径表达式及相关概念
• 2.2.3 支持简单路径查询的XML结构索引
• 2.2.4 面向全文的互关联后继树模型
• 2.3 面向XML数据图的互关联后继树模型
• 2.4 IRST（k）-Index的理论模型
• 2.4.1 IRST（k）-Index的定义和基本理论
• 2.4.2 IRST（k）-Index的理论创新之处
• 2.5 IRST（k）-Index创建算法
• 2.5.1 算法描述
• 2.5.2 算法复杂度及性能分析
• 2.6 IRST（k）-Index查询算法
• 2.6.1 算法描述
• 2.6.2 算法复杂度及性能分析
• 2.7 IRST（k）-Index更新算法
• 2.7.1 子图增加算法
• 2.7.2 边增加算法
• 2.8 实验结果及分析
• 2.8.1 实验数据集与代价模型
• 2.8.2 IRST（k）-Index创建时间的实验结果与分析
• 2.8.3 IRST（k）-Index空间开销的实验结果与分析
• 2.8.4 IRST（k）-Index查询开销的实验结果与分析
• 2.9 本章小结
• 第三章 支持分支路径查询的半动态XML结构索引
• 3.1 引言
• 3.2 背景知识及相关工作
• 3.2.1 XML数据模型
• 3.2.2 分支路径表达式及相关概念
• 3.2.3 支持分支路径查询的XML结构索引
• 3.3 面向XML数据图的互关联后继树模型
• 3.4 IRST（k,l）-Index的基本理论
• 3.5 IRST（k,l）-Index创建算法
• 3.5.1 算法描述
• 3.5.2 算法分析
• 3.6 IRST（k,l）-Index查询算法
• 3.6.1 复杂分支路径查询算法
• 3.6.1.1 算法描述
• 3.6.1.2 算法分析
• 3.6.2 基本分支路径查询算法
• 3.6.2.1 算法描述
• 3.6.2.2 算法分析
• 3.6.3 简单路径查询算法
• 3.6.3.1 算法描述
• 3.6.3.2 算法分析
• 3.7 实验结果及分析
• 3.7.1 实验数据集与代价模型
• 3.7.2 IRST（k,l）-Index创建时间的实验结果与分析
• 3.7.3 IRST（k,l）-Index空间开销的实验结果与分析
• 3.7.4 IRST（k,l）-Index查询开销的实验结果与分析
• 3.8 本章小结
• 第四章 支持分支路径查询的全动态XML结构索引
• 4.1 引言
• 4.2 背景知识
• 4.3 MBF（k,l）-Index的基本理论
• 4.4 MBF（k,l）-Index查询算法
• 4.4.1 复杂分支路径查询算法
• 4.4.1.1 算法描述
• 4.4.1.2 算法分析
• 4.4.2 基本分支路径查询算法
• 4.4.2.1 算法描述
• 4.4.2.2 算法分析
• 4.4.3 简单路径查询算法
• 4.4.3.1 算法描述
• 4.4.3.2 算法分析
• 4.4.4 查询性能分析
• 4.5 MBF（k,l）-Index优化算法
• 4.6 实验结果及分析
• 4.6.1 实验数据集与代价模型
• 4.6.2 MBF（k,l）-Index空间开销的实验结果与分析
• 4.6.3 MBF（k,l）-Index分支路径查询开销的实验结果与分析
• 4.6.4 MBF（k,l）-Index简单路径查询开销的实验结果与分析
• 4.7 本章小结
• 第五章 XML数据与全文数据的联合索引技术
• 5.1 引言
• 5.2 背景知识及相关工作
• 5.2.1 全文索引模型
• 5.2.1.1 位图
• 5.2.1.2 署名文件
• 5.2.1.3 倒排表
• 5.2.1.4 Pat树和Pat数组
• 5.2.2 XML数据与全文数据的联合索引
• 5.3 统一索引模型——基于后继模式树的互关联区间后继树
• 5.4 XML树型结构与文本节点的联合索引机制
• 5.5 XML联合索引的创建算法
• 5.5.1 算法描述
• 5.5.2 算法分析
• 5.6 XML联合索引的查询算法
• 5.6.1 基于后继模式树的区间过滤查询算法
• 5.6.1.1 算法描述
• 5.6.1.2 算法分析
• 5.6.2 基于后继模式树的自底向上查询算法
• 5.6.2.1 算法描述
• 5.6.2.2 算法分析
• 5.7 实验结果及分析
• 5.8 本章小结
• 第六章 XML索引与查询原型系统
• 6.1 引言
• 6.2 一个集成的XML索引与查询系统框架结构
• 6.2.1 系统架构
• 6.2.2 系统的主要功能模块
• 6.3 原型系统
• 6.3.1 索引存储结构设计
• 6.3.1.1 索引的数据结构
• 6.3.1.2 索引的物理存储
• 6.3.2 系统设计及运行机制
• 6.4 本章小结
• 第七章 总结与展望
• 7.1 总结
• 7.2 进一步的工作
• 参考文献
• 攻读博士学位期间参与的科研项目及主要成果
• 致谢