基于蟻群算法的分布式數(shù)據(jù)庫(kù)查詢優(yōu)化方法

崔峰峰　南振岐

摘 要： 在分布式數(shù)據(jù)庫(kù)查詢優(yōu)化中，數(shù)據(jù)傳輸和多連接次序往往決定了查詢執(zhí)行速度，以通信代價(jià)最小為目標(biāo)的代價(jià)模型一直是研究的重點(diǎn)。隨著大數(shù)據(jù)時(shí)代的到來(lái)，如何提高數(shù)據(jù)庫(kù)的查詢效率成為我們所要面對(duì)的首要問(wèn)題。為此，利用蟻群算法優(yōu)化查詢計(jì)劃，以多元連接查詢操作為例，進(jìn)行了模型建立和算法實(shí)現(xiàn)。在Oracle數(shù)據(jù)庫(kù)中進(jìn)行了仿真實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明該算法有較好的尋優(yōu)效果，并對(duì)分布式數(shù)據(jù)庫(kù)的查詢優(yōu)化具有實(shí)際意義。

關(guān)鍵詞： 分布式數(shù)據(jù)庫(kù)； 查詢優(yōu)化； 多元連接； 蟻群算法

中圖分類號(hào)：TP319 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1006-8228（2014）05-47-03

Abstract： In the distributed database query optimization， the speed of query depends on the data transfer and join sequence. The price model minimizing communication cost is the emphasis of research. Since the era of big data is coming， the first important problem is how to enhance the speed of database query. Seeking the best query path by using the ant colony algorithm， and taking multiple connection query as an example， model building and algorithm implementation are carried on. The experimental results show that this algorithm has the better effect in selecting path and is practically meaningful for the query optimization of distribute database.

Key words： distributed database； query optimization； multiple connection； ant colony algorithm

0 引言

查詢優(yōu)化是分布式數(shù)據(jù)庫(kù)系統(tǒng)中的核心問(wèn)題。與集中式數(shù)據(jù)庫(kù)查詢相比，分布式查詢處理增加了不少新的內(nèi)容和復(fù)雜性。不同的查詢處理方法，其查詢的通信費(fèi)用和并行程度是大不一樣的。分布式查詢優(yōu)化的準(zhǔn)則是使通信費(fèi)用最低和使響應(yīng)時(shí)間最短，即以最小的總代價(jià)在最短的響應(yīng)時(shí)間內(nèi)獲得需要的數(shù)據(jù)。分布式數(shù)據(jù)庫(kù)中數(shù)據(jù)的特征是：全局化和局部化。數(shù)據(jù)局部化是將一個(gè)分布式數(shù)據(jù)庫(kù)上的代數(shù)查詢轉(zhuǎn)換成一個(gè)等價(jià)的段查詢，并通過(guò)代數(shù)轉(zhuǎn)換來(lái)做進(jìn)一步的簡(jiǎn)化。全局查詢優(yōu)化通過(guò)決策操作的順序，結(jié)點(diǎn)間的數(shù)據(jù)移動(dòng)，以及數(shù)據(jù)庫(kù)操作的分布和局部算法的選擇來(lái)為輸入的分段查詢計(jì)劃，產(chǎn)生一個(gè)優(yōu)化的執(zhí)行計(jì)劃[1-2]。

文獻(xiàn)[3]的作者提出了基于遺傳算法的分布式數(shù)據(jù)庫(kù)查詢優(yōu)化方法，并且設(shè)計(jì)了一種新的查詢執(zhí)行計(jì)劃模型。文獻(xiàn)[4]中提出了采用改進(jìn)的最小生成樹(shù)算法。本文提出了一種利用蟻群算法解決分布是數(shù)據(jù)庫(kù)系統(tǒng)中查詢優(yōu)化問(wèn)題的方法。此方法仍處于初期研究階段，但初步研究已表明，應(yīng)用蟻群算法進(jìn)行分布式數(shù)據(jù)庫(kù)的查詢優(yōu)化不但有效，而且具有良好的尋優(yōu)能力。多元連接查詢涉及多個(gè)片段上的查詢，由于分布式數(shù)據(jù)庫(kù)數(shù)據(jù)分布與冗余的特征，多元連接查詢涉及多個(gè)不同的結(jié)點(diǎn)上的片段。等值連接與自然連接是應(yīng)用最多的連接操作，所以我們以研究多元連接操作的查詢處理為例。

