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

论文摘要

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

论文目录

• 摘要
• Abstract
• 目录
• 第一章 绪论
• 1.1 研究背景及意义
• 1.2 研究现状
• 1.2.1 数据仓库查询优化研究现状
• 1.2.2 本文完成的主要工作
• 1.3 论文结构安排
• 第二章 数据仓库与OLAP技术
• 2.1 数据仓库
• 2.1.1 数据仓库的产生及发展
• 2.1.2 数据仓库的概念及特征
• 2.1.3 数据仓库的体系结构
• 2.1.4 数据仓库的多维模型
• 2.1.4.1 星型结构
• 2.1.4.2 雪花结构
• 2.2 OLAP技术
• 2.2.1 OLAP概念及特征
• 2.2.2 OLAP操作
• 2.2.3 OLAP的实现
• 2.3 数据仓库和OLAP技术的研究和发展现状
• 2.4 本章小结
• 第三章 多连接查询优化研究
• 3.1 多连接查询的研究背景
• 3.2 多连接查询优化
• 3.2.1 查询优化
• 3.2.1.1 查询处理
• 3.2.1.2 查询优化器
• 3.2.2 多连接查询优化
• 3.2.2.1 多连接查询的概念
• 3.2.2.2 多连接查询的表示
• 3.2.3 代价评估模型
• 3.2.3.1 QEP的代价构成
• 3.2.3.2 代价模型
• 3.2.3.4 逻辑优化代价评估模型
• 3.2.4 查询优化搜索算法
• 3.3 本章小结
• 第四章 蚁群算法
• 4.1 引言
• 4.2 蚁群算法的机制原理
• 4.3 蚁群算法的模型特征
• 4.3.1 TSP描述
• 4.3.2 基本蚁群算法的数学模型
• 4.3.3 基本蚁群算法程序结构流程
• 4.4 最大最小蚁群系统
• 4.4.1 信息素更新机制
• 4.4.2 信息素限制机制
• 4.4.3 信息素的初始化机制
• 4.4.4 信息素平滑机制
• 4.5 本章小结
• 第五章 基于改进蚁群算法的数据仓库查询优化
• 5.1 数据仓库查询优化问题描述
• 5.2 改进的蚁群算法
• 5.2.1 伪随机状态转移策略
• 5.2.2 迭代局部搜索
• 5.2.2.1 局部搜索的概念
• 5.2.2.2 局部搜索策略
• 5.2.2.3 迭代局部搜索机制
• 5.3 算法设计
• 5.3.1 算法初始化
• 5.3.2 查询优化搜索
• 5.3.3 迭代更新
• 5.4 关键参数优化
• 5.4.1 试验平台介绍
• 5.4.2 信息素挥发因子ρ的选择
• 5.4.3 信息启发式因子α的选择
• 5.4.4 期望启发式因子β的选择
• 5.5 逻辑优化评估
• 5.6 本章小结
• 第六章 总结与展望
• 6.1 本文总结
• 6.2 展望
• 致谢
• 参考文献
• 附录A 图索引
• 附录B 表索引
• Appendix A Figure Index
• Appendix B Table Index
• 攻读学位期间发表的学术论文目录