基于蚁群算法的分布式数据库查询优化方法

崔峰峰　南振岐

摘 要： 在分布式数据库查询优化中，数据传输和多连接次序往往决定了查询执行速度，以通信代价最小为目标的代价模型一直是研究的重点。随着大数据时代的到来，如何提高数据库的查询效率成为我们所要面对的首要问题。为此，利用蚁群算法优化查询计划，以多元连接查询操作为例，进行了模型建立和算法实现。在Oracle数据库中进行了仿真实验，实验结果表明该算法有较好的寻优效果，并对分布式数据库的查询优化具有实际意义。

关键词： 分布式数据库； 查询优化； 多元连接； 蚁群算法

中图分类号：TP319 文献标志码：A 文章编号：1006-8228（2014）05-47-03

Abstract： In the distributed database query optimization， the speed of query depends on the data transfer and join sequence. The price model minimizing communication cost is the emphasis of research. Since the era of big data is coming， the first important problem is how to enhance the speed of database query. Seeking the best query path by using the ant colony algorithm， and taking multiple connection query as an example， model building and algorithm implementation are carried on. The experimental results show that this algorithm has the better effect in selecting path and is practically meaningful for the query optimization of distribute database.

Key words： distributed database； query optimization； multiple connection； ant colony algorithm

0 引言

查询优化是分布式数据库系统中的核心问题。与集中式数据库查询相比，分布式查询处理增加了不少新的内容和复杂性。不同的查询处理方法，其查询的通信费用和并行程度是大不一样的。分布式查询优化的准则是使通信费用最低和使响应时间最短，即以最小的总代价在最短的响应时间内获得需要的数据。分布式数据库中数据的特征是：全局化和局部化。数据局部化是将一个分布式数据库上的代数查询转换成一个等价的段查询，并通过代数转换来做进一步的简化。全局查询优化通过决策操作的顺序，结点间的数据移动，以及数据库操作的分布和局部算法的选择来为输入的分段查询计划，产生一个优化的执行计划[1-2]。

文献[3]的作者提出了基于遗传算法的分布式数据库查询优化方法，并且设计了一种新的查询执行计划模型。文献[4]中提出了采用改进的最小生成树算法。本文提出了一种利用蚁群算法解决分布是数据库系统中查询优化问题的方法。此方法仍处于初期研究阶段，但初步研究已表明，应用蚁群算法进行分布式数据库的查询优化不但有效，而且具有良好的寻优能力。多元连接查询涉及多个片段上的查询，由于分布式数据库数据分布与冗余的特征，多元连接查询涉及多个不同的结点上的片段。等值连接与自然连接是应用最多的连接操作，所以我们以研究多元连接操作的查询处理为例。

1 蚁群算法原理概述

蚁群算法最初由意大利学者Dorigo.M于1991年首次提出，其本质上是一个复杂的智能系统，它具有较强的鲁棒性、优良的分布式计算机制、易于与其他方法结合等优点。目前对其研究已渗透到多个应用领域，并由解决一维静态优化问题发展到解决多维动态问题。

仿生学家的长期研究发现：蚂蚁虽没有视觉，但在运动过程中通常会释放特殊的分泌物找到路径。当它们穿过一个没有走过的路口时，则随机地选择一条路径，并在路径上释放信息素。时间越长，蚂蚁所走路径上的信息量就越小。当后来的蚂蚁再次来到此路口时，选择信息量较大的那条路经的概率就相对越大，从而形成了一个正反馈机制。最优路径上的信息量越来越大，但在其他路径上随着时间的推移，信息量会逐渐减小，整个蚁群最终会找到一条最优路径。我们用图1进行了形象的描述，以此来进一步说明蚁群的搜索原理[5]。

AE的所连接的直线上有一障碍物。由于障碍物的存在，蚂蚁只能从A经B、C或者D到达E，或者由D到达A，假设单位时间内有20只蚂蚁由A到达E点，有20只蚂蚁由E到达A点，蚂蚁所留下的信息量为2。为了便于计算，设信息素停留时间为1.5。在初始状态，由于路径AB、BC、CE、AD、DE上均无信息素存在，位于A和E点的蚂蚁可以随意选择所要走的路径，从统计学的角度可以认为蚂蚁选择路径AB、BC、AD、DE的概率是相同的。经过一个单位时间后，在路径ADE上的信息量大于路径ABCE上的信息量。又经过一段时间，将有10只蚂蚁由D点到达E。随着时间的推移，蚂蚁选择ADE的概率将会越来越大，最终将会完全选择路径ADE，从而找到蚁穴到食物所在地的最短路径。

2 分布式数据库

分布式数据库系统，通俗地说，是物理上分散而逻辑上集中的数据库系统。分布式数据库使用计算机网络将地理位置分散而管理和控制又需要不同程度集中的多个逻辑单位连接起来，共同组成一个统一的数据库系统[6]。

3 多连接查询优化问题

在分布式数据库系统中，执行一条查询语句，如果这条查询语句涉及多个表，就需要进行多元连接。由于分布式数据库物理上分散的缘故，连接的代价往往不同，因此必须找出一条最优的连接路径[1]。

在多元连接查询中再根据式⑶计算下一个关系的连接概率，将该关系的序号放入有序串。

⑹ 判断是否所有的关系都在有序序列中，若是，则这只蚂蚁的任务结束；否则，转入第⑷步继续执行。

⑺ 若种群中所有的蚂蚁都搜索完成，由式⑶计算每只蚂蚁生成的关系的连接序列的代价总和，选择代价最小的哪条路径，并在该路径上释放一定量的同位素。

⑻ 判断迭代次数是否大于等于N，若是，则结束搜索；否则，转入第⑶步进行下一次搜索操作。

⑼ 根据搜索出来的代价最小的连接顺序，做查询连接操作，得出实验结果。

5 实验及结果分析

6 结束语

查询优化问题一直是分布式数据库研究的重要方向，作者采用蚁群算法来实现多元连接的查询优化。通过代价估计模型计算连接代价作为蚁群算法中的路径权值，利用蚁群算法在寻找最优路径上的优点进行查询优化。实验结果表明，该算法不仅有效，而且当在连接元组数增多时能有更好的表现，缩减了查询时间。可以得出结论：基于蚁群算法时间多元连接查询优化，对于分布式数据库查询与设计具有实际意义。

参考文献：

[1] 郭聪莉.基于蚁群算法的多连接查询优化[J].计算机工程，2009.10：

173-175

[2] 贺宁.蚁群算法在数据库查询中的应用[J].山西电子技术，2008.1：

71-72

[3] 帅训波.基于遗传算法的分布式数据库查询优化研究[J].小型微型计

算机系统，2009.8：1600-1604

[4] 胡枫.一种分布式数据库多元连接查询优化算法及改进[J]. 计算机工

程与应用，2001.16：125-127

[5] 段海滨.蚁群算法原理及应用[M].科技出版社，2005.

[6] 邵佩英.分布式数据库系统及其引用[M].科学出版社，2000.