学位论文 > 优秀研究生学位论文题录展示
基于改进蚁群算法的数据仓库查询优化研究
作 者: 王守军
导 师: 赵鹏
学 校: 安徽大学
专 业: 计算机应用技术
关键词: 数据仓库 联机分析处理 蚁群算法 多连接查询优化 查询执行计划
分类号: TP311.13
类 型: 硕士论文
年 份: 2011年
下 载: 37次
引 用: 0次
阅 读: 论文下载
内容摘要
随着信息技术和决策支持系统的迅速发展,信息的潜在价值成为企业间竞争的新利器,数据仓库成为企业必然的选择,随着经济的发展和业务环境的变化,用户需求的不断提升,数据仓库已经进入一个快速发展的阶段。联机分析处理作为数据仓库系统的前端分析技术,对海量数据进行大量复杂的运算,并从多个角度以快速、直观的形式将查询结果呈现给决策人员,以便制定正确的方案增加效益。在数据仓库的应用中,用户的查询请求会经常涉及到多连接、聚集计算等操作,随着数据量的不断膨胀,查询请求响应时间已经成为影响数据仓库系统性能的关键性因素。因此,如何缩短用户响应时间成为数据仓库领域的一个研究热点。数据仓库的多连接查询优化属于NP问题,与典型的TSP问题极为相似。数据仓库应用的有效实现需要关系查询技术的支持,OLAP的多维数据模型采用二维关系进行管理,而且数据分析和数据挖掘的实现都是在多维数据或相关数据集上进行的,而这些多维数据或数据集的提取需要经过维表和事实表的连接操作来完成。对于每一个多连接查询都对应多个代价消耗不同的查询执行计划,查询执行计划的个数随关系的个数指数性增长,查询优化器需要能够通过优化算法在庞大的搜索空间中寻找代价消耗最小的查询执行计划。蚁群算法是一种最新发展的模拟蚂蚁群体觅食行为的仿生优化算法,该算法采用正反馈机制,易于与其它优化方法结合,在解决许多复杂优化问题中体现了较好的性能,如机器人路径规划、TSP问题、数据挖掘、图像处理等领域。但传统的蚁群算法在解决数据仓库查询优化的问题时,存在过早收敛、收敛速度慢等缺点,为了提高算法的全局搜索能力和收敛速度,本文从算法本身及其应用实现两个方面作了改进,主要创新点如下。第一:算法采用基于伪随机概率转移规则的城市选择策略,并融合基于“3-opt”的迭代局部寻优策略。该策略采用了确定性选择和随机性选择相结合的城市选择方法,在提高全局搜索能力的同时,也在一定程度上加快了收敛速度;同时,在每一次迭代结束,即蚂蚁完成路径构建步骤后,以“3-opt”为局部搜索策略进行迭代局部搜索,将当前解优化为局部最优解(非全局最优解),在一定程度上提高了最优解的质量。第二:基于连接操作的有序编码策略。改进的蚁群算法解决数据仓库中MJQO问题时,采用对join编码、而非对关系编码的策略,以尽可能避免两个结果集(或关系)之间进行笛卡尔积操作,缩小了搜索策略空间,同时也提高了优化算法的搜索效率。改进的蚁群算法在解决数据仓库多连接查询优化问题时,以左线性空间为搜索空间,采用有序串对连接进行编码,应用改进的蚁群算法找出全局最优搜索策略,分析了关键参数的选择对算法性能的影响,构建算法性能评估模型。实验结果表明,该改进策略加快了算法的收敛速度,并提高了最优解的质量。
|
全文目录
摘要 3-5 Abstract 5-7 目录 7-9 第一章 绪论 9-13 1.1 研究背景及意义 9-10 1.2 研究现状 10-12 1.2.1 数据仓库查询优化研究现状 10-11 1.2.2 本文完成的主要工作 11-12 1.3 论文结构安排 12-13 第二章 数据仓库与OLAP技术 13-22 2.1 数据仓库 13-17 2.1.1 数据仓库的产生及发展 13-14 2.1.2 数据仓库的概念及特征 14 2.1.3 数据仓库的体系结构 14-15 2.1.4 数据仓库的多维模型 15-17 2.1.4.1 星型结构 16 2.1.4.2 雪花结构 16-17 2.2 OLAP技术 17-20 2.2.1 OLAP概念及特征 17-18 2.2.2 OLAP操作 18-19 2.2.3 OLAP的实现 19-20 2.3 数据仓库和OLAP技术的研究和发展现状 20-21 2.4 本章小结 21-22 第三章 多连接查询优化研究 22-32 3.1 多连接查询的研究背景 22-23 3.2 多连接查询优化 23-31 3.2.1 查询优化 23-24 3.2.1.1 查询处理 23 3.2.1.2 查询优化器 23-24 3.2.2 多连接查询优化 24-28 3.2.2.1 多连接查询的概念 24-25 3.2.2.2 多连接查询的表示 25-28 3.2.3 代价评估模型 28-30 3.2.3.1 QEP的代价构成 28-29 3.2.3.2 代价模型 29-30 3.2.3.4 逻辑优化代价评估模型 30 3.2.4 查询优化搜索算法 30-31 3.3 本章小结 31-32 第四章 蚁群算法 32-41 4.1 引言 32-33 4.2 蚁群算法的机制原理 33-34 4.3 蚁群算法的模型特征 34-37 4.3.1 TSP描述 34 4.3.2 基本蚁群算法的数学模型 34-36 4.3.3 基本蚁群算法程序结构流程 36-37 4.4 最大最小蚁群系统 37-40 4.4.1 信息素更新机制 37-38 4.4.2 信息素限制机制 38-39 4.4.3 信息素的初始化机制 39 4.4.4 信息素平滑机制 39-40 4.5 本章小结 40-41 第五章 基于改进蚁群算法的数据仓库查询优化 41-59 5.1 数据仓库查询优化问题描述 41-42 5.2 改进的蚁群算法 42-46 5.2.1 伪随机状态转移策略 42-43 5.2.2 迭代局部搜索 43-46 5.2.2.1 局部搜索的概念 43 5.2.2.2 局部搜索策略 43-45 5.2.2.3 迭代局部搜索机制 45-46 5.3 算法设计 46-50 5.3.1 算法初始化 46-48 5.3.2 查询优化搜索 48-49 5.3.3 迭代更新 49-50 5.4 关键参数优化 50-56 5.4.1 试验平台介绍 50 5.4.2 信息素挥发因子ρ的选择 50-53 5.4.3 信息启发式因子α的选择 53-54 5.4.4 期望启发式因子β的选择 54-56 5.5 逻辑优化评估 56-58 5.6 本章小结 58-59 第六章 总结与展望 59-61 6.1 本文总结 59 6.2 展望 59-61 致谢 61-62 参考文献 62-68 附录A 图索引 68 附录B 表索引 68-69 Appendix A Figure Index 69 Appendix B Table Index 69-70 攻读学位期间发表的学术论文目录 70
|
相似论文
- 多导弹协同作战突防效能评估及组合优化算法研究,TJ760.1
- 基于蚁群算法的电梯群优化控制研究,TU857
- 动态环境下移动对象导航系统相关技术的研究,TP301.6
- 基于改进蚁群算法的机器人路径规划研究,TP242
- 改进的蚁群算法及其在TSP上的应用研究,TP301.6
- 基于免疫机制蚁群算法的电力系统无功优化研究,TP18
- 基于视觉反馈与行为记忆的GPU并行蚁群算法,TP301.6
- 数据仓库技术在银行客户管理系统中的研究和实现,TP315
- 关联规则算法在高职院校贫困生认定工作中的应用,G717
- 家校互动教育平台中数据仓库的研究与应用,TP311.13
- 高校毕业生就业状况监测系统研究,G647.38
- 基于数据仓库的药品监管辅助决策支持系统的设计与实现,TP311.13
- 基于数据挖掘技术的电信客户维系挽留系统分析及应用,TP311.13
- PG炼钢厂MES系统数据挖掘的设计与开发,TP311.13
- 六盘水市烟草公司人力资源管理系统信息集成设计实现,TP311.52
- 基于领域本体的海洋环境数据仓库设计,TP311.13
- 基于物理拓扑感知的Chord算法研究,TP393.02
- 电渣炉过程控制系统的设计及优化控制,TP273
- Ad Hoc网络中分簇路由算法的研究,TN929.5
- 图像信息处理机的图像处理方法研究,TP391.41
- DWMS中元数据以及缓冲区的设计和实现,TP311.13
中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 计算机软件 > 程序设计、软件工程 > 程序设计 > 数据库理论与系统
© 2012 www.xueweilunwen.com
|