XML数据管理中的结构查询技术研究

论文摘要

随着互联网技术迅猛发展,XML已逐渐成为数据表达和数据交换的标准。越来越多的Web数据通过XML文档形式呈现。如何有效管理这些XML数据,是当前数据库领域一个重要研究课题。XML数据具有半结构化特征,其存储、查询、更新比传统结构化数据更为复杂。使用传统数据库技术解决XML数据管理问题,其效果不佳。为此,需要根据XML数据特点,研究开发新的XML数据管理技术。本文主要研究XML数据管理中的结构查询处理。XML结构查询是XML所特有的一类查询,其查询条件为XML结构约束,以路径表达式形式出现。在XML数据查询中,XML结构查询占有基础地位,许多已知的XML查询语言,如XQuery,XPath等,都以XML结构查询作为其核心部分。因此,高效的XML结构查询处理在XML数据管理中非常重要。本文根据路径表达式的不同,对XML结构查询实行分类处理,从而提高其查询效率。首先,本文提出了一种多分类XML结构查询处理框架MCXArch,具体描述了该框架的两个重要组成部分:查询执行模型MCXEng和查询优化模型MCXOpt。在模型MCXEng中,给出了各类查询执行算子。在模型MCXOpt中,给出了多类结构查询优化规则。接着,本文围绕MCXArch框架,分析研究了四个XML结构查询关键技术点:XML线性路径匹配;XML分支路径匹配;XML结构查询加速和XML包含连接估计。在XML线性路径匹配研究中,本文提出了两种新匹配算法:整数差值匹配法和约简式遍历匹配法。整数差值匹配法用于XML简单线性路径匹配;而约简式遍历匹配法主要用于XML复杂线性路径匹配。这两种匹配算法都通过约简方式,提高查询匹配效率。在XML分支路径匹配研究中,本文给出了两种启发式匹配算法:Heur-PC和Heur-Unnested。算法Heur-PC用于简单分支路径匹配;算法Heur-Unnested用于非自嵌套分支路径匹配。与先前的小枝连接类匹配算法相比,两种启发式算法所需的查询匹配时间更少。在XML结构查询加速研究中,本文提出了一种位图过滤加速法。利用前/后缀标签位图,该方法能加速多类查询匹配算法,如遍历类匹配算法、连接类匹配算法等。本文给出了过滤加速原理,并研究了位图过滤加速法与查询匹配算法的集成。在XML包含连接估计研究中,本文给出了一种权重哈尔小波的估计方法。在预处理阶段,使用哈尔小波,压缩统计数据,生成小波摘要。在查询估计阶段,利用小波系数重构,获取XML包含连接估计值。同时,在估计方法中,使用概率权重模型,体现查询负载变化。在相同的空间限制下,权重哈尔小波估计法比先前的XML包含连接估计法具有更小的估计误差。

论文目录

• 摘要
• ABSTRACT
• 第1章 绪论
• 1.1 研究背景与目的
• 1.2 相关工作及研究现状
• 1.2.1 原生XML数据库系统研究
• 1.2.2 XML结构查询处理研究
• 1.2.3 XML存储及索引研究
• 1.2.4 现有研究的问题和不足
• 1.3 本文研究思路
• 1.4 本文研究内容
• 1.5 本文组织
• 第2章 MCXARCH:一种多分类XML结构查询框架
• 2.1 引言
• 2.2 XML结构查询框架MCXArch
• 2.3 多分类 XML结构查询执行模型
• 2.3.1 查询执行计划
• 2.3.2 查询匹配算子
• 2.3.3 结果重构算子
• 2.3 4 XML结构索引管理
• 2.3 5 XML结构元信息管理
• 2.4 多分类XML结构查询优化模型
• 2.4.1 XML查询路径
• 2.4.2 查询路径重写
• 2.4.3 选择性估计
• 2.4.4 查询执行决策
• 2.4.5 静态信息管理
• 2.4.6 动态信息管理
• 2.5 本章总结
• 第3章 约简式XML线性路径匹配技术
• 3.1 引言
• 3.2 简单线性路径匹配
• 3.2.1 现有方法
• 3.2.2 整数路径编码
• 3.2.3 整数差值匹配
• 3.2.4 长路径处理
• 3.3 复杂线性路径匹配
• 3.3.1 自动机遍历匹配
• 3.3.2 约简缩略树
• 3.3.3 约简式遍历匹配
• 3.4 XML线性路径匹配应用
• 3.5 实验及性能评价
• 3.5.1 实验设置
• 3.5.2 简单线性路径匹配实验
• 3.5.3 复杂线性路径匹配实验
• 3.6 本章总结
• 第4章 启发式XML分支路径匹配技术
• 4.1 引言
• 4.2 现有方法
• 4.2.1 结构连接算法
• 4.2.2 完全小枝连接匹配算法
• 4.3 非自嵌套分支路径匹配
• 4.3.1 非自嵌套启发模型
• 4.3.2 Heur-Unnested算法实现
• 4.4 简单分支路径匹配
• 4.4.1 标签编码
• 4.4.2 路径匹配点模型
• 4.4.3 Heur-PC算法实现
• 4.4.4 其他细节
• 4.5 XML分支路径匹配应用
• 4.6 实验及性能评价
• 4.6.1 实验设置
• 4.6.2 简单分支路径匹配实验
• 4.6.3 非自嵌套分支路径匹配实验
• 4.7 本章总结
• 第5章 面向XML结构查询的位图过滤加速技术
• 5.1 引言
• 5.2 标签位图
• 5.2.1 预备定义
• 5.2.2 标签位图
• 5.2.3 位图创建
• 5.2.4 位图约简
• 5.3 标签位图过滤加速原理
• 5.4 标签位图过滤集成
• 5.4.1 遍历匹配中的位图过滤集成
• 5.4.2 结构连接匹配中的位图过滤集成
• 5.4.3 游标流匹配中的位图过滤集成
• 5.5 实验及性能评价
• 5.5.1 实验设置
• 5.5.2 线性路径匹配加速实验
• 5.5.3 分支路径匹配加速实验
• 5.5.4 空间代价
• 5.6 本章总结
• 第6章 基于权重哈尔小波的XML包含连接估计技术
• 6.1 引言
• 6.2 XML包含连接估计
• 6.3 现有方法
• 6.3.1 间隔模型
• 6.3.2 PL直方图法
• 6.3.3 IM随机取样法
• 6.4 权重哈尔小波估计法
• 6.4.1 标签名对模型
• 6.4.2 哈尔小波技术
• 6.4.3 估计方法
• 6.5 实验及性能评价
• 6.5.1 实验设置
• 6.5.2 估计误差度量
• 6.5.3 构造代价
• 6.5.4 估计代价
• 6.6 本章总结
• 第7章 总结与展望
• 7.1 论文研究工作
• 7.2 论文创新点
• 7.3 未来工作展望
• 参考文献
• 致谢
• 作者简历