基于蚁群算法的数据库多连接查询优化问题研究

《基于蚁群算法的数据库多连接查询优化问题研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、河北工业大学硕士学位论文基于蚁群算法的数据库多连接查询优化问题研究姓名：刘玉娟申请学位级别：硕士专业：计算机应用技术指导教师：顾军华20081101河北工业大学硕士学位论文基于蚁群算法的数据库多连接查询优化问题研究摘要多连接操作是数据库领域的重要操作之一，其优化问题属于NP问题，也是数据库领域的一个没有很好解决的问题。随着超大规模数据库和数据仓库的出现，多连接查询优化越来越深地影响着数据查询的效率，而传统的优化技术在多连接查询优化问题上显得更加无能为力。本文提出采用蚁群算法求解多连接查询优化问题，提高了多连接查询的执行效率，优化后的查询代价大大降低。首先，研究了目前的关系型数据

2、库中多连接查询优化问题，全面分析了数据库系统中多连接查询优化的特点，详细描述了当前的多种优化方法,并分析了当前的查询优化方法中存在的问题，提出了相应的解决思路。其次，本文基于查询代价评估的优化策略，建立了一个代价估计模型，提出了采用蚁群算法来求解该数学模型，并给出了用蚁群算法求解代价模型的详细过程，包括如何定义启发式信息；如何实施信息素的全局更新和局部更新；如何设定状态转移规则等。然后，通过大量仿真实验，分析了蚁群算法的几个关键参数对算法性能的影响。最后，以左线性树为搜索空间，将蚁群算法求解多连接查询优化问题的方法应用到实践中，并通过大量的仿真实验，证明了蚁群算法求解该问题的有

3、效性和优越性。关键词：蚁群算法，多连接查询优化，代价估计模型，左线性树空间i基于蚁群算法的关系数据库多连接查询优化问题研究RESEARCHONMULTI-JOINQUERYOPTIMIZATIONBASEDONANTCOLONYSYSTEMABSTRACTTheproblemofoptimizingamulti-joinqueryisanNP-completecombinatorialoptimizationproblem,andisalsoanunsolvedproblemindatabasefield.Inrecentyears,asappearingoftheveryla

4、rgedatabaseanddatawarehouse,theeffectivenessofthemulti-joinqueryoptimizationlargelyimprovestheefficiencyofthedataquery.Buttraditionaloptimizationtechniquesformulti-joinqueryareinadequatetosupportsomeoftheemergingdatabaseapplications.Themaincontentofthisthesisistodemonstratethatantcolonyoptim

5、izationalgorithmcanbeeffectiveinthesolutionofamulti-joinqueryoptimization.Firstly,thisthesisdescribesresearchbackgroundofmulti-joinqueryoptimization(MJQO)incurrentrelationdatabasesystem,comprehensivelyanalysesmainfeaturesaboutmulti-joinqueryandmakesadetaileddescriptionofdefectsinthecurrentqu

6、eryoptimizationmethodsthatexist.Secondly,basedontheassessmentcoststrategy,theestimatedcostmodelhasbeenestablished.ThispaperproposesanewalgorithmtosolveMJQOproblembasedonantcolonysystem(ACS).Inthispaper,detailsofthealgorithmusedtosolveMJQOproblemhavebeeninterpreted,includinghowtodefineheurist

7、icinformation,howtoimplementlocalpheromoneupdateandglobalpheromoneupdateandhowtodesignstatetransitionrule.Lastly,inleft-lineartreespace,afterrepeatediteration,areasonablesolutionisobtained.ComparedwithgeneticalgorithmandGreedyalgorithmthesimulation