分布式数据库系统查询优化算法的研究

论文摘要

本文首先介绍了分布式数据库系统的基本概念,然后简要描述了分布式查询的处理过程;重点描述了各种分布式数据库的查询处理及优化算法,如基于关系代数等价变换规则的优化算法、基于连接的优化算法、基于半连接的优化算法等。然后对基于Hash划分的分布式连接算法进行了详细讨论。特别是对CHAIN算法和Kruskal启发式算法的优缺点进行了较深入的分析和研究,以此为切入点,采用回溯法思想,对原有算法进行了改进。该优化算法对查询图进行深度优先搜索,产生各个边界点及相应的查询块。然后利用Kruskal启发式算法对特定的查询块进行优化。当一轮遍历结束后,算法将重新构造一个新的查询图,接着对该查询图以深度优先搜索,重复以上各步操作,直到查询图不能再分割为止。论文最后对本算法进行了实验验证,实验结果表明使用该算法产生的关系连接序列花费的代价比传统的Kruskal启发式算法更小。

论文目录

• 摘要
• ABSTRACT
• 1 绪论
• 1.1 论文的研究背景及选题的意义
• 1.2 国内外现状综述
• 1.3 研究内容
• 2 分布式数据库查询处理及优化
• 2.1 分布式数据库系统的定义及特点
• 2.2 分布式查询优化概述
• 2.2.1 集中式查询优化与分布式查询优化
• 2.2.2 分布式查询优化的准则和代价估算
• 2.2.3 分布式查询处理的层次结构
• 2.3 查询处理过程
• 2.4 查询分解
• 2.5.1 基于关系代数等价变换的优化算法
• 2.5.2 基于半连接算法的查询优化算法
• 2.5.3 基于直接连接算法的查询优化算法
• 2.6 Hash 划分算法
• 2.6.1 Hash 划分
• 2.6.2 重哈希划分问题
• 2.7 本章小结
• 3 重哈希划分问题的优化算法
• 3.1 基于链查询的 CHAIN 算法
• 3.1.1 查询图及其生成树
• 3.1.2 代价模型
• 3.1.3 冗余条件表达式及带冗余条件表达式的查询图QGq+
• 3.1.4 链查询
• 3.1.5 CHAIN 算法的实现
• 3.1.6 CHAIN 算法的一个实例
• 3.2 Kruskal 启发式算法
• 3.2.1 Kruskal 启发式算法的基本思想
• 3.2.2 Kruskal 启发式算法的实现
• 3.2.3 Kruskal 启发式算法的主要数据结构和函数
• 3.3 本章小结
• 4 算法的改进
• 4.1 改进的原因
• 4.2 改进的思路
• 4.3 具体实现
• 4.3.1 边界点和查询块的定义
• 4.3.2 边界点和查询块的获得
• 4.3.3 查询块的连接优化
• 4.3.4 重构查询图
• 4.3.5 代价估算
• 4.4 基本步骤
• 4.5 主要数据结构和函数
• 4.6 本章小结
• 5 实验
• 5.1 实验样本
• 5.2 总结分析
• 6 结论
• 6.1 总结
• 6.2 论文研究展望
• 攻读硕士期间参与的科研项目及论文
• 致谢
• 参考文献