基于免疫遗传算法的多连接查询优化.pdf

《基于免疫遗传算法的多连接查询优化.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、总第15卷167期大众科技V01．15N0．72013年7月PopularScience&TechnologyJuly2013基于免疫遗传算法的多连接查询优化周凌云(中南民族大学计算机学院，湖北武汉430074)【摘要】给出了多连接查询优化问题的计算模型，分析了免疫遗传算法的基本原理，提出将免疫遗传算法应用于多连接查询优化问题。针对多连接查询优化问题的具体特点，给出了免疫遗传算法的设计，包括亲和度、适应度函数的设计，基于抗体浓度的选择算子、交叉算子、变异算子的设计，免疫算子的设计。【关键词】多连接查询优化；免疫遗传算法

2、；抗体浓度；免疫接种【中图分类号】TP31【文献标识码】A【文章编号】1008—1151(2013)07—0001—03BasedonimmunegeneticalgorithmformultidoinqueryoptimizationAbstract：Givesamulti-joinqueryoptimizationcalculationmodel，analysisofthebasicprinciplesofimmunegeneticalgorithm，proposeimmunegeneticalgorithmapp

3、fiedtomulti-joinqueryoptimizationproblem．Againstmulti-joinqueryoptimizationproblemspecificcharacteristics，givestheimmunegeneticalgorithmdesign，includingaffinity，fitnessfunctiondesign，concentrationofantibody—basedselectionoperator，crossoveroperator，mutationoperat

4、ordesign，immuneoperatordesign．Keywords：Mu1d—joinqueryoptimization；immunegeneticalgorithm；antibodyconcentration；immunization询计划的性能。本文的主要内容是将免疫思想和遗传算法相1引言结合，设计一个多连接查询优化算法，在保持遗传算法优良随着Internet技术与信息管理系统的发展与普及，基于特性的前提下，加入抽取疫苗、接种疫苗、疫苗选择等免疫数据库、数据仓库的联机事务处理和联机分析处理已成为银算子，抑

5、制优化过程中出现的退化现象，提高算法的寻优能行、企业、政府等部门最为重要的计算机应用之一。在这些力。应用中，多连接查询操作在各种数据库操作中所占比重非常2多连接查询优化问题大，而且，执行多连接查询操作时，运算先后次序不同，查询请求响应的时间就不同。多连接查询优化就是对于由Y个多连接查询优化问题可以描述为合理时间内在搜索空间(N>10)关系的连接操作构成的一个查询请求，在合理的时中找到一个最好或者近似最好的关系连接次序问题。搜索空间内找到一个最佳的查询执行计划。一个好的查询计划往往间常采用左线性树空间，并根据关系代数的等

6、价变换规则，可以使程序性能提高数十倍。然而，在大规模数据库、数据利用“选择操作下移、投影操作尽量先做、避免笛卡尔积”仓库、联机分析处理的环境下，参与多连接查询运算的表的等启发式信息。多连接查询优化问题可简化为一个带约束的数目较大，导致多连接查询优化的计算复杂性非常大。因此，组合优化问题，求解该问题的数学模型如下。多连接查询优化对获得好的查询性能至关重要“。n-1，一多连接查询优化问题是一个NP问题，高效的优化算法是c，z(ff)(1)式提高查询性能的关键问题。目前，已有一些算法解决这个问题，这些方法在某些方面提高或改进

7、了查询性能。文献[2]n(t)(2)式利用增量启发式信息来初始化种群，提高了遗传算法的收敛速度。文献[3]在遗传算法的过程中加入了模拟退火操作，有利于保持物种的多样性。文献[4]在查询优化中，结合哈希过V(AIt)：』V(A,r)，,A∈er-s(3)式滤方法，减少查询执行计划的计算代价，从而提高多连接查Imin(V(A，r)，v(A，))，A∈r^A∈询效率。文献[5]结合遗传算法和模拟退火算法提出了一种混合算法，并将其应用到多连接优化问题，改进了获得最佳查【收稿日期】2013—06-12【作者简介】周凌云(1979

8、一)，女，重庆人，中南民族大学计算机学院讲师，硕士，研究方向为智能算法。上述模型中，C表示多连接查询的代价，tf表示左线性本文吸取免疫遗传算法的思想，结合多连接查询优化的树中的内部结点，r和s是tf的左右子结点(即tf是r与s特点，将它用于求解多连接查询优化问题。首先，将免疫遗传算法中涉及的基本概念与多连接查询优化的基本概念进行对