基于改進蟻群算法的數(shù)據(jù)倉庫查詢優(yōu)化研究.pdf

1、隨著信息技術和決策支持系統(tǒng)的迅速發(fā)展，信息的潛在價值成為企業(yè)間競爭的新利器，數(shù)據(jù)倉庫成為企業(yè)必然的選擇，隨著經(jīng)濟的發(fā)展和業(yè)務環(huán)境的變化，用戶需求的不斷提升，數(shù)據(jù)倉庫已經(jīng)進入一個快速發(fā)展的階段。聯(lián)機分析處理作為數(shù)據(jù)倉庫系統(tǒng)的前端分析技術，對海量數(shù)據(jù)進行大量復雜的運算，并從多個角度以快速、直觀的形式將查詢結果呈現(xiàn)給決策人員，以便制定正確的方案增加效益。
　　 在數(shù)據(jù)倉庫的應用中，用戶的查詢請求會經(jīng)常涉及到多連接、聚集計算等操作，隨著

2、數(shù)據(jù)量的不斷膨脹，查詢請求響應時間已經(jīng)成為影響數(shù)據(jù)倉庫系統(tǒng)性能的關鍵性因素。因此，如何縮短用戶響應時間成為數(shù)據(jù)倉庫領域的一個研究熱點。
　　 數(shù)據(jù)倉庫的多連接查詢優(yōu)化屬于NP問題，與典型的TSP問題極為相似。數(shù)據(jù)倉庫應用的有效實現(xiàn)需要關系查詢技術的支持，OLAP的多維數(shù)據(jù)模型采用二維關系進行管理，而且數(shù)據(jù)分析和數(shù)據(jù)挖掘的實現(xiàn)都是在多維數(shù)據(jù)或相關數(shù)據(jù)集上進行的，而這些多維數(shù)據(jù)或數(shù)據(jù)集的提取需要經(jīng)過維表和事實表的連接操作來完成。對于

3、每一個多連接查詢都對應多個代價消耗不同的查詢執(zhí)行計劃，查詢執(zhí)行計劃的個數(shù)隨關系的個數(shù)指數(shù)性增長，查詢優(yōu)化器需要能夠通過優(yōu)化算法在龐大的搜索空間中尋找代價消耗最小的查詢執(zhí)行計劃。
　　 蟻群算法是一種最新發(fā)展的模擬螞蟻群體覓食行為的仿生優(yōu)化算法，該算法采用正反饋機制，易于與其它優(yōu)化方法結合，在解決許多復雜優(yōu)化問題中體現(xiàn)了較好的性能，如機器人路徑規(guī)劃、TSP問題、數(shù)據(jù)挖掘、圖像處理等領域。但傳統(tǒng)的蟻群算法在解決數(shù)據(jù)倉庫查詢優(yōu)化的問題

4、時，存在過早收斂、收斂速度慢等缺點，為了提高算法的全局搜索能力和收斂速度，本文從算法本身及其應用實現(xiàn)兩個方面作了改進，主要創(chuàng)新點如下。
　　 第一：算法采用基于偽隨機概率轉移規(guī)則的城市選擇策略，并融合基于“3-opt”的迭代局部尋優(yōu)策略。該策略采用了確定性選擇和隨機性選擇相結合的城市選擇方法，在提高全局搜索能力的同時，也在一定程度上加快了收斂速度；同時，在每一次迭代結束，即螞蟻完成路徑構建步驟后，以“3-opt”為局部搜索策略進

5、行迭代局部搜索，將當前解優(yōu)化為局部最優(yōu)解（非全局最優(yōu)解），在一定程度上提高了最優(yōu)解的質量。
　　 第二：基于連接操作的有序編碼策略。改進的蟻群算法解決數(shù)據(jù)倉庫中MJQO問題時，采用對join編碼、而非對關系編碼的策略，以盡可能避免兩個結果集（或關系）之間進行笛卡爾積操作，縮小了搜索策略空間，同時也提高了優(yōu)化算法的搜索效率。
　　 改進的蟻群算法在解決數(shù)據(jù)倉庫多連接查詢優(yōu)化問題時，以左線性空間為搜索空間，采用有序串對連接進