基于改进和声搜索群算法的数据库查询优化
高洁
摘 要： 查询优化是数据库应用的基础，针对当前数据库查询效率低，难以获得最优查询优化方案的局限性，提出基于改进和声搜索算法的数据库查询优化方法。首先对当前数据库查询优化研究现状进行分析，找出当前算法存在的一些不足；然后构建数据查询优化的数学模型，采用和声搜索算法进行求解，并对标准和声搜索算法的缺陷进行改进；最后采用VC++编程实现数据库查询优化性能测试。结果表明，该算法可以提高数据库的查询效率，尤其对大型数据库查询优化的优势更加显著。
关键词： 数据库； 数学模型； 查询优化； 和声搜索算法
中图分类号： TN911?34； TP391 文献标识码： A 文章编号： 1004?373X（2017）03?0114?03
Database query optimization based on improved harmony search algorithm
GAO Jie1， 2
（1. University of Electronic Science and Technology of China， Chengdu 611731， China；
2. Department of Modern Service， Hebei Women′s Vocational College， Shijiazhuang 050091， China）
Abstract： The database query optimization is the foundation of the database application. Since the database query has low efficiency， and it is difficult to obtain the optimal query scheme， a new database query optimization method based on improved harmony search algorithm is proposed. The research status of the database query optimization is analyzed to find out the shortcomings existing in the current algorithms. The mathematical model of the database query optimization was constructed， and solved with the harmony search algorithm. The defect of the standard harmony search algorithm was improved. The VC++ programming is used to test the performance of the database query optimization. The results show that the algorithm can improve the database query efficiency， and has more significant advantage especially for the large?scale database query optimization.
Keywords： database； mathematical model； query optimization； harmony search algorithm
0 引 言
近些年随着网络技术、数据处理技术的不断成熟和融合，出现了许多的数据库，而且数据库规模越来越庞大[1?2]。查询优化操作是数据库应用最常用的技术，查询优化效率的优劣直接决定了数据库访问结果的好坏，因此如何设计性能优异的数据库查询优化方法具有十分重要的实际应用价值[3]。
数据库查询优化问题引起了国内外研究人员的高度重视，它们采用各种技术对其进行深入分析，涌现出了大量、有效的数据库查询优化算法[3]。最原始的数据库查询优化算法基于穷尽策略，即搜索每一种可能的查询方案，找到最优的数据库查询方案，当数据库规模比较小时，其查询效率高[4]，然而对于大型数据库，由于查询条件和约束比较多，该算法的计算时间复杂度急剧上升，查询过程耗时相当长，有时甚至无法找到数据库的最优查询方案[5]。为此，有关研究人员提出了基于动态规划的数据库查询优化算法，该算法的查询效率得到了提高，但其实质上仍然采用穷举搜索策略，而对于大型数据库，查询效率低的问题仍然存在[6]。近些年，随着人工智能算法的不断成熟，有学者将遗传算法、粒子群优化算法以及蚁群优化算法[7?9]引入到数据查询优化问题的求解过程中，它们将最优或者次优数据库查询优化方案作为搜索目标，通过模拟自然界一些生物行为进行问题求解，找到数据库查询最优方案的速度明显加快，计算时间复杂度下降，成为当前数据库查询优化问题的主要解决算法[10]。相关研究表明，数据库查询优化受到多种条件约束，是一种典型的NP，这些算法的求解过程易陷入局部最优解，有时不能得到最优查询方案[11]。
和声搜索（Harmony Search，HS）算法[12]是一种模拟乐师调整音调的人工智能算法，具有控制参数少，简单易实现，收敛速度快等优点，在很大程度上防止了局部最优解的出现。为了获得更加理想的数据库查询优化结果，提出改进和声搜索算法的数据库查询优化算法（Improved Harmony Search，IHS），并采用具体实验对其性能进行测试和分析。结果表明，本文算法可以提高数据库查询效率，特别适合于大规模数据库查询问题的求解。
1 改进和声搜索算法
1.1 HS算法
HS算法是一种受到和声音乐启发的人工智能算法，模拟乐师们不断调整各种乐器的音调产生美妙的和声对问题实现求解。设乐器[（i=1，2，…，m）]为待求解问题的第[i]个决策变量，和声为待求解问题的第[j]个解向量，HS工作步骤为：
Step1：设待求解问题为最小优化问题，[f（X）]为问题的目标函数，那么问题可以描述为：
[min f（X）s.t. X∈（x1，x2，…，xN）] （1）
式中：[X]为决策变量[xi（i=1，2，…，N）]组成的解向量；[N]为变量的个数。
Step2：确定[N]的值，音调调节概率和带宽PAR和bw；决策变量取值范围为[[xLi，xUi]；]和声记忆库的规模为HMS；记忆库的概率为HMCR。
Step3： 随机生成[HMS]个和声[x1，x2，…，xHMS，]并且将它们保存在和声记忆库中，具体为：
[HM=x11x12…x1Nx21x22…x2N????xHMS1xHMS2…xHMSNf（x1）f（x2）?f（xHMS）] （2）
Step4：通过HM的学习、音调微调和随机选择音调产生新的和声[x′i=（x′1，x′2，…，x′N）]，具体如下：
[x′1]通过HMCR的概率，其值来自HM[（x′1～xHMS1）]，根据1～HMCR的概率随机产生，即：
[x′i=x′i∈（x1i，x2i，…，xHMSi）， if rand<hmcrx′i∈xi，
若[x′i]来自[HM，]那么根据式（4）对其音调进行微调。
[x1i=x′i+rand*bw， if rand<parx′i，
式中[rand]为[0，1]的随机数。
Step5： 对[x′i]进行評估，若其优于[HM]的最差解，那么将[x′i]替换为最差解，并保存到[HM]中，即：
[f（xworst）=maxj=1，2，…，HMSf（xj）if f（x）<f（xworst），
Step6：如果满足终止条件就停止运行，否则不断重复Step3和Step4。
1.2 IHS算法
相关研究结果表明，与其他人工智能算法相似，HS算法在后期出现搜索停滞、易出现“早熟”现象[13]，为此本文对其进行改进，提出IHS算法，具体思想为：引入参数WSR，其值的大小与迭代次数[k]之间是一种动态的变化关系，算法工作初期，其值较大，更新HM的最差和声，算法工作后期更新HM最优和声，可以有效避免“早熟”现象发生，加快算法的收敛速度。
为了分析IHS算法的性能，选择Griewank和Rastrigin函数进行测试，采用HS算法进行对照实验，测试结果见图1。对图1的测试结果进行对比分析可以发现，IHS算法的搜索速度明显要快于HS算法，而且解决了HS算法的“早熟”难题，证明了本文对HS算法改进的有效性。
2 GM?QPSO的数据查询优化问题求解
2.1 数学模型
数据库查询最优方案实际是一个有[n]个关系的连接树：[j1， j2，…， ji，]查询方案评估模型为：
[COST=i=1n-icost（ji）] （6）
设[R]为关系[R]的元组数；[C]为[R]和[S]的公共属性集合，[J=RjoinS，]查询代价[cost（J）]为：
[cost（J）=R×Sci∈CmaxVci，R，Vci，S] （7）
[V（c，R）]为[R]中属性[c]的取值，具体为：[V（c，J）=V（c，J）， c∈R-SV（c，S）， c∈S-Rmin（V（c，R），V（c，S））， c∈R?S1≤i1，i2，…，im<n]
2.2 IHS算法的数据库查询优化问题求解
（1） IHS参数的初始化。
（2） 设[xi=round（rand（1，N）），i=1，2，…，HMS]随机产生[HMS]个向量，即数据库查询优化问题的可行解。
（3） 计算[HM]每个和声的适应度值，并根据适应度值找到最优和最差的和声[xbest]和[xworst，]适应度计算公式为：
[f（Xi）=1cost（Xi）] （9）
（4） 确定WSR的值，具体如下所示：
[WSR=0.7×1-kTmax+0.3] （10）
式中[k]为当前迭代的次数。
（5） 产生一个随机数rand，若rand>WSR，那么表示[xworst]被选中，且有[xnew=xworst，]否则有[xnew=xbest。]
（6） 若rand<hmcr，那么新变量[xnew]来自hm中的任何一个值；否则对新变量进行音调微调。
（7） 计算[xnew]的适应度值[fnew=f（xnew），]若[xworst]被选中，且[fnew>fworst，]那么就有[xworst=xnew，]否则[xbest=xnew]。
（8） 如果达到最大迭代次数，最优和声对应的解为数据库最优查询方案，否则返回步骤（3），继续执行。
基于IHS算法的数据库查询优化流程见图2。
3 性能测试
为了分析IHS算法的数据库查询优化问题求解的有效性，采用VC++编程实现仿真实验，并选择HS算法、文献[8]算法进行对比测试，选择查询代价和执行时间（单位：s）对数据库查询最优方案进行评价，所有算法的数据库查询代价和执行时间如图3，图4所示。
对图3中各种算法的数据查询代价进行对比分析，得到如下结论：
（1） 当连接数很小时，IHS算法、HS算法以及文献[8]算法的数据库查询代价相差不大，没有太大的区别。
（2） 随着连接数不断增加，IHS算法、HS算法以及文献[8]算法的数据库查询代价也随之增加，在相同条件下，IHS算法的数据库查询代价要小于HS算法以及文献[8]算法，这是由于IHS算法加快了数据库查询优化问题的求解速度，得到了更加理想的数据库查询方案。
从图4的执行时间可以看出，相对于HS算法以及文献[8]算法，IHS算法找到数据库查询最优方案的时间大幅度减少，尤其当数据库连接数很大时，IHS算法的执行速度更快，优势更加明显，可以满足数据库查询的实时性要求，同时可以应用于网络数据库的查询，应用范围更加广泛。
4 结 语
查询效率直接影响大型数据库的应用范围，为了加快数据库查询的速度，满足数据库在线查询的实际要求，提出基于改进和声搜索算法的数据库查询优化算法，实验结果表明，本文算法可以很快找到数据库查询的最优结果，有效提高了数据库的查询效率，尤其对于大型数据库查询的优越性更加明显，可以应用于实际的数据库系统中。
参考文献
[1] 张敏，冯登国，徐震.多级多版本数据库管理系统全局串行化[J].软件学报，2007，18（2）：346?347.
[2] 张丽平，李松，郝忠孝.球面上的最近邻查询方法研究[J].计算机工程与应用，2011，47（5）：126?129.
[3] 帅训波，马书南，周相广，等.基于遗传算法的分布式数据库查询优化研究[J].小型微型计算机系统，2009，30（8）：1600?1604.
[4] ZHOU Zehai. Using heuristics and genetic algorithms for large scale database query optimization [J]. Journal of information and computing science， 2007， 2（4）： 261?280.
[5] CHEN P H， SHAHANDASHTI S M. Hybrid of genetic algorithm and simulated annealing for multiple project scheduling with multiple resource constraints [J]. Automation in construction， 2009， 18（4）： 434?443.
[6] 郭聪莉，朱莉，李向.基于蚁群算法的多连接查询优化方法[J].计算机工程，2009，35（10）：173?176.
[7] 林桂亚.基于粒子群算法的数据库查询优化[J].计算机应用研究，2012，29（3）：974?975.
[8] 郑先锋，王丽艳.自适应逃逸动量粒子群算法的数据库多连接查询优化[J].四川大学学报（自然科学版），2013，50（3）：100?103.
[9] 于洪涛，钱磊.一种改进的分布式查询优化算法[J].计算机工程与应用，2013，49（8）：151?155.
[10] 徐增敏，张昆，丁勇，等.基于动态视图的数据库性能调优[J].计算机应用与软件，2012，29（12）：58?60.
[11] 林键，刘仁义，刘南，等.基于查询优化器的分布式空间查询优化方法[J].计算机工程与应用，2012，48（22）：161?165.
[12] GEEM Z W， KIM J H， LOGANATHAN G V. A new heuristic optimization algorithm： harmony search [J]. Simulation， 2001， 76（2）： 60?68.
[13] OMRAN M， MAHDAV M. Global?best harmony search [J]. Applied mathematics and computation， 2008， 198（2）： 643?656.
摘 要： 查询优化是数据库应用的基础，针对当前数据库查询效率低，难以获得最优查询优化方案的局限性，提出基于改进和声搜索算法的数据库查询优化方法。首先对当前数据库查询优化研究现状进行分析，找出当前算法存在的一些不足；然后构建数据查询优化的数学模型，采用和声搜索算法进行求解，并对标准和声搜索算法的缺陷进行改进；最后采用VC++编程实现数据库查询优化性能测试。结果表明，该算法可以提高数据库的查询效率，尤其对大型数据库查询优化的优势更加显著。
关键词： 数据库； 数学模型； 查询优化； 和声搜索算法
中图分类号： TN911?34； TP391 文献标识码： A 文章编号： 1004?373X（2017）03?0114?03
Database query optimization based on improved harmony search algorithm
GAO Jie1， 2
（1. University of Electronic Science and Technology of China， Chengdu 611731， China；
2. Department of Modern Service， Hebei Women′s Vocational College， Shijiazhuang 050091， China）
Abstract： The database query optimization is the foundation of the database application. Since the database query has low efficiency， and it is difficult to obtain the optimal query scheme， a new database query optimization method based on improved harmony search algorithm is proposed. The research status of the database query optimization is analyzed to find out the shortcomings existing in the current algorithms. The mathematical model of the database query optimization was constructed， and solved with the harmony search algorithm. The defect of the standard harmony search algorithm was improved. The VC++ programming is used to test the performance of the database query optimization. The results show that the algorithm can improve the database query efficiency， and has more significant advantage especially for the large?scale database query optimization.
Keywords： database； mathematical model； query optimization； harmony search algorithm
0 引 言
近些年随着网络技术、数据处理技术的不断成熟和融合，出现了许多的数据库，而且数据库规模越来越庞大[1?2]。查询优化操作是数据库应用最常用的技术，查询优化效率的优劣直接决定了数据库访问结果的好坏，因此如何设计性能优异的数据库查询优化方法具有十分重要的实际应用价值[3]。
数据库查询优化问题引起了国内外研究人员的高度重视，它们采用各种技术对其进行深入分析，涌现出了大量、有效的数据库查询优化算法[3]。最原始的数据库查询优化算法基于穷尽策略，即搜索每一种可能的查询方案，找到最优的数据库查询方案，当数据库规模比较小时，其查询效率高[4]，然而对于大型数据库，由于查询条件和约束比较多，该算法的计算时间复杂度急剧上升，查询过程耗时相当长，有时甚至无法找到数据库的最优查询方案[5]。为此，有关研究人员提出了基于动态规划的数据库查询优化算法，该算法的查询效率得到了提高，但其实质上仍然采用穷举搜索策略，而对于大型数据库，查询效率低的问题仍然存在[6]。近些年，随着人工智能算法的不断成熟，有学者将遗传算法、粒子群优化算法以及蚁群优化算法[7?9]引入到数据查询优化问题的求解过程中，它们将最优或者次优数据库查询优化方案作为搜索目标，通过模拟自然界一些生物行为进行问题求解，找到数据库查询最优方案的速度明显加快，计算时间复杂度下降，成为当前数据库查询优化问题的主要解决算法[10]。相关研究表明，数据库查询优化受到多种条件约束，是一种典型的NP，这些算法的求解过程易陷入局部最优解，有时不能得到最优查询方案[11]。
和声搜索（Harmony Search，HS）算法[12]是一种模拟乐师调整音调的人工智能算法，具有控制参数少，简单易实现，收敛速度快等优点，在很大程度上防止了局部最优解的出现。为了获得更加理想的数据库查询优化结果，提出改进和声搜索算法的数据库查询优化算法（Improved Harmony Search，IHS），并采用具体实验对其性能进行测试和分析。结果表明，本文算法可以提高数据库查询效率，特别适合于大规模数据库查询问题的求解。
1 改进和声搜索算法
1.1 HS算法
HS算法是一种受到和声音乐启发的人工智能算法，模拟乐师们不断调整各种乐器的音调产生美妙的和声对问题实现求解。设乐器[（i=1，2，…，m）]为待求解问题的第[i]个决策变量，和声为待求解问题的第[j]个解向量，HS工作步骤为：
Step1：设待求解问题为最小优化问题，[f（X）]为问题的目标函数，那么问题可以描述为：
[min f（X）s.t. X∈（x1，x2，…，xN）] （1）
式中：[X]为决策变量[xi（i=1，2，…，N）]组成的解向量；[N]为变量的个数。
Step2：确定[N]的值，音调调节概率和带宽PAR和bw；决策变量取值范围为[[xLi，xUi]；]和声记忆库的规模为HMS；记忆库的概率为HMCR。
Step3： 随机生成[HMS]个和声[x1，x2，…，xHMS，]并且将它们保存在和声记忆库中，具体为：
[HM=x11x12…x1Nx21x22…x2N????xHMS1xHMS2…xHMSNf（x1）f（x2）?f（xHMS）] （2）
Step4：通过HM的学习、音调微调和随机选择音调产生新的和声[x′i=（x′1，x′2，…，x′N）]，具体如下：
[x′1]通过HMCR的概率，其值来自HM[（x′1～xHMS1）]，根据1～HMCR的概率随机产生，即：
[x′i=x′i∈（x1i，x2i，…，xHMSi）， if rand<hmcrx′i∈xi，
若[x′i]来自[HM，]那么根据式（4）对其音调进行微调。
[x1i=x′i+rand*bw， if rand<parx′i，
式中[rand]为[0，1]的随机数。
Step5： 对[x′i]进行評估，若其优于[HM]的最差解，那么将[x′i]替换为最差解，并保存到[HM]中，即：
[f（xworst）=maxj=1，2，…，HMSf（xj）if f（x）<f（xworst），
Step6：如果满足终止条件就停止运行，否则不断重复Step3和Step4。
1.2 IHS算法
相关研究结果表明，与其他人工智能算法相似，HS算法在后期出现搜索停滞、易出现“早熟”现象[13]，为此本文对其进行改进，提出IHS算法，具体思想为：引入参数WSR，其值的大小与迭代次数[k]之间是一种动态的变化关系，算法工作初期，其值较大，更新HM的最差和声，算法工作后期更新HM最优和声，可以有效避免“早熟”现象发生，加快算法的收敛速度。
为了分析IHS算法的性能，选择Griewank和Rastrigin函数进行测试，采用HS算法进行对照实验，测试结果见图1。对图1的测试结果进行对比分析可以发现，IHS算法的搜索速度明显要快于HS算法，而且解决了HS算法的“早熟”难题，证明了本文对HS算法改进的有效性。
2 GM?QPSO的数据查询优化问题求解
2.1 数学模型
数据库查询最优方案实际是一个有[n]个关系的连接树：[j1， j2，…， ji，]查询方案评估模型为：
[COST=i=1n-icost（ji）] （6）
设[R]为关系[R]的元组数；[C]为[R]和[S]的公共属性集合，[J=RjoinS，]查询代价[cost（J）]为：
[cost（J）=R×Sci∈CmaxVci，R，Vci，S] （7）
[V（c，R）]为[R]中属性[c]的取值，具体为：[V（c，J）=V（c，J）， c∈R-SV（c，S）， c∈S-Rmin（V（c，R），V（c，S））， c∈R?S1≤i1，i2，…，im<n]
2.2 IHS算法的数据库查询优化问题求解
（1） IHS参数的初始化。
（2） 设[xi=round（rand（1，N）），i=1，2，…，HMS]随机产生[HMS]个向量，即数据库查询优化问题的可行解。
（3） 计算[HM]每个和声的适应度值，并根据适应度值找到最优和最差的和声[xbest]和[xworst，]适应度计算公式为：
[f（Xi）=1cost（Xi）] （9）
（4） 确定WSR的值，具体如下所示：
[WSR=0.7×1-kTmax+0.3] （10）
式中[k]为当前迭代的次数。
（5） 产生一个随机数rand，若rand>WSR，那么表示[xworst]被选中，且有[xnew=xworst，]否则有[xnew=xbest。]
（6） 若rand<hmcr，那么新变量[xnew]来自hm中的任何一个值；否则对新变量进行音调微调。
（7） 计算[xnew]的适应度值[fnew=f（xnew），]若[xworst]被选中，且[fnew>fworst，]那么就有[xworst=xnew，]否则[xbest=xnew]。
（8） 如果达到最大迭代次数，最优和声对应的解为数据库最优查询方案，否则返回步骤（3），继续执行。
基于IHS算法的数据库查询优化流程见图2。
3 性能测试
为了分析IHS算法的数据库查询优化问题求解的有效性，采用VC++编程实现仿真实验，并选择HS算法、文献[8]算法进行对比测试，选择查询代价和执行时间（单位：s）对数据库查询最优方案进行评价，所有算法的数据库查询代价和执行时间如图3，图4所示。
对图3中各种算法的数据查询代价进行对比分析，得到如下结论：
（1） 当连接数很小时，IHS算法、HS算法以及文献[8]算法的数据库查询代价相差不大，没有太大的区别。
（2） 随着连接数不断增加，IHS算法、HS算法以及文献[8]算法的数据库查询代价也随之增加，在相同条件下，IHS算法的数据库查询代价要小于HS算法以及文献[8]算法，这是由于IHS算法加快了数据库查询优化问题的求解速度，得到了更加理想的数据库查询方案。
从图4的执行时间可以看出，相对于HS算法以及文献[8]算法，IHS算法找到数据库查询最优方案的时间大幅度减少，尤其当数据库连接数很大时，IHS算法的执行速度更快，优势更加明显，可以满足数据库查询的实时性要求，同时可以应用于网络数据库的查询，应用范围更加广泛。
4 结 语
查询效率直接影响大型数据库的应用范围，为了加快数据库查询的速度，满足数据库在线查询的实际要求，提出基于改进和声搜索算法的数据库查询优化算法，实验结果表明，本文算法可以很快找到数据库查询的最优结果，有效提高了数据库的查询效率，尤其对于大型数据库查询的优越性更加明显，可以应用于实际的数据库系统中。
参考文献
[1] 张敏，冯登国，徐震.多级多版本数据库管理系统全局串行化[J].软件学报，2007，18（2）：346?347.
[2] 张丽平，李松，郝忠孝.球面上的最近邻查询方法研究[J].计算机工程与应用，2011，47（5）：126?129.
[3] 帅训波，马书南，周相广，等.基于遗传算法的分布式数据库查询优化研究[J].小型微型计算机系统，2009，30（8）：1600?1604.
[4] ZHOU Zehai. Using heuristics and genetic algorithms for large scale database query optimization [J]. Journal of information and computing science， 2007， 2（4）： 261?280.
[5] CHEN P H， SHAHANDASHTI S M. Hybrid of genetic algorithm and simulated annealing for multiple project scheduling with multiple resource constraints [J]. Automation in construction， 2009， 18（4）： 434?443.
[6] 郭聪莉，朱莉，李向.基于蚁群算法的多连接查询优化方法[J].计算机工程，2009，35（10）：173?176.
[7] 林桂亚.基于粒子群算法的数据库查询优化[J].计算机应用研究，2012，29（3）：974?975.
[8] 郑先锋，王丽艳.自适应逃逸动量粒子群算法的数据库多连接查询优化[J].四川大学学报（自然科学版），2013，50（3）：100?103.
[9] 于洪涛，钱磊.一种改进的分布式查询优化算法[J].计算机工程与应用，2013，49（8）：151?155.
[10] 徐增敏，张昆，丁勇，等.基于动态视图的数据库性能调优[J].计算机应用与软件，2012，29（12）：58?60.
[11] 林键，刘仁义，刘南，等.基于查询优化器的分布式空间查询优化方法[J].计算机工程与应用，2012，48（22）：161?165.
[12] GEEM Z W， KIM J H， LOGANATHAN G V. A new heuristic optimization algorithm： harmony search [J]. Simulation， 2001， 76（2）： 60?68.
[13] OMRAN M， MAHDAV M. Global?best harmony search [J]. Applied mathematics and computation， 2008， 198（2）： 643?656.