1 蟻群算法原理概述

蟻群算法最初由意大利學(xué)者Dorigo.M于1991年首次提出，其本質(zhì)上是一個(gè)復(fù)雜的智能系統(tǒng)，它具有較強(qiáng)的魯棒性、優(yōu)良的分布式計(jì)算機(jī)制、易于與其他方法結(jié)合等優(yōu)點(diǎn)。目前對(duì)其研究已滲透到多個(gè)應(yīng)用領(lǐng)域，并由解決一維靜態(tài)優(yōu)化問(wèn)題發(fā)展到解決多維動(dòng)態(tài)問(wèn)題。

仿生學(xué)家的長(zhǎng)期研究發(fā)現(xiàn)：螞蟻雖沒(méi)有視覺(jué)，但在運(yùn)動(dòng)過(guò)程中通常會(huì)釋放特殊的分泌物找到路徑。當(dāng)它們穿過(guò)一個(gè)沒(méi)有走過(guò)的路口時(shí)，則隨機(jī)地選擇一條路徑，并在路徑上釋放信息素。時(shí)間越長(zhǎng)，螞蟻所走路徑上的信息量就越小。當(dāng)后來(lái)的螞蟻再次來(lái)到此路口時(shí)，選擇信息量較大的那條路經(jīng)的概率就相對(duì)越大，從而形成了一個(gè)正反饋機(jī)制。最優(yōu)路徑上的信息量越來(lái)越大，但在其他路徑上隨著時(shí)間的推移，信息量會(huì)逐漸減小，整個(gè)蟻群最終會(huì)找到一條最優(yōu)路徑。我們用圖1進(jìn)行了形象的描述，以此來(lái)進(jìn)一步說(shuō)明蟻群的搜索原理[5]。

AE的所連接的直線上有一障礙物。由于障礙物的存在，螞蟻只能從A經(jīng)B、C或者D到達(dá)E，或者由D到達(dá)A，假設(shè)單位時(shí)間內(nèi)有20只螞蟻由A到達(dá)E點(diǎn)，有20只螞蟻由E到達(dá)A點(diǎn)，螞蟻所留下的信息量為2。為了便于計(jì)算，設(shè)信息素停留時(shí)間為1.5。在初始狀態(tài)，由于路徑AB、BC、CE、AD、DE上均無(wú)信息素存在，位于A和E點(diǎn)的螞蟻可以隨意選擇所要走的路徑，從統(tǒng)計(jì)學(xué)的角度可以認(rèn)為螞蟻選擇路徑AB、BC、AD、DE的概率是相同的。經(jīng)過(guò)一個(gè)單位時(shí)間后，在路徑ADE上的信息量大于路徑ABCE上的信息量。又經(jīng)過(guò)一段時(shí)間，將有10只螞蟻由D點(diǎn)到達(dá)E。隨著時(shí)間的推移，螞蟻選擇ADE的概率將會(huì)越來(lái)越大，最終將會(huì)完全選擇路徑ADE，從而找到蟻穴到食物所在地的最短路徑。

2 分布式數(shù)據(jù)庫(kù)

