XML数据库查询优化及相关技术研究

论文摘要

随着互联网的快速发展，出现了大量的Web数据。这些Web数据多以XML文档形式出现。如何有效存储、处理XML文档和从大量XML文档中检索有用信息，已成为数据库研究领域的一个重要研究课题。本文的研究工作主要围绕XML数据库的查询优化技术展开，重点研究基于模式信息和语义信息的XML查询优化技术。 针对XML文档的模式信息不精确的特点，提出了基于模糊决策树的XML模式抽取方法。分析了已有XML模式抽取算法的缺点和存在的问题，提出抽取XML近似模式的方法。用一阶Datalog作为XML的表示，用自增量的聚类算法将各实例对象聚类得到模式中的对象，建立模糊决策树来确定模式中各对象的近似模式，解决了模式抽取中的多边和缺边问题。 提出了基于粗糙集的XML数据依赖关系的发现方法。重点讨论了函数依赖和多值依赖关系。给出了XML函数依赖和XML多值依赖的定义。还给出了基于粗糙集的XML函数依赖和XML多值依赖关系的判定定理。基于判定定理，提出了XML函数依赖和XML多值依赖的发现算法。 提出了基于DTD的正则路径表达式查询优化方法。给出了扩展正则表达式的定义，实现对DTD模式树的简化。给出了交结点的定义，提出简路径和补路径两个查询优化策略。该方法通过对XML查询语句的重写，实现对XML语言级上的查询优化。 提出了一种基于树代数的XML代数系统及其逻辑优化策略。给出了一种XML代数的描述，以模式树作为操作对象，定义了操作范围和三类操作符。针对XML查询处理及优化的问题，提出五种XML查询优化策略。针对XML压缩数据库，引入新的解压操作符，将ETA代数扩展到XML压缩数据库上。 提出了基于访问控制的XML查询优化方法。给出了一种高安全的XML访问控制模型，该模型基于访问控制视图，可解决隐推理和结构信息隐藏问题。利用XML访问控制视图实现对XML查询的重写，主要采用剪枝技术，实现XML语言级上的查询优化。

论文目录

• 第1章 绪论
• 1.1 研究目的及意义
• 1.2 XML数据库的研究内容
• 1.2.1 XML存储及索引
• 1.2.2 XML查询处理及查询优化
• 1.3 国内外研究现状
• 1.3.1 XML数据库系统
• 1.3.2 XML压缩数据库
• 1.3.3 查询处理
• 1.3.4 查询优化
• 1.4 存在的问题
• 1.5 主要研究内容
• 1.6 本文的篇章结构
• 第2章 XML基本定义及查询语言
• 2.1 XML数据模型
• 2.1.1 XML特性
• 2.1.2 OEM模型
• 2.1.3 DOM模型
• 2.1.4 XML文档类型定义
• 2.2 XML的基本概念
• 2.3 XML查询语言
• 2.3.1 XPath查询语言
• 2.3.2 XQuery查询语言
• 2.4 本章小结
• 第3章 基于模糊决策树的模式抽取
• 3.1 问题的提出
• 3.2 相关的研究工作
• 3.2.1 图模式抽取
• 3.2.2 Datalog规则抽取
• 3.2.3 聚类分类方法
• 3.3 模式抽取算法
• 3.3.1 Datalog模式表示
• 3.3.2 增量式结点聚类
• 3.3.3 基于模糊决策树的模式抽取算法
• 3.4 实验及结果分析
• 3.5 本章小结
• 第4章 基于粗糙集的XML数据依赖发现
• 4.1 粗糙集的基本概念
• 4.2 XML数据依赖
• 4.3 XML函数依赖
• 4.3.1 XML函数依赖定义
• 4.3.2 XML函数依赖推理规则
• 4.3.3 XML函数依赖发现算法
• 4.3.4 XML函数依赖实例与分析
• 4.4 XML多值依赖
• 4.4.1 XML多值依赖定义
• 4.4.2 XML多值依赖推理规则
• 4.4.3 XML多值依赖抽取算法
• 4.5 本章小结
• 第5章 XML查询优化
• 5.1 基于DTD的XML路径表达式查询优化
• 5.1.1 动机
• 5.1.2 扩展正则表达式
• 5.1.3 基于DTD的查询优化
• 5.1.4 实验及性能评价
• 5.2 XML查询代数
• 5.2.1 相关研究工作
• 5.2.2 问题的提出
• 5.2.3 ETA代数
• 5.2.4 等价变换规则
• 5.3 XML代数查询优化
• 5.3.1 启发式代数优化规则
• 5.3.2 选择谓词下移
• 5.3.3 抽取下移与分合
• 5.3.4 抽取替代自连接
• 5.3.5 XML函数依赖及键约束
• 5.3.6 其他
• 5.4 XML压缩数据库的查询优化
• 5.4.1 相关研究工作
• 5.4.2 压缩操作符
• 5.4.3 查询优化算法
• 5.5 本章小结
• 第6章 XML访问控制及查询优化
• 6.1 动机
• 6.2 相关研究工作
• 6.3 基于视图的访问控制模型
• 6.3.1 文件级访问控制
• 6.3.2 元素级访问控制
• 6.4 查询重写算法
• 6.5 实验结果及分析
• 6.6 本章小结
• 结论
• 参考文献
• 攻读博士学位期间发表的论文和取得的科研成果
• 致谢