一种基于萤火虫算法的数据库多表连接查询优化方法

本发明涉及数据库领域，尤其涉及一种基于萤火虫算法的数据库多表连接查询优 化方法。

随着大规模数据库和数据仓库的出现，数据库规模日益增大，数据查询频率增加， 如何 到满足用户查询要求方案，提高数据库查询效率，成为当前研究的热点问题。

查询优化是数据库应用的基础，多连接查询优化问题是一个NP问题，但都不能保 证能 在有限的时间内给出一个最优的执行计划。针对数据库查询效率低，难以获得最佳查 询优化 方案的局限性，一些学者将启发式算法引入到数据库查询中。

目前，数据库查询优化方法中，通常所采用的方法有：1.传统的穷尽搜索算法2.确 定算 法，如动态规划算法、贪心算法；3.随机优化算法，如遗传算法，粒子算法，蚁算法 等。

现有的转化方法存在一定的缺陷，大概表示为：

1.传统的穷尽搜索算法无法对包含的关系个数太大的查询进行优化。

2.确定算法中，动态规划算法不适用于复杂的多连接查询的优化，贪心算法只能 求得当 前意义上的局部最优解。

3.随机优化算法中，不能保证一定能得到问题的最优解，但能得到近似最优解，可 以提 高查询优化效率，但在算法后期可能出现收敛速度慢，易陷入局部最优解等。

数据库多表连接查询优化是提高数据库性能的关键技术，为了提高数据库多表连 接查询 效率，提出了一种基于萤火虫算法的数据库多表连接查询优化方法，通过萤火虫算 法寻最 佳查询执行计划，提高了数据库多表连接查询效率。

数据库的主要功能是存储和管理数据，向用户提供查询功能。针对数据库多表连 接查询 效率低，算法后期易陷入局部最优解的问题，本发明提供一种基于萤火虫算法的数 据库多表 连接查询优化方法，通过萤火虫算法寻最佳查询执行计划，对数据库查询执行 计划进行优 化，提高了数据库多表连接查询效率。

为了实现上述目的，本发明采用了如下技术方案：

1.定义数据库的搜索空间，建立数据库多表连接查询优化代价模型；

2.在左深树组成的解空间中，使用后续遍历连接树得到编码序列；

3.定义适应度函数；

4.应用萤火虫算法寻最佳查询执行计划；

5.满足结束条件，输出最佳查询执行计划。

其中，应用萤火虫算法寻最佳查询执行计划，在本发明中算法步骤包括：

(1)初始化算法基本参数，设置萤火虫数目n，最大吸引度β0，光强吸收系数γ，步 长因 子α，最大迭代次数MaxGeneration或搜索精度ε；

(2)随机初始化萤火虫的位置，根据适应度函数计算萤火虫的适应度值作为其最 大荧光强 度I0；

(3)计算萤火虫的相对亮度I和吸引度β，比较所属邻域内萤火虫的荧光亮度大小， 根据相 对亮度决定萤火虫的移动方向；

(4)根据引入的线性递减权重函数和引入自适应补偿机制，更新萤火虫的位置；

(5)对处在最佳位置的萤火虫，如果最优值连续三次没有更新，可能陷入局部最 优，则对 最优萤火虫的位置进行随机扰动，加入一个服从高斯分布的随机扰动，可以使算 法跳出局部 最优；

(6)根据更新后萤火虫的位置，重新计算萤火虫的亮度；

(7)如果满足终止条件，输出全局极值点和最优个体值，最优萤火虫位置对应的数 据库最 佳查询执行计划，否则，搜索次数增加1，转第(3)步，进行下一次搜索。

图1为本发明实施例提供的一种基于萤火虫算法的数据库多表连接查询优化方法 的流程 图；

图2为本发明实施例提供的一种萤火虫算法寻最佳查询执行计划的算法流程 图。

为了使本发明的目的、技术方案及优点更加清楚明白，以下将参照附图并结合实 例对本 发明作进一步描述，应当理解，此处所描述的具体实施例仅仅用以解释本发明，并 不用于限 定本发明。

