基于基因算法的大型关系数据库查询优化技术研究

摘要

随着数据库技术的迅速发展和信息系统的广泛应用,企业管理效率提高的同时也促成了海量数据的积累,一些大规模的系统,如证券、银行和人口统计等系统的数据量甚至超过了TB级。从大多数系统的应用实例来看,查询操作在各种数据库操作中所占比重最大,但在进行访问查询时,会遇到系统响应时间过长,占用系统资源过多等问题,查询速度已成为影响系统性能的重要瓶颈。常规算法在处理查询优化问题时都有着自身无法克服的局限性。例如:穷尽搜索算法所优化的关系数目不能太多,否则效率会急剧下降;启发式算法不一定得到最优解;局部随机搜索算法容易陷入局部最优化的陷阱中;一般的全局搜索算法又太过于依赖“代价函数分布曲面”。因此,本文在大型关系数据库查询优化中引入基因算法,来更好的解决大型数据库的查询优化问题。论文所做的工作如下:①分析了目前国内外针对关系数据库查询优化的研究成果,并对查询优化必要性进行了论证。②重点研究了查询优化器的结构、模块功能和工作原理;重点分析了查询重写和计划优化阶段的作用。③研究了多连接查询优化的原理和执行引擎的相关理论,分析了常见的搜索算法,并对它们的特点进行了总结。④研究了基因算法理论及其关键技术,并对变异算子进行改进,提出使用两种变异算子,克服了在树型编码中交叉算子生成新个体能力不足的问题,最后把基因算法和其它搜索算法进行比较。⑤根据基因算法的特点,设计出一个基于基因算法的多连接查询优化模型,并对该模型进行分析测试。结果证明使用基因算法的查询效率比使用其它普通算法的查询效率有明显的提高。

目录

中文摘要

英文摘要

1 引言

1.1 论文选题背景

1.2 国内外研究现状

1.3 本文的组织结构

2 查询优化技术综述

2.1 查询优化技术的相关知识

2.1.1 关系查询语言

2.1.2 查询语句分类

2.1.3 查询优化的技术

2.1.4 查询优化的主要内容

2.2 查询优化的必要性

3 查询优化器

3.1 查询优化的原则

3.2 查询处理步骤

3.3 关于执行引擎的基本理论

3.3.1 执行引擎概述

3.3.2 物理查询计划操作符

3.3.3 针对单个操作符的算法

3.3.4 表达式的计算

3.4 查询优化器的结构

3.4.1 结构概览

3.4.2 模块功能

3.5 查询重写阶段

3.5.1 查询重写的目标

3.5.2 视图重写

3.5.3 子查询合并

3.5.4 等价谓词重写

3.6 计划优化阶段

3.6.1 存取路径的选取

3.6.2 访问代价估计

3.6.3 算法策略空间的选取

3.6.4 计划树

3.6.5 查询条件处理

3.7 查询优化器的工作原理

4 多连接查询优化的算法设计

4.1 多连接的查询优化

4.1.1 多连接查询优化问题的图论描述

4.1.2 影响多连接查询优化的因素

4.2 组合优化问题

4.2.1 组合优化问题概述

4.2.2 多连接查询优化与TSP 问题

4.3 搜索策略的算法研究

4.3.1 穷尽搜索算法

4.3.2 启发式算法

4.3.3 局部随机搜索算法

4.3.4 全局随机搜索算法

5 基因算法

5.1 基因算法简介

5.2 模板理论

5.3 基因算法实现的关键技术

6 多连接查询优化的基因算法设计模型

6.1 设计模型

6.2 基于左深树空间的基因算法设计与实现

6.2.1 编码

6.2.2 适应度函数

6.2.3 选择策略确定

6.2.4 基因算子的确定

6.2.5 控制参数的选取

6.2.6 确定算法的终止准则

6.2.7 算法主程序框图和算法设计

6.3 实验结果与分析

6.3.1 程序运行环境

6.3.2 实验的设计

6.3.3 实验结果分析

7 结论与展望

致谢

参考文献

附录