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

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

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

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

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

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