基于蟻群算法的分布式數據庫查詢優化方法

崔峰峰　南振岐

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

關鍵詞： 分布式數據庫； 查詢優化； 多元連接； 蟻群算法

中圖分類號：TP319 文獻標志碼：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 引言

查詢優化是分布式數據庫系統中的核心問題。與集中式數據庫查詢相比，分布式查詢處理增加了不少新的內容和復雜性。不同的查詢處理方法，其查詢的通信費用和并行程度是大不一樣的。分布式查詢優化的準則是使通信費用最低和使響應時間最短，即以最小的總代價在最短的響應時間內獲得需要的數據。分布式數據庫中數據的特征是：全局化和局部化。數據局部化是將一個分布式數據庫上的代數查詢轉換成一個等價的段查詢，并通過代數轉換來做進一步的簡化。全局查詢優化通過決策操作的順序，結點間的數據移動，以及數據庫操作的分布和局部算法的選擇來為輸入的分段查詢計劃，產生一個優化的執行計劃[1-2]。

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

1 蟻群算法原理概述

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

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

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

2 分布式數據庫

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

3 多連接查詢優化問題

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

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

⑹ 判斷是否所有的關系都在有序序列中，若是，則這只螞蟻的任務結束；否則，轉入第⑷步繼續執行。

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

⑻ 判斷迭代次數是否大于等于N，若是，則結束搜索；否則，轉入第⑶步進行下一次搜索操作。

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

5 實驗及結果分析

6 結束語

查詢優化問題一直是分布式數據庫研究的重要方向，作者采用蟻群算法來實現多元連接的查詢優化。通過代價估計模型計算連接代價作為蟻群算法中的路徑權值，利用蟻群算法在尋找最優路徑上的優點進行查詢優化。實驗結果表明，該算法不僅有效，而且當在連接元組數增多時能有更好的表現，縮減了查詢時間。可以得出結論：基于蟻群算法時間多元連接查詢優化，對于分布式數據庫查詢與設計具有實際意義。

參考文獻：

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

173-175

[2] 賀寧.蟻群算法在數據庫查詢中的應用[J].山西電子技術，2008.1：

71-72

[3] 帥訓波.基于遺傳算法的分布式數據庫查詢優化研究[J].小型微型計

算機系統，2009.8：1600-1604

[4] 胡楓.一種分布式數據庫多元連接查詢優化算法及改進[J]. 計算機工

程與應用，2001.16：125-127

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

[6] 邵佩英.分布式數據庫系統及其引用[M].科學出版社，2000.