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

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

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

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

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

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