改进粒子群优化算法的数据库查询优化方法

王崑凌

(西安工程大学 计算机科学学院， 西安 710048)

0 引言

随着信息化技术和数据处理技术的不断发展和融合，而人们对数据管理的要求越来越高，在此背景下现了大量的数据库管理系统。近年来了，数据量不断的增加，数据库管理系统的规模越来越大，数据库的查询和更新更加复杂，其中数据库查询是最为频繁操作，而查询操作是衡量一个数据库管理系统性能好坏的一个重要指标，因此数据库的查询优化是一直数据库管理系统研究中的一个重要方向[1-3]。

为了使数据库管理系统的工作性能更优，更加稳定可靠，国内外相关学者以及专家对数据库查询优化问题进行了深入的研究，当前存在许多有效的数据库查询优化方法[4]。当前数据库查询优化方法可以划为两大数，一类为确定性的数据库查询优化方法，其包括：贪心算法、动态规划算法[5,6]，它们对数据库全部可能的查询方案进行搜索，最后形成一个完整的查询树，根据查询树得到最优数据库查询优化方案，对于小规模的数据库查询优化问题，它们可以快速、准确找到最优数据库查询优化方案，但是对于大规模的数据库查询优化问题，它们的缺陷十分明显，存在数据库查询时间长、查询效率极低等，无法满足现代数据库管理系统的查询要求[7]。另一类为随机搜索的数据库查询优化方法，主要包括：遗传算法、蚁群算法以及模拟退火算法，相对于为确定性的数据库查询优化方法，它们可以提高数据库查询的效率，而且可以得到较优的数据库查询结果[8,9]。但是在实际应用中，遗传算法、蚁群算法以及模拟退火算法均存在一定的不足，如遗传算法后期收敛速度慢，蚁群算法前期信息缺陷，搜索速度慢，模拟退火算法易陷入局部最优解[10]。

粒子群优化算法(particle swarm optimization，PSO)是一种常用随机搜索算法，其比遗传算法、蚁群算法、模拟退火算法有更好的搜索能力，为了解决当前数据库查询优化过程存在的一些缺陷，设计了改进粒子群优化算法的数据库查询优化方法。仿真对比实验结果表明，改进粒子群优化算法找到最优数据库查询优化方案的时间短，加快了数据库查询优化速度，改善提高了数据库查询结果。

2 数据库查询优化问题的描述

数据库管理系统的发展经历了几个阶段，最初采用层次性的数据库管理系统，该数据库管理系统一般是一个单位或者一个公司的局部数据管理，数据无法进行实时共享，随后出现网络数据库管理系统，通过网络将不同单位或者公司的数据库管理系统连接在一起，实现数据共熟，由于不同单位的数据结构不一样，因此这些数据库管理系统具有一定的异构性，但是由于数据爆炸式增长，人们对数据处理功能要求越来越高，网络数据库管理系统的局限性也不断体现出来，出现分布式数据库管理系统。分布式数据库管理系统是一种更加符合社会需求的数据库管理系统，数据协作、共享更加方便，是当前主要数据库管理方式。查询技术是分布式数据库管理系统的最基本操作，而查询技术包括查询处理和查询优化两个方面，本文针对查询优化进行研究。分布式数据库管理系统的查询优化目标就是查询总代价尽可能小，同时保证查询响应时间最短，其中查询总代价主要包括：输入和输出开销、存储开销、计算开销、通信开销，而查询响应时间指从接收查询命令到输出查询结果所需要的时间。一个分布式数据库系统里查询代价计算公式可以表示为式(1)。

T=I/O代价+CPU代价+通信代价

(1)

通信代价的计算公式为式(2)。

T(X)=C0+C1×X

(2)

式中，C0表示两个节点的通信时间，C1表示传输率，X表示数据传输量。

由于分布式数据库管理系统的工作环境十分复杂，查询方案有许多种，要从中搜索一种最优方案作为分布式数据库管理系统的最终查询结果，因此分布式数据库管理系统查询问题求解的原理如图1所示。

图1 数据库查询问题的求解原理

2 改进粒子群群优化算法

2.1 标准粒子群优化算法

粒子群优化算法是一种模拟受鸟群生活习性的搜索优化算法，每一个粒子均有与其相关的邻近粒子，它们的速度相同，粒子速度对优化问题的方向，但是每一个粒子的位置不一样，粒子对应优化问题的可行解，粒子均可以向任意方向进行运动，可控参数少、编码容易，在许多领域得到了成功应用[11,12]。第i个粒子的当前速度、当前位置和当前历史最优位置分别为：Xi=(xi1,xi2,…,xid)和Vi=(vi1,vi2,…,vid)；Pi=(pi1,pi2,…,pid)，整个粒子群当前的历史最优位置为：Pg=(pg1,pg2,…,pgd)，第k+1代、第i个粒子的速度和位置更新方式为式(3)、式(4)。

(3)

(4)