分布式數(shù)據(jù)庫(kù)系統(tǒng)，通俗地說(shuō)，是物理上分散而邏輯上集中的數(shù)據(jù)庫(kù)系統(tǒng)。分布式數(shù)據(jù)庫(kù)使用計(jì)算機(jī)網(wǎng)絡(luò)將地理位置分散而管理和控制又需要不同程度集中的多個(gè)邏輯單位連接起來(lái)，共同組成一個(gè)統(tǒng)一的數(shù)據(jù)庫(kù)系統(tǒng)[6]。

3 多連接查詢優(yōu)化問(wèn)題

在分布式數(shù)據(jù)庫(kù)系統(tǒng)中，執(zhí)行一條查詢語(yǔ)句，如果這條查詢語(yǔ)句涉及多個(gè)表，就需要進(jìn)行多元連接。由于分布式數(shù)據(jù)庫(kù)物理上分散的緣故，連接的代價(jià)往往不同，因此必須找出一條最優(yōu)的連接路徑[1]。

在多元連接查詢中再根據(jù)式⑶計(jì)算下一個(gè)關(guān)系的連接概率，將該關(guān)系的序號(hào)放入有序串。

⑹ 判斷是否所有的關(guān)系都在有序序列中，若是，則這只螞蟻的任務(wù)結(jié)束；否則，轉(zhuǎn)入第⑷步繼續(xù)執(zhí)行。

⑺ 若種群中所有的螞蟻都搜索完成，由式⑶計(jì)算每只螞蟻生成的關(guān)系的連接序列的代價(jià)總和，選擇代價(jià)最小的哪條路徑，并在該路徑上釋放一定量的同位素。

⑻ 判斷迭代次數(shù)是否大于等于N，若是，則結(jié)束搜索；否則，轉(zhuǎn)入第⑶步進(jìn)行下一次搜索操作。

⑼ 根據(jù)搜索出來(lái)的代價(jià)最小的連接順序，做查詢連接操作，得出實(shí)驗(yàn)結(jié)果。

5 實(shí)驗(yàn)及結(jié)果分析

6 結(jié)束語(yǔ)

查詢優(yōu)化問(wèn)題一直是分布式數(shù)據(jù)庫(kù)研究的重要方向，作者采用蟻群算法來(lái)實(shí)現(xiàn)多元連接的查詢優(yōu)化。通過(guò)代價(jià)估計(jì)模型計(jì)算連接代價(jià)作為蟻群算法中的路徑權(quán)值，利用蟻群算法在尋找最優(yōu)路徑上的優(yōu)點(diǎn)進(jìn)行查詢優(yōu)化。實(shí)驗(yàn)結(jié)果表明，該算法不僅有效，而且當(dāng)在連接元組數(shù)增多時(shí)能有更好的表現(xiàn)，縮減了查詢時(shí)間?？梢缘贸鼋Y(jié)論：基于蟻群算法時(shí)間多元連接查詢優(yōu)化，對(duì)于分布式數(shù)據(jù)庫(kù)查詢與設(shè)計(jì)具有實(shí)際意義。

參考文獻(xiàn)：

[1] 郭聰莉.基于蟻群算法的多連接查詢優(yōu)化[J].計(jì)算機(jī)工程，2009.10：

173-175

[2] 賀寧.蟻群算法在數(shù)據(jù)庫(kù)查詢中的應(yīng)用[J].山西電子技術(shù)，2008.1：

71-72

[3] 帥訓(xùn)波.基于遺傳算法的分布式數(shù)據(jù)庫(kù)查詢優(yōu)化研究[J].小型微型計(jì)

算機(jī)系統(tǒng)，2009.8：1600-1604

[4] 胡楓.一種分布式數(shù)據(jù)庫(kù)多元連接查詢優(yōu)化算法及改進(jìn)[J]. 計(jì)算機(jī)工

程與應(yīng)用，2001.16：125-127

[5] 段海濱.蟻群算法原理及應(yīng)用[M].科技出版社，2005.

[6] 邵佩英.分布式數(shù)據(jù)庫(kù)系統(tǒng)及其引用[M].科學(xué)出版社，2000.