本发明实施例中，定义数据库的搜索空间，建立数据库查询优化代价模型；在左深 树组 成的解空间中，使用后续遍历连接树得到编码序列；定义适应度函数；应用萤火虫算 法寻 最佳查询执行计划；满足结束条件，输出最佳查询执行计划。其中，应用萤火虫算法 寻最 佳查询执行计划算法步骤包括：(1)初始化算法基本参数，设置萤火虫数目n，最大 吸引度β0， 光强吸收系数γ，步长因子α，最大迭代次数MaxGeneration或搜索精度ε；(2)随 机初始化萤 火虫的位置，根据适应度函数计算萤火虫的适应度值作为其最大荧光强度I0； (3)计算萤火虫 的相对亮度I和吸引度β，比较所属邻域内萤火虫的荧光亮度大小，根据相 对亮度决定萤火虫 的移动方向；(4)根据引入的线性递减权重函数和引入自适应补偿机 制，更新萤火虫的位置； (5)对处在最佳位置的萤火虫，如果最优值连续三次没有更新，可 能陷入局部最优，则对最优 萤火虫的位置进行随机扰动，加入一个服从高斯分布的随机扰 动，可以使算法跳出局部最优； (6)根据更新后萤火虫的位置，重新计算萤火虫的亮度；(7) 如果满足终止条件，输出全局极值 点和最优个体值，最优萤火虫位置对应的数据库最佳查 询执行计划，否则，搜索次数增加1， 转第(3)步，进行下一次搜索。

为了说明本发明所述的技术方案，下面通过具体实施例来进行说明。

图1为本发明实施例提供的一种基于萤火虫算法的数据库多表连接查询优化方法 的流程 图。参照图1，本发明实施例提供一种基于萤火虫算法的数据库多表连接查询优化 方法，所 述方法包括：

1.定义数据库的搜索空间，建立数据库查询优化代价模型；

2.在左深树组成的解空间中，使用后续遍历连接树得到编码序列；

3.定义适应度函数；

4.应用萤火虫算法寻最佳查询执行计划；

5.满足结束条件，输出最佳查询执行计划。

其中，步骤4应用萤火虫算法寻最佳查询执行计划包括以下内容，参照图2。图2 为 本发明实施例提供的一种萤火虫算法寻最佳查询执行计划的算法流程图。参照图2， 本发 明实施例提供一种应用萤火虫算法寻最佳查询执行计划方法，所述方法步骤包括：

(1)初始化算法基本参数，设置萤火虫数目n，最大吸引度β0，光强吸收系数γ，步 长因 子α，最大迭代次数MaxGeneration或搜索精度ε；

(2)随机初始化萤火虫的位置，根据适应度函数计算出萤火虫的适应度值作为其 最大荧光 强度I0；

(3)计算萤火虫的相对亮度I和吸引度β，比较所属邻域内萤火虫的荧光亮度大小， 根据 相对亮度决定萤火虫的移动方向；

(4)根据引入的线性递减权重函数和引入自适应补偿机制，更新萤火虫的位置；

(5)对处在最佳位置的萤火虫，如果最优值连续三次没有更新，可能陷入局部最 优，则对 最优位置的萤火虫进行随机扰动，加入一个服从高斯分布的随机扰动，可以使算 法跳出局部 最优；

(6)根据更新后萤火虫的位置，重新计算萤火虫的亮度；

(7)如果满足终止条件，输出全局极值点和最优个体值，最优萤火虫位置对应的数 据库最 佳查询执行计划，否则，搜索次数增加1，转第(3)步，进行下一次搜索。

