崔峰峰　南振岐

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

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

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

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

1 蟻群算法原理概述

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

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

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

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

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

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

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

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

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

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

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

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

5 實驗及結(jié)果分析

6 結(jié)束語

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

參考文獻(xiàn)：

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

173-175

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

71-72

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

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

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

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

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

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