GA在数据库多连接查询优化中的应用研究

论文摘要

多连接查询优化问题是数据库领域的一个难题。查询操作速度在很大程度上影响了数据库应用软件的执行效率。当关系个数增多时,查询执行计划的数目会随着该查询包含的关系个数呈现指数级的增长,导致搜索空间极度膨胀,计算复杂性非常大。传统的数据库采用的大多数是近似穷举的优化算法。在数据仓库和专家系统等应用中,查询所涉及到的关系数目通常都很大,这使得此类搜索算法效率非常低,用启发式算法或随机算法来处理连接关系较多时的优化问题是比较好的方法。因此,本文提出用遗传算法来优化数据库的多连接查询。对于多连接查询优化,必须建立一个相应的代价评估模型来评估执行计划的代价。本文在研究了代价估计方法及代价估计中的统计信息的基础上给出了连接代价评估模型。并结合多连接查询的特点,设计出一个应用遗传算法来解决多连接查询优化问题的三元模型,依据提出的优化模型,在查询策略空间上构造了遗传算法的一个原型。详细阐述了引入模拟退火思想的遗传算法求解多连接查询优化问题的具体实现过程,引入了适合多连接查询问题的树形染色体编码方法,基于该编码方法给出了交叉算子和变异算子,采用了自适应的交叉、变异概率。最后进行了仿真实验测试,实验结果验证了该算法的有效性。将本文的遗传算法与动态编程算法、贪婪算法的计划生成时间和计划执行代价分别进行了实验测试,给出了结果对比图。得出实验结论:当连接的关系个数大于8时,遗传算法的优势明显显现出来,可以用相对较少的运行时间得到近似于最优的计划。

论文目录

• 摘要
• ABSTRACT
• 创新点摘要
• 前言
• 第一章 数据库查询优化理论
• 1.1 查询处理
• 1.1.1 查询处理器
• 1.1.2 查询处理流程
• 1.2 查询优化
• 1.2.1 查询优化概述
• 1.2.2 查询优化器
• 1.3 查询优化研究的主要内容
• 1.4 查询优化的分类
• 1.5 多连接查询优化算法的研究现状
• 1.6 本章小结
• 第二章 遗传算法研究
• 2.1 遗传算法的基本思想
• 2.2 遗传算法的求解步骤
• 2.3 遗传算法的实现
• 2.3.1 问题的编码
• 2.3.2 适应度函数
• 2.3.3 遗传算子
• 2.3.4 控制参数性能分析
• 2.4 遗传算法的特点及应用
• 2.4.1 遗传算法的特点
• 2.4.2 遗传算法的应用
• 2.5 本章小结
• 第三章 多连接查询优化模型设计
• 3.1 多连接查询优化问题描述与数学模型
• 3.2 多连接查询优化的必要性
• 3.3 多连接查询的计划搜索空间
• 3.4 连接代价评估模型的建立
• 3.4.1 代价估计中的统计信息
• 3.4.2 连接运算结果的代价估计
• 3.4.3 连接运算不同取值个数的估计
• 3.4.4 代价评估数学模型的建立
• 3.5 多连接查询搜索算法比较
• 3.5.1 算法比较分析
• 3.5.2 多连接查询优化的动态编程算法设计
• 3.5.3 多连接查询优化的贪婪算法设计
• 3.6 基于遗传算法的多连接查询优化模型的设计
• 3.7 本章小结
• 第四章 多连接查询优化的遗传算法的设计与实现
• 4.1 遗传算法的详细设计
• 4.1.1 树型编码方法
• 4.1.2 连接树生成算法
• 4.1.3 适应度函数的设计
• 4.1.4 初始种群的生成
• 4.1.5 选择策略的确定
• 4.1.6 交叉算子的设计
• 4.1.7 变异算子的设计
• 4.1.8 个体的模拟退火操作
• 4.1.9 自适应的交叉、变异概率
• 4.2 算法实现流程
• 4.3 仿真实验及结果分析
• 4.3.1 实验设计
• 4.3.2 实验结果
• 4.3.3 与其它优化算法的对比分析
• 4.4 本章小结
• 结论
• 参考文献
• 发表文章目录
• 致谢
• 详细摘要