上述步骤1中，定义数据库的搜索空间，建立数据库查询优化代价模型。一个查询 对应 的所有的查询执行计划构成了该查询的策略空间，策略空间的大小由遵循的等价转 换规则集 和查询执行引擎支持的物理操作集决定。由于策略空间一般都很大，因此，查询 优化算法通 常不会在整个策略空间里进行搜索，而是在一个最佳执行计划可能存在的策 略空间子集中进 行搜索，即搜索空间进行。因为左深树空间是策略空间的一个相当小的子 集，而且左深树空 间常常包含着最佳的执行计划，至少也包含着较好的近似最优解。又因 为左深树空间需要的 存储空间，远远比右深树所需的存储空间小，所以常采用较优的左深 树空间来简化优化问题 的求解。

数据库多表查询的过程中会涉及到多个关系表，不同表之间的连接顺序会导致查 询计划 的多样性。对于n个表，左、右深树都含有n的阶乘个查询计划，查询优化就是到一 条最 小查询代价的执行计划。

假设一个含有n个关系R＝{r1,r2,…,rn}的连接树，其语法树的内部节点个数为 ti，则查询 的执行代价即为语法树内部节点个数的总和。

对于一个多连接查询语句，S为所有的用户提供的查询语句有相同结果的查询策 略的集 合，那么这个集合中查询执行代价最小的查询语句就是最优的查询计划。

cos t(s0)＝Min(cos t(s)),s∈S

其中，r₁,r₂,…,r_i∈R，i＝1,2,…,n-1。

上述步骤2中，在左深树组成的解空间中，使用后续遍历连接树得到编码序列。

本实施例采用左线性树空间作为搜索空间，数据库多连接查询优化问题可以简单 地描述 为：以顶点集V中所有的顶点作为叶节点构造一棵最小代价的二叉树，每个顶点出 现且仅出 现一次。基于左线性空间多连接查询优化问题，考虑到查询执行计划在时间和空 间上的复杂 性，并且其代价的评估取决于操作结果集的记录数目，所以将连接查询优化问 题简化为查询 中n个表(关系)的join树连接次序的逻辑优化问题，这样多连接查询优化问 题就转化成类似典 型的TSP问题。

上述步骤3中，定义适应度函数，算法中，用萤火虫的绝对亮度表征萤火虫所在位 置处 的目标函数值。使用适应度来衡量体中各个萤火虫在优化计算中有可能达到或接 近于最优 解的优良程度，从而得到下一步的搜索信息，度量个体适应度的函数就是适应函 数。

适应函数可以分为简单适应函数、线性加速适应函数、非线性加速适应函数和排 序适应 函数。通常都倾向于使用简单的适应函数，本文也应用简单的适应函数。

适应度函数直接影响者萤火虫算法的收敛情况。查询优化的目标是要获得代价 cost(t)最 小的执行计划，因此萤火虫个体的适应度函数必须与代价cost(X)相关，因此适 应度值函数定 义如下：

即首先计算萤火虫的执行代价，再对所求得的值取倒数即为适应度函数值。当萤 火虫的 执行代价越小时，适应度越高，那么查询的效果越好。

上述步骤4中，应用萤火虫算法寻最佳查询执行计划，通过引入萤火虫算法可以 寻 数据库多表连接最佳查询执行计划。

在上述步骤(1)中，初始化算法基本参数，设置萤火虫数目n，最大吸引度β0，光强 吸收 系数γ，步长因子α，最大迭代次数MaxGeneration或搜索精度ε。

其中，β0为最大吸引力，即在光源处(r＝0处)萤火虫的吸引力,取β0＝1；

γ为光吸收系数，标志了吸引力的变化，它的值对萤火虫算法的收敛速度和优化 效果有 很大的影响，对于大部分的问题，可以取γ∈[0.01,100]；

α为常数，一般可以取α∈[0,1]；

本实施例中，取β₀＝1.0，γ＝1.0，α＝1.0，其中rand是在[0,1]上均匀分布 的随机数。

上述步骤(2)中，在求解空间内随机初始化萤火虫的位置，根据适应度函数计算萤 火虫的 适应度值作为其最大荧光强度Ii。

在该解空间中，萤火虫算法随机地初始化一萤火虫xi(i＝1,2,…,n)，n为萤火 虫的个数， xi＝(xi1,xi2,…,xid)是一个D维向量，表示萤火虫i在解空间中的位置，可以代 表该问题的一 个潜在解。

