论文部分内容阅读
查询优化是数据库管理系统设计和实现所采用的一项重要技术，也是直接影响数据库系统性能的一个重要因素，当前所有商用数据库都成功采用了这项技术。关系数据库系统和非过程化的SQL语言能够取得巨大成功，主要得益于查询优化技术的发展。对于一个复杂的查询，寻找一个高校的执行策略是数据库系统开发成功的关键所在，此项研究目前在数据库领域仍属于NP-Hard问题。在查询执行的过程中，低效的SQL查询语句、概貌信息的匾乏、连接顺序的错误选择都是直接导致查询效率低下的原因。
本文工作即着眼于查询优化亟待解决的问题之一——连接顺序的优化选择而展开。在多连接关系型数据库中关系的连接次序直接影响查询效率。因此，用优化算法确定好的连接次序是当前研究的一个热点。本文首先从国内外查询优化技术研究的现状出发，研究了数据库多连接查询优化技术，讨论了查询优化的整个流程及各个阶段优化的原理和技术，研究了将一些优秀的仿生算法(如：遗传算法、模拟退火算法、免疫算法、粒子群算法等)在多连接数据库查询优化中成功应用的实例和建模策略，分析了现有数据库的查询优化理论和方法。
蚁群算法是一种最新发展的模拟昆虫王国中蚂蚁群体觅食行为的仿生优化算法。该算法采用了正反馈进行自催化机制，具有较强的鲁棒性、优良的分布式计算机制、易于与其他算法结合等优点，在解决许多复杂优化问题方面已经展现出其优异的性能和巨大的发展潜力。近几年，蚁群算法得到了多方面的研究和多领域的应用，其应用范围完全可与遗传算法相媲美。但是，目前国内外还较少将蚁群算法应用到数据库多连接查询优化问题的求解中。蚁群算法提出后在解决TSP问题中得到了成功，本文深入分析研究了经典TSP问题和数据库多连接查询优化问题，通过分析发现数据库多连接查询优化问题和经典TSP问题有很多相似之处，故将数据库多连接查询优化问题建模成一个有特定条件的TSP模型。提出了将蚁群算法应用到数据库多连接查询优化问题中的思想，并进行了算法建模，确定了优化策略。
文章进行了多方面实验，从不同的角度证明蚁群算法在数据库多连接查询优化问题中应用中的可行性。实验中选取了两个具有代表性的数据库，分别按一定关系数下和不同关系数下进行了测试。不同关系下查询优化实验将蚁群算法与常用的查询优化算法Greedy优化算法在相同环境下进行对比实验。对实验结果进行了分析，证明本文提出的基于蚁群算法的数据库多连接查询优化的解决方案在关系连接数较多的大型数据库的查询优化中优于传统的Greedy优化算法。
本文的创新点可以总结如下：
(1)在前人研究的基础上将多连接查询优化建模，并与经典TSP问题进行对比研究。
通过对比将多连接查询优化建模成特殊的TSP模型。通过将多连接查询优化与经典TSP问题进行比较，找出这两个组合优化问题的异同。由于蚁群算法在解决TSP问题中具有一定优势，故通过比较建模为利用蚁群算法解决多连接优化问题提供理论依据。
(2)将蚁群算法应用到数据库多连接查询优化中，从而拓展了蚁群算法在工程实践中的应用领域。
查询优化是目前大型数据库亟待解决的一个NP-hard问题，国内外学者提出了各类算法解决该问题，并取得了较好的结果。蚁群算法在解决组合优化问题中取得了令人满意的效果，但目前国内外还较少将其应用到查询优化问题中。本文在前人研究的基础上提出将蚁群算法应用到多连接查询优化问题中的思想。
通过本文进行的一系列实验，结果表明，本文提出的基于蚁群算法的数据库多连接查询优化算法对实际数据库有明显的优化效果。并且，该方法在大型数据库的多连接优化问题中优化效果优于传统的Greedy优化算法，证明了蚁群算法在处理数据库多连接查询优化问题具有一定的优越性。通过本文的实验进一步证明了蚁群算法在求解复杂问题时明显的优越性，该方法的应用为实现数据库多连接查询优化展开了新的思路与途径。