基于并行遗传最大最小蚁群算法的分布式数据库查询优化

来源：计算机应用杂志2016年第3期北京时间：

作者：林基明, 班文娇, 王俊义, 童记超

单位：1. 桂林电子科技大学 信息与通信学院, 广西 桂林 541004;2. 桂林电子科技大学 广西密码学与信息安全重点实验室, 广西 桂林 541004

摘要：针对分布式数据库中关系及其分片多副本、多站点存储的特性会增加查询搜索空间及时间复杂度,从而降低查询执行计划(QEP)搜索效率的问题,提出一种基于分片分配选择器(FSS)设计准则的并行遗传-最大最小蚁群算法(PGA-MMAS)。首先,结合实际的企业分布式信息管理系统设计FSS,启发式选择较优关系副本,以减少查询连接代价并缩小PGA-MMAS的搜索空间;然后结合遗传算法(GA)收敛较快的优势,对最终连接关系进行编码和并行遗传操作,得到一组相对较优的QEP,并将其转化为并行最大最小蚁群算法(MMAS)的初始信息素分布,从而使其更快速地搜索到全局最优QEP;最后分别在不同关系数情况下对算法进行仿真实验,结果表明,基于FSS的PGA-MMAS搜索最优QEP的效率高于原GA以及基于FFS的GA、MMAS和GA-MMAS;经实际工程应用验证,所提算法搜索出的高质量QEP可以提高分布式数据库多关系查询效率。

关键词：分布式数据库,遗传算法,最大最小蚁群算法,最优查询执行计划,并行

基金资助：国家自然科学基金资助项目(61261017);广西自然科学基金资助项目(2014GXNSFAA118387);广西无线宽带通信与信号处理重点实验室资助项目(GXKL0614202);桂林电子科技大学研究生科研创新项目(YJCXS201523)。