基于改进蚁群算法的数据仓库查询优化研究

摘要

随着信息技术和决策支持系统的迅速发展，信息的潜在价值成为企业间竞争的新利器，数据仓库成为企业必然的选择，随着经济的发展和业务环境的变化，用户需求的不断提升，数据仓库已经进入一个快速发展的阶段。联机分析处理作为数据仓库系统的前端分析技术，对海量数据进行大量复杂的运算，并从多个角度以快速、直观的形式将查询结果呈现给决策人员，以便制定正确的方案增加效益。
　　 在数据仓库的应用中，用户的查询请求会经常涉及到多连接、聚集计算等操作，随着数据量的不断膨胀，查询请求响应时间已经成为影响数据仓库系统性能的关键性因素。因此，如何缩短用户响应时间成为数据仓库领域的一个研究热点。
　　 数据仓库的多连接查询优化属于NP问题，与典型的TSP问题极为相似。数据仓库应用的有效实现需要关系查询技术的支持，OLAP的多维数据模型采用二维关系进行管理，而且数据分析和数据挖掘的实现都是在多维数据或相关数据集上进行的，而这些多维数据或数据集的提取需要经过维表和事实表的连接操作来完成。对于每一个多连接查询都对应多个代价消耗不同的查询执行计划，查询执行计划的个数随关系的个数指数性增长，查询优化器需要能够通过优化算法在庞大的搜索空间中寻找代价消耗最小的查询执行计划。
　　 蚁群算法是一种最新发展的模拟蚂蚁群体觅食行为的仿生优化算法，该算法采用正反馈机制，易于与其它优化方法结合，在解决许多复杂优化问题中体现了较好的性能，如机器人路径规划、TSP问题、数据挖掘、图像处理等领域。但传统的蚁群算法在解决数据仓库查询优化的问题时，存在过早收敛、收敛速度慢等缺点，为了提高算法的全局搜索能力和收敛速度，本文从算法本身及其应用实现两个方面作了改进，主要创新点如下。
　　 第一：算法采用基于伪随机概率转移规则的城市选择策略，并融合基于“3-opt”的迭代局部寻优策略。该策略采用了确定性选择和随机性选择相结合的城市选择方法，在提高全局搜索能力的同时，也在一定程度上加快了收敛速度；同时，在每一次迭代结束，即蚂蚁完成路径构建步骤后，以“3-opt”为局部搜索策略进行迭代局部搜索，将当前解优化为局部最优解（非全局最优解），在一定程度上提高了最优解的质量。
　　 第二：基于连接操作的有序编码策略。改进的蚁群算法解决数据仓库中MJQO问题时，采用对join编码、而非对关系编码的策略，以尽可能避免两个结果集（或关系）之间进行笛卡尔积操作，缩小了搜索策略空间，同时也提高了优化算法的搜索效率。
　　 改进的蚁群算法在解决数据仓库多连接查询优化问题时，以左线性空间为搜索空间，采用有序串对连接进行编码，应用改进的蚁群算法找出全局最优搜索策略，分析了关键参数的选择对算法性能的影响，构建算法性能评估模型。实验结果表明，该改进策略加快了算法的收敛速度，并提高了最优解的质量。