Print

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

论文摘要

本文首先介绍了分布式数据库系统的基本概念,然后简要描述了分布式查询的处理过程;重点描述了各种分布式数据库的查询处理及优化算法,如基于关系代数等价变换规则的优化算法、基于连接的优化算法、基于半连接的优化算法等。然后对基于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 论文研究展望
  • 攻读硕士期间参与的科研项目及论文
  • 致谢
  • 参考文献

    • 相关论文文献

    本文来源: https://www.lw50.cn/article/11c21a2429b946ed6cd07c4a.html