式中，d=1,2,…,D，D表示搜索空间维数，c1表示个体认知能力，c2表示社会认知能力；r1,r2表示0到1之间的随机数。

3.2 标准粒子群优化算法的改进

从标准粒子群优化算法的工作过程可以看出，影响算法性能为速度和位置，然而在实际应用中，还有许多其它因素会对算法的性能产生影响，这样使得标准粒子群优化算法稳定性较差，因此本文从以下几个方面对标准粒子群优化算法进行改进，以提高其工作稳定性。

(1) 引入惯性权重。将惯性权重加入到粒子飞行的速度中，用于平稳粒子的调节全局和局部搜索能力，那么式(3)变为式(5)。

(5)

式中，W表示惯性权重。

由于粒子群优化算法在工作过程中，前期全局搜索能力要强，后期局部搜索能力要强，因此惯性权重W的变化方式为式(6)。

(6)

式中，Wmax和Wmin分别表示惯性权重的最大值和最小值，iter表示粒子群的当前迭代次数，Itermax表示粒子群的最大迭代次数。

(2) 混沌方式产生初始粒子群。初始粒子群质量的好坏，影响种群的多样性，标准粒子群优化算法采用随机方式产生粒子群，到了工作后期，种群多样性变差，难以找到问题的最优解，为此本文采用混沌方式产生初始粒子群。Logistic混沌映射公式为式(7)。

(7)

式中，t表示种群序号，u表示控制参数。

当t=1,2,…,NP时，通式(7)可以产生NP个粒子初始种群，通过式(8)的逆混沌映射得到相应的变量空间为式(8)。

(8)

3 改进粒子群优化算法的数据查询优化方法具体设计

分布式数据库管理系统查询问题是一个NP难题，要从中找到最优方案十分困难，为此本文引入改进粒子群优化算法对其进行求解，以求找到最优的分布式数据库管理系统查询方案，具体步骤为：

(1) 建立分布式数据库管理系统查询方案的可行解集合。

(2) 根据混沌映射方式产生与分布式数据库管理系统查询方案的可行解数量相同的粒子群。

(3) 设迭代次数t=0，对粒子群的最大迭代次数Itermax，参数c1，c2以及Wmax和Wmin的值进行设置。

(4) 建立分布式数据库管理系统查询目标的约束条件，本文选择查询代价最小，响应时间最短。

(5) 根据分布式数据库管理系统查询目标的约束条件构建粒子的适应度函数。

(6) 根据适应度函数对每一个粒子的好坏进行衡量，找到当前最优历史位置。

(7) 根据式(6)对权值进行调整，并根据式(5)和式(4)更新粒子的速度和位置。

(8) 迭代次数t=t+1。

(9) 如果t>Itermax，就停止执行，不然返回到式(6)继续。

(10) 根据粒子群的最优位置得到最终分布式数据库管理系统查询方案。

4 数据库查询方法的性能测试

4.1 测试平台

为了测试本文的改进粒子群优化算法的数据库查询优化方法性能，采用测试平台为：AMD Ryzen 5 2600X CPU，威刚XPG DDR4 3200 8G RAM， 金士顿A1000 NVMe M.2 240G 硬盘，Linux 操作系统，编程环境为：VC++6.0，选择遗传算法、标准粒子群优化算法进行对照测试，以分析数据库查询优化结果的优劣。

4.2 结果与分析

统计所有数据库查询优化方法的查询代价和最优查询方法的生成时间，结果如图2和图3所示。

图2 数据库查询代价对比

图3 最优查询方案的生成时间对比

对比图2和图3进行分析可以知道，本文方法的数据库查询代价远远低于遗传算法、标准粒子群优化算法的数据库查询代价，得到了最优数据库查询方案更优，同时最优查询方案的生成时间更短，提高了最优查询优化效率。

统计所有数据库查询优化方法的成功率，其进行5次测试实验，每次进行100次查询，结果如表1所示。

表1 数据库查询成功率对比

从表1可知，本文方法的数据库查询成功率远远高于遗传算法、标准粒子群优化算法的数据库查询成功率，降低了数据库查询错误率，数据库查询方法的整体性能更优。

5 总结

查询优化研究一直是数据库管理领域的一个热点问题，针对当前数据库查询优化方法构建过程中存一些难题，设计了改进粒子群算法的数据库查询方法，并采用相同实例与其它数据库查询方法进行了对比测试，结果表明：

(1) 传统数据库查询方法的工作效率低、找到最优数据库查询方案的时间长，使得数据库查询代价比较大，无法适应现代数据库向大规模发展的要求。

(2) 粒子群优化算法较好的克服了当前数据库查询方法存在一些难题，找到最优数据库查询方案的时间短，有降低了数据库查询代价，得到了比较理想的数据库查询方案。

(3) 对标准粒子群优化算法进行了改进，提高了找到数据库查询最优方案的成功率，减少了数据库查询的错误率，数据库查询效果更佳，在数据库管理领域具有更加广泛的应用前景。