根据初始位置计算适应度值，并将其作为萤火虫的最大荧光强度I0。

上述步骤(3)中，计算萤火虫的相对亮度I和吸引度β，比较所属邻域内萤火虫的荧 光亮 度大小，根据相对亮度决定萤火虫的移动方向。

相对荧光亮度为：其中，I₀表示第i只萤火虫最大荧光亮度；λ为光强 度吸收系数；相互吸引度β决定了萤火虫移动的距离，定义为：

其中，β0表示最大吸引度，即光源处(r＝0处)的吸引度。

r_ij为萤火虫i与j之间的距离，定义为:

上述步骤(4)中，根据引入的线性递减权重函数和引入自适应补偿机制，更新萤火 虫的位 置。

在萤火虫算法中，由于被萤火虫i吸引，萤火虫j向其移动而更新自己的位置，j位 置更 新公式如下：

xj(t+1)＝xj(t)+βij(rij)(xi(t)-xj(t))+αεj

式中：t为算法的迭代次数，x_i，x_j为第i和第j个萤火虫所处的空间位置；α为步长因 子；其中rand是在[0,1]上均匀分布的随机数。

标准的萤火虫算法在算法迭代后期，由于萤火虫已经逐渐移动到局部或者全局极值点的 附近，此时萤火虫之间的距离逐渐缩小，萤火虫之间的吸引度逐渐增大，将会使萤火虫个体 的移动距离过大而无法到达或者错过最优位置，造成在极值点附近震荡的问题，因此本实施 例中引入线性递减权重函数

同时由于算法设计的萤火虫移动步长是固定的α，不利于算法后期求解局部最优 值，而 步长自适应调整有利于提高求解的精度和收敛速度。因此引入自适应补偿机制，步 长因子α取 值影响萤火虫算法的收敛性能影响，可进一步提高算法收敛速度和全局寻优能 力，在寻优过 程中采用自适应变步长机制：初期α值较大，提高全局寻优能力；随着迭代次 数增加，逐步减 小α值，加快后期收敛速度，具体调整方式为：α＝α×Δα，式中，Δα为步长 步长衰减系数， 在(0.95,1)内取值。

位置公式更新为：

xj(t+1)＝w(t)xj(t)+βij(rij)(xi(t)-xj(t))+α×Δαεj

其中，x，I分为萤火虫位置和亮度。

通过惯性权重可以控制萤火虫上一次位置信息对当前位置的影响，权重大小决定 了萤火 虫移动的距离大小，并加强了萤火虫算法的全局寻优和局部搜索能力。

在上述步骤(5)中，对处在最佳位置的萤火虫，若最优值连续三次没有更新，可能 陷入局 部最优，则对最优萤火虫的位置进行随机扰动，加入一个服从高斯分布的随机扰 动，可以使 算法跳出局部最优。

采用高斯变异因子对该子进行扰动。高斯分布是一种工程常用的重要概率分布，其概 率密度函数下式所示：式中，σ为高斯分布的方差，μ为期望。对萤 火虫体的状态进行高斯变异处理，x_i＝x_i+x_i×N(μ,σ)。

在上述步骤(6)中，根据更新后萤火虫的位置，重新计算萤火虫的亮度。

当萤火虫可能陷入局部最优后，对萤火虫加入高斯扰动，加入高斯扰动过后，重新 更新 萤火虫的位置，通过把萤火虫新的位置带人到目标函数中，重新计算萤火虫亮度。

在上述步骤(7)中，如果满足终止条件，输出全局极值点和最优个体值，最优萤火 虫位置 对应数据库最佳查询执行计划，否则，搜索次数增加1，转第5步，进行下一次搜索。

在上述步骤5中，满足结束条件，输出最佳查询执行计划，当使用萤火虫算法搜索 最佳 查询执行计划时，当满足终止条件如达到最大的迭代次数等，结束搜索，输出结果， 到最 佳查询执行计划，完成数据库多表连接的查询优化。