基于演化计算的多连接式并行查询优化技术研究

摘要

该文着重从另一个新的角度,使用遗传算法和与演化策略中的爬山算法分别解决多连接表达式的并行查询优化问题,并结合启发式规则并行调度的执行计划.同时提出了一种新的基于启发式规则、结合爬山算法的改进遗传算法,这种方法在一定程度上弥裤了遗传算法的局部搜索能力,能更快的收敛于最优解.文末还给出了详细的仿实验的设计,实验通过从调度策略,遗传算法的参数控制和遗传算法、爬山算法、改进的遗传算法的性能三个方面进行了深入的分析和总结.

目录

文摘

英文文摘

第一章前言

1.1并行计算机体系结构

1.2并行编程模式及并行计算在数据库系统中的应用

1.3演化计算

1.3.1演化计算的发展过程

1.3.2演化计算的主要分支

1.3.3演化计算的主要特点

1.3.4演化计算的研究内容及前景

1.4小结

第二章多连接表达式的并行查询优化问题

2.1多连接表达式的求解是一个NP完全问题

2.2并行连接算法

2.2.1并行Simple-Hash-Join算法

2.2.2并行Grace-Hash-Join算法

2.2.3并行Hybrid-Hash-Join算法

2.3对多连接表达式的并行调度策略

2.3.1顺序并行执行(SequentialParallelExecution，Sp)

2.3.2同步执行(Synchronous Execution，SE)

2.3.3分段右深树的执行(SegmentedRight-Deep Execution，RD)

2.3.4完全并行执行(Full Parallel Execution，FP)

2.4 小结

第三章遗传算法和演化策略

3.1遗传算法(GENETICALGORITHM，GA)的简介

3.2遗传算法的特点和应用

3.3遗传算法的描述

3.3.1遗传算法的形式化定义

3.3.2遗传算法的构成要素

3.4演化策略简介及其特点

3.5遗传算法和演化策略的比较

3.6爬山算法的描述

3.7 小结

第四章结合遗传算法和启发式规则的并行查询优化方法

4.1多连接表达式的编码

4.2建立优化模型

4.3设计遗传算子

4.3.1选择算子的设计

4.3.2交叉第子的设计

4.3.2变异算子的设计

4.4确定遗传算法的运行参数

4.5利用启发式规则建立多处理机并行调度的代价模型

4.5.1建立代价树

4.5.2遗传算法的多处理机并行调度的启发式规则

4.5.3代价模型

4.6小结

第五章结合爬山算法和启发式规则的并行查询优化方法

5.1问题的表示和爬山算法的搜索空间

5.2爬山算法的优化模型和运算规则

5.3爬山算法的多处理机并行调度的启发式规则

5.4结合爬山方法的改进遗传算法的并行查询优化方法

5.5 小结

第六章仿真实验的设计和性能评价

6.1仿真实验的设计和实验参数

6.2并行调度策略的对比

6.3遗传算法的参数控制

6.4爬山算法、遗传算法和改进的遗传算法的性能比较

6.5 小结

结束语

致谢

参考文献

研究生期间发表的论文目录