刘 东

LIU Dong

陕西理工学院 物理与电信工程学院，陕西 汉中 723001

School of Physics and Communication Engineering,Shaanxi University of Technology,Hanzhong,Shaanxi 723001,China

1 引言

随着数据库技术成熟和应用范围的扩大，出现了许多大规模数据库，而查询优化是提高数据库性能的关键技术之一，因此针对一个查询问题，如何找到一种最优查询计划至关重要，成为数据库研究中的重要课题[1-2]。

找到数据库的最优查询计划就是要构造一棵代价最小的多连接查询树，为此针对数据库查询优化问题，国内外学者从不同角度做了大量的工作，提出许多查询优化算法[3]。最传统的查询优化算法采用穷尽搜索算法或其他变形算法，当连接关系数目较小时，可以取得较好的查询效果，但现代数据库管理系统的查询连接数目通常很大，这类算法毫无用处，没有什么实际应用价值[4]。随后有学者提出动态规划算法解决数据库查询优化问题，但查询效率低，不能满足现代数据库查询要求[5]。大量研究表明，数据库查询优化包括了许多约束条件，实质上是一个组合优化问题，群智能算法具有搜索速度快的优点，因此一些学者将群智能算法应用于数据库查询优化问题的求解中[5]。文献[6]等提出一种基于遗传算法的数据库查询优化方法，采用遗传算法对查询执行计划代价进行求解，取得了不错的效果。Kumar等人根据查询数据关联度之间的关系，提出一种基于遗传算法的数据库查询优化方法[7]。遗传算法虽然具有寻优能力强的优点，但是对于不同问题需要设置不同的遗传算子，存在局部搜索能力差等不足[8]。……