張?zhí)m勇，耿文杰，劉 勝

(哈爾濱工程大學 自動化學院，哈爾濱 150001)

?

【信息科學與控制工程】

基于蟻群算法的多連接查詢優(yōu)化問題研究

張?zhí)m勇，耿文杰，劉 勝

(哈爾濱工程大學 自動化學院，哈爾濱 150001)

介紹了蟻群算法在數據庫查詢中的應用，在給出蟻群算法的基本原理和程序流程的基礎上，對傳統(tǒng)蟻群算法進行了改進，將偽隨機狀態(tài)轉移規(guī)則和局部信息素更新規(guī)則引入蟻群算法，提出了基于蟻群系統(tǒng)解決數據庫多連接查詢優(yōu)化的方法，建立了多連接查詢優(yōu)化問題的數學模型，并進行了相關的實驗；結果表明：當數據庫的表數目較多時，基于蟻群系統(tǒng)算法對解決多連接查詢優(yōu)化問題有良好的求解性能，在求最優(yōu)解品質和求最優(yōu)解時間上都有較好的效果。

蟻群算法；多連接查詢優(yōu)化；數據庫查詢；最優(yōu)解

多連接查詢優(yōu)化是數據庫技術領域目前研究的一個重要方向，隨著大規(guī)模數據庫和數據倉庫的出現(xiàn)，傳統(tǒng)的查詢技術已經難以滿足需求，國內外的學者從不同的角度對查詢優(yōu)化算法進行了廣泛和深入地研究。文獻[1]的作者提出了基于遺傳算法的分布式數據庫查詢優(yōu)化方法，并設計了一種新的查詢執(zhí)行計劃模型；文獻[2]提出了采用改進的最小生成樹算法；T.V.Vijay Kumar[3]提出一種基于遺傳算法的數據庫連接查詢優(yōu)化方法；Zehai Zhou[4]對遺傳算法進行改進，但對于不同問題，需要進行相應的改進，通用性差；Po-Han Chen等[5]將模擬退火算法引入遺傳算法的變異過程中，獲得比遺傳算法更優(yōu)的數據庫連接查詢優(yōu)化效果；Lingyun Wei等[6]利用小生境技術優(yōu)點，對遺傳算法探索能力進行改進，但無法改進局部探索能力差的缺陷。本文針對數據庫的多連接查詢優(yōu)化問題，將偽隨機變量和局部信息素更新規(guī)則引入蟻群算法，避免了局部最優(yōu)解，提高了算法的收斂速度。

1 蟻群算法

蟻群算法(Ant Colony Algorithm，ACA)最初由意大利學者M.Dorigo提出，M.Dorigo系統(tǒng)闡述了蟻群算法的數學模型和機制原理，并利用該方法解決了旅行商問題(TSP)、車間作業(yè)調度問題(JSP)和二次分配問題(QAP)等一系列組合優(yōu)化的問題。

1.1 基本原理

蟻群算法是模擬自然界中螞蟻尋食的過程得出的一種模擬進化仿生算法。螞蟻在經過的路徑上會釋放一種稱為信息素的化學物質，從而形成信息素軌跡，在一定的范圍內其他的螞蟻會感知信息素的存在和強度。本文簡要介紹蟻群搜索食物源的模擬過程。蟻群算法的原理示意圖如圖1。

圖1 蟻群算法的原理示意圖

假設A是蟻穴，D是食物源，EF是一障礙物。由于障礙的存在，螞蟻的可選擇路徑有：A-B-E-C-D或A-B-F-C-D。假定單位時間內從A到B的螞蟻個數是30，從C到D的螞蟻個數也是30，再假定信息素的停留時間是1。在初始時刻(T=0)，由于沒有信息素的存在，位于B點和C點的螞蟻可以隨機的選擇路徑，以統(tǒng)計學角度分析螞蟻選擇BE、BF、CE、CF的概率是相同的，這樣經過一個時間單位后，信息素在路徑BFC的累積量是路徑BEC上的2倍。在T=1時刻，單位時間內，將有20只螞蟻選擇BF和CF路徑，而BE和CE路徑只有10只螞蟻。隨著時間的累積，越來越多的螞蟻會選擇A-B-F-C-D作為蟻穴到食物源的路徑，從而找到蟻穴到食物源的最短路徑。張大衛(wèi)等[7]提出了量子建模優(yōu)化和查詢的辦法，為蟻群算法提出了新的方法。以下分析基本的蟻群建模算法，為深入研究做準備。

1.2 基本蟻群算法數學模型

數據庫查詢優(yōu)化問題與傳統(tǒng)的TSP問題(旅行商問題)非常的相似，TSP可以描述為：已知有n個城市，旅行商選擇其中一個城市作為出發(fā)點，然后經過所有城市且僅經過一次，最終回到出發(fā)點，要求尋求一條距離最短的路線。對于n個城市規(guī)模的TSP問題，有(n-1)!/2條不同方式的閉合路徑，TSP問題的數學模型描述表達為：

一個完全加權的向量圖G=(v,A,d)，其中v={0,1,2…,n-1}是節(jié)點(城市)；集合A={(r,s)|(s,r)}∈v×v是支路集合；d是A的權函數，表示A到G上的一個映射，它將每條支路(r,s)與一個正整數權d(r,s)相關聯(lián)(d(r,s)表示r和s之間的距離)，TPS問題的目標是尋找一條訪問每個節(jié)點一次的最小長度的閉合回路。

描述基于蟻群算法的數學模型中符號說明如下：

n：TSP的規(guī)模；

m：蟻群中螞蟻的總數；

τij(t)：t時刻路徑(i,j)上的信息素量；

dij：元素(城市)i和元素(城市)j間的距離；

ηij：啟發(fā)函數，由城市i轉移城市j的期望程度；

Γ={τij(t)|cj,cj=C}：t時刻集合C中兩兩城市連接lij份上殘留信息的集合；

在初始時刻，每一條路徑上信息素量是相同的，蟻群算法在尋優(yōu)過程中，螞蟻的狀態(tài)轉移概率如式(1)所示：

(1)

式(2)中符號的含義：

allowedk={C-tabuk}，表示螞蟻k下一步允許選擇的節(jié)點(城市)集合；

α：信息啟發(fā)因子，表示路徑上積累的信息素對螞蟻選擇路徑作用大??；

β：期望啟發(fā)因子，表示ηij的作用，螞蟻從城市i轉移到城市j的期望程度大小，一般取ηij=1/dij，dij依據問題的實際應用確定。

螞蟻遍歷所有的城市完成一次循環(huán)后，對路徑上的信息更新規(guī)則如式(2)所示：

萬元工業(yè)增加值用水量 萬元工業(yè)增加值用水量為工業(yè)用水量與工業(yè)增加值（萬元）的比值。其中工業(yè)用水量指工礦企業(yè)在生產過程中用于制造、加工、冷卻（包括火電直流冷卻）、空調、凈化、洗滌等方面的用水，按新水取用量計，不包括企業(yè)內部的重復利用水量。

(2)

式(2)中：ρ是信息揮發(fā)因子，用來表示隨著時間的推進信息素量的衰減程度，ρ=[0,1)，(1-ρ)表示信息殘留系數；τij(t+1) 是更新后的信息素量；τij(t)更新前的信息素量；Δτij是本次循環(huán)的信息素增量。

(3)

(4)

1.3 蟻群系統(tǒng)

蟻群系統(tǒng)(Ant Colony System，ACS)由M.Dorigo和Gambardella提出，用于改善蟻群的性能，ACS能在小規(guī)模的范圍內一個合適的時間找到較好的解。蟻群系統(tǒng)的改進方面有：

1) 狀態(tài)轉移規(guī)則。狀態(tài)轉移規(guī)則提供了一個更好合理地利用新路徑和先驗知識的方法，表達式如下：

(5)

其中q是[0，1]之間的隨機數，q0為一個狀態(tài)轉移參數，0≤q0≤1，V是US中某個節(jié)點，是個隨機變量，根據下式的狀態(tài)轉移概率選取，進行下一個節(jié)點選擇。

(6)

2) 全局更新規(guī)則。在最優(yōu)的螞蟻路徑上使用全局更新規(guī)則來提高算法的搜索效率，其式如下：

(7)

3) 局部信息素更新規(guī)則。在螞蟻構造路徑同時使用局部信息素更新規(guī)則來提高算法的搜索效率，如下式所示：

(8)

其中，τ0為初始信息素濃度，通常取τ0=(NLnn)-1，N為節(jié)點總數，Lnn為Greedy算法求解的總距離。蟻群系統(tǒng)的程序流程如圖2所示。

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

在數據庫系統(tǒng)中執(zhí)行一條查詢語句涉及到多個表，在查詢之前要先確定一條路徑連接相關的表，在產生的多種連接可能中大部分的連接代價是不相同的，當涉及表的數量大于10個時，找到一條代價較小的路徑就存在很大的困難，查詢優(yōu)化就是要通過一定的算法確定一條最優(yōu)的表連接次序，文獻[8]中提到了數據庫多表查詢優(yōu)化的方法。以下對查詢處理過程進行分析，并且建立多鏈接查詢優(yōu)化方法。

圖2 蟻群系統(tǒng)的程序流程

2.1 查詢處理

數據庫的主要功能是存儲和管理數據，向用戶提供查詢功能。Sitarz等[9]分析了模型參數的最優(yōu)化評估以利于查詢，當檢索數據時，SQL語句向關系數據庫管理系統(tǒng)(Relational Database Management System，RDBMS)提交請求，RDBMS處理查詢過程為：RDBMS接收到查詢請求(高級查詢語言書寫)后，首先對詞法和語法進行分析，再確認語義無誤后，產生查詢的內部表示(一般是查詢樹或查詢圖)，然后RDBMS選擇一個包含操作執(zhí)行順序、訪問外部文件方式、存儲中間結果的執(zhí)行策略，直到最后獲取查詢結果。RDBMS查詢執(zhí)行過程如圖3所示，查詢優(yōu)化是指在查詢過程中生成的多種執(zhí)行策略中，選擇一個最佳執(zhí)行策略的過程，文獻[10]中Gao,Shangce等作者給出了大型數據的蟻群算法動態(tài)定位問題，使得查詢過程更為簡便迅速。

圖3 查詢執(zhí)行過程

查詢優(yōu)化器的作用是產生查詢執(zhí)行計劃((Query Execution Plan，QEP)；查詢執(zhí)行引擎的作用是產生執(zhí)行查詢的代碼，并交給數據庫處理器獲取查詢結果。

SQL語言是標準的關系查詢語言，RDBMS能充分利用非過程性的語言(例如SQL語言)通過查詢優(yōu)化器對正在執(zhí)行的查詢生成一個有效的QEP，高效處理用戶的查詢請求。

2.2 查詢優(yōu)化器

用戶向數據庫提出查詢請求Q，查詢優(yōu)化器的目標是選擇最有效的QEP來完成對數據的讀取和返回。假設S是滿足Q的所有策略的集合，s是S中的元素，并且有一個相關聯(lián)的代價C(s)，查詢優(yōu)化算法的目標是找到s0∈minC(s),s∈S。

查詢優(yōu)化的最終目的就是減少查詢請求的反應時間，提升查詢效率,Dadaneh等[11]分析了蟻群算法的可能性選擇原則，提升查詢效率的同時，也優(yōu)化了系統(tǒng)的能量分配。在搜索空間較大時，如果尋找最佳QEP的優(yōu)化時間過久，那優(yōu)化時間和最佳QEP執(zhí)行時間之和會非常大，這不符合查詢優(yōu)化的最終目標。

查詢優(yōu)化的最終目標并不僅僅是找到一個最佳的QEP，而是找到一個恰當的QEP，滿足“優(yōu)化時間+恰當的QEP執(zhí)行時間”時間最短的條件?；诖四康模琇i,B.H等[12]給出了二位平面的最優(yōu)化蟻群算法，可以方便迅速定位。

一個查詢多數情況下對應多個QEP，這是由于一個查詢請求對應著大量的等價關系的代數表達式，并且任何一個代數表達式都可由大量的QEP實現(xiàn)。Mi,Nan等[13]進行了限制區(qū)域的蟻群最優(yōu)分配方法，用于鎖定求解空間。隨著Q中關系數的增加，Q對應的代數表達式集合和Q對應的QEP集合會以指數幅度增長。查詢優(yōu)化器對高級查詢語句的轉換過程示意圖如圖4所示。

圖4 高級查詢語句的轉換過程示意圖

查詢優(yōu)化器在浩瀚的搜索空間中，按照一定的原理依據代價估計函數評估所有的QEP，估計對應的代價，從中選取代價最小的QEP。

2.3 多連接查詢

多連接查詢((Multi-Join Query，MJQ)是指僅包含Select、Project、Join的查詢(SPJ查詢)經過投影、選擇操作并在優(yōu)化后得到的N個基關系連接操作構成的關系代數表達式。

對于多連接查詢得到一個優(yōu)化的關系連接次序是查詢優(yōu)化的核心，Xu,Bo等[14]給出了查詢過程中的最小限制下的最優(yōu)評估，查詢優(yōu)化器在對一個多連接的查詢優(yōu)化過程會使用不同方式的查詢表示，以下對查詢圖、連接樹和操作樹3種多連接查詢表示形式進行說明。查詢圖形式在查詢執(zhí)行過程的初期經過語法、詞法分析和語義確認后采用，中間經查詢優(yōu)化器轉換成的關系代數表達式采用連接樹形式。操作樹形式在最后物理優(yōu)化后的最佳QEP采用。

2.3.1 查詢圖

在多連接查詢中，join查詢圖為G=(V，E)，R∈V表示待連接關系，用大寫字母表示；(R1,R2)∈E表示一個連接操作，用數字表示。對于一個多連接查詢：(AjoinB)and (BjoinC)and (CjoinD)and (CjoinE)的查詢圖如圖5所示。

2.3.2 連接樹

查詢圖的每個可能的查詢計劃可由連接樹表示，葉子的節(jié)點表示數據庫的連接關系，中間節(jié)點對應左右節(jié)點連接的結果集，操作的順序是從上到下。圖6描述了圖5中查詢圖三種不同的查詢執(zhí)行計劃。

圖6 連接樹

邏輯優(yōu)化的目的是確定一個合適的join樹，左深樹是最常用的連接樹，本文采用以往查詢優(yōu)化算法中通用的策略，采用左深樹作為搜索策略空間。

2.3.3 操作樹

操作樹通常用來表示查詢請求經過物理優(yōu)化后，得到的實際連接的物理操作執(zhí)行順序。圖7表示圖6連接樹中左深樹物理優(yōu)化后的一個操作樹。連接操作實現(xiàn)的算法一般有嵌套循環(huán)連接(Nested Loop Join)、合并連接(Merge Join)、哈希連接(Hash Join)、索引連接(Index Join)。

圖7 操作樹

2.4 多連接查詢優(yōu)化

多連接查詢優(yōu)化(Multi-join Query Optimization，MJQO)是指在搜索的策略空間中找到一個最優(yōu)的join樹，并且為join樹中的每個連接操作選取有效的join方法，MJQO問題也是邏輯優(yōu)化和物理優(yōu)化問題。Talafuse,T.P等[15]建立了冗余分配計算方法，可以借鑒到多鏈接優(yōu)化查詢中。多連接查詢優(yōu)化算法的執(zhí)行時間長短和尋找到的QEP的大小代價取決于以下3個方面：

2.4.1 搜索空間

一個多連接查詢包含大量的QEP，這構成了該多連接查詢的策略空間，一般而言策略空間很大，查詢優(yōu)化算法通常不在整個策略空間搜索，而是在最佳的QEP可能存在的空間搜索，這個策略空間的子集就是搜索空間。

搜索策略空間一般分為3種，分別是最佳QEP、有效QEP和低效QEP。

2.4.2 代價估計函數

查詢執(zhí)行計劃的代價包括：I/O代價、存儲代價、計算代價和通信代價，分別以字母I、S、E、C表示，代價的權值分別用Pi、Ps、Pe、Pc表示，則查詢執(zhí)行計劃的表達式如下式，其中Pi+Ps+Pe+Pc=1。

Cost=I*P+S*P+E*Pe+C*Pc

(9)

假設一個含有n個關系的連接樹，(j1,j2,…,ji)是連接樹的非葉子節(jié)點(內部節(jié)點)，則代價評估模型如下式：

(10)

對于一個連接JjoinS代價的計算式如下式。

(11)

其中V(c,R)的計算式如下式所示

(12)

2.4.3 搜索算法

查詢優(yōu)化器的搜索算法目標是在一個指定的搜索空間找到一個高效的QEP。

確定搜索空間后要選定一種高效的搜索算法，滿足“優(yōu)化時間+恰當的QEP執(zhí)行時間”時間最短。查詢優(yōu)化搜索算法大致分為窮盡搜索算法、局部隨機搜索算法和啟發(fā)式搜索算法3種。蟻群算法屬于啟發(fā)式搜索算法，本文針對改進的蟻群算法對查詢優(yōu)化器的搜索算法進行分析研究。

3 蟻群算法對多連接查詢優(yōu)化問題的描述

通過對多連接查詢優(yōu)化問題的描述，對比典型的TSP問題，可以發(fā)現(xiàn)多連接查詢優(yōu)化問題和TSP問題有很多的相似之處，將數據庫中的每個關系(表)當作一個城市，將兩個關系(表)之間的join方法(連接代價)當作一個城市到另一個城市的開銷，這樣多連接查詢優(yōu)化問題就轉換為類似TSP的問題，而蟻群算法能夠很好地解決TSP問題。

本文采用左線性樹空間作為搜索空間，多連接查詢優(yōu)化問題可以簡單地描述為：以頂點集V中所有的頂點作為葉節(jié)點構造一棵最小代價的二叉樹(QEP)，每個頂點出現(xiàn)并僅出現(xiàn)一次。

MJQO問題和TSP問題也存在著明顯的差別，為了簡化問題，本文只考慮的區(qū)別是MJQO問題的任意一個解中，vi和vj兩個相鄰的頂點之間的代價不固定，由頂點vi、vj本身和vi、vj之前的頂點集合的共同特點決定。

基于左線性空間多連接查詢優(yōu)化問題(L-MJQO)，考慮到查詢執(zhí)行計劃在時間和空間上的復雜性，并且其價評估取決于操作結果集的記錄數目，所以將L-MJQO問題簡化為查詢中n個表(關系)的join樹連接次序的邏輯優(yōu)化問題，這樣多連接查詢優(yōu)化問題就轉化成類似典型TSP問題。

采用避免笛卡爾積當作啟發(fā)信息來縮小搜索空間，圖8給出了基于蟻群系統(tǒng)的L-MJQO算法流程圖。

算法的主要步驟如下：

步驟1：初始化參數(信息素分布參數等)；

步驟2：將m只螞蟻隨機地置于查詢圖的某一頂點；

步驟3：設置螞蟻的狀態(tài)向量Tag=[0…0]，Tag(k)=0表示第k只螞蟻要繼續(xù)添加接成分；Tag(k)=1表示第k只螞蟻已經完成了解構造；

步驟4：判斷是否所有的螞蟻均完成解構造，即判斷是否Tag=[1…1]，若滿足條件則執(zhí)行步驟9，否則令k=1；

步驟5：判斷第k只螞蟻是否完成解構造，若滿足則執(zhí)行步驟8，否則按照狀態(tài)轉移規(guī)則選擇先一個與當前結果不產生笛卡爾積關系的關系節(jié)點；

步驟6：使用局部信息更新規(guī)則對剛走過的路徑修改信息素量；

步驟7：依據搜索停止函數判斷該螞蟻是否滿足解構造，滿足則Tag(k)=1；

步驟8：判斷是否k=m，滿足則執(zhí)行步驟10，不滿足則令k=k+1執(zhí)行步驟5；

步驟9：依據適應度評價函數計算螞蟻所構造的m個QEP的適應值，并記錄當前最優(yōu)解；

步驟10：使用全局信息素更新規(guī)則對全局最優(yōu)解所處的路徑修改信息素量；

步驟11：判斷是否滿足停止條件，滿足則算法停止，否則執(zhí)行步驟2。

該算法的輸入量是查詢Q涉及的所有的基關系的集合，輸出量是查詢Q中查詢代價最小的QEP。

下面結合多連接查詢優(yōu)化問題對個別參數進行。

Nc：迭代次數；

table：一個多連接查詢包含的表信息(表的編號和基數)；

attribute：表之間的公共屬性信息矩陣(表的編號、公共屬性編號和該公共屬性在表中取不同值的個數)；

graph：表之間表示查詢圖的連通關系矩陣；

ηij：定義ηij=D(j)/N(j)為啟發(fā)式信息；

τ0：信息素初始值τ0=1/NCmin，N是查詢Q涉及的基關系總數，Cmin是查詢Q采用Greedy算法得到的最小QEP的代價。

局部搜索算法：采用Greedy算法(圖8)。

圖8 基于蟻群系統(tǒng)的L-MJQO程序流程

4 實驗結果及分析

4.1 算法參數設置的影響

蟻群算法中參數的選擇對其算法性能有重要影響，但其選取的方法和原則一般是依據實驗經驗確定。本節(jié)的實驗主要研究α、β、ρ三個參數的不同取值對算法的影響，討論其設定的最佳原則。

實驗數據為5個關系表n=5，迭代次數為N=200，螞蟻的數目選取經驗值m=10，q0=0.2，取α=1，β=4，ρ=0.5，實驗內容僅考慮α、β、ρ值對算法的影響，所以其他參數的值保持不變，依次改變α、β、ρ的值，運行次數為50，取最優(yōu)解的平均值，得到仿真結果。

1) 信息揮發(fā)因子對算法的影響，取α=1，β=4，ρ的取值為0，0.1，0.2，…，1，ρ的每個數據各自運行50次，取最優(yōu)解的平均值，得到信息揮發(fā)因子對算法的影響如圖9所示。

當ρ∈[0.5,0.8]時，最優(yōu)解比較穩(wěn)定，算法的性能比較好。這是因為ρ的雙重性，當ρ較小時，路徑上的殘留信息較多，正反饋作用減弱，螞蟻搜索的隨機性增強，算法的收斂速度慢；當ρ較大時，正反饋作用增強，螞蟻搜索隨機性減弱，算法的收斂速度加快，但容易陷入局部最優(yōu)。

圖9 信息揮發(fā)因子對算法的影響

2) 信息啟發(fā)因子對算法的影響，取β=4，ρ=0.5，α的取值為0，0.5，1，…，5，α的每個數據各自運行50次，取最優(yōu)解的平均值，得到信息啟發(fā)因子對算法的影響如圖10所示。

圖10 信息啟發(fā)因子對算法的影響

當α∈[1,2]時算法有較好的求解性，這是由于在α較大時，對螞蟻運動的指導性程度強，走過重復路徑的可能性小，搜索隨機性減弱；α較小時，螞蟻的搜索會過早的陷入局部的最優(yōu)解。

3) 期望啟發(fā)因子對算法的影響，取α=1，ρ=0.5，β的取值為0，1，2，…，10，α的每個數據各自運行50次，取最優(yōu)解的平均值，得到期望啟發(fā)因子對算法的影響如圖11所示。

圖11 期望啟發(fā)因子對算法的影響

當β∈[2,5]時算法有較好的求解性，這是因為β表示螞蟻在運動過程中啟發(fā)信息對螞蟻搜索指導的重要程度，在β過大時，啟發(fā)信息的作用程度增加，減弱了螞蟻搜索的隨機性，螞蟻的搜索易限于局部的最優(yōu)解。

由以上的實驗數據可知，α、β、ρ參數的取值對算法的影響很大，所以在采用蟻群算法解決多連接查詢優(yōu)化問題時，要合理的設置α、β、ρ值。

4.2 算法求解性能比較

本節(jié)在討論相同的實驗條件下，針對多連接查詢中表個數的不同，比較Greedy算法、遺傳算法和蟻群算法3種不同算法求解時的查詢執(zhí)行代價和QEP的生成時間，每個算法運行40次，然后取平均值。

遺傳算法參數：N=50，Pc=0.6，Pm=0.12，進化代數G=100。

蟻群算法參數：α=1，β=3，ρ=0.8，q0=0.2螞蟻個數m=10，迭代次數N=200。

1) 取多連接查詢的關系表的個數為5，10，15，…，50，計算遺傳算法和Greedy算法的查詢執(zhí)行代價，并除以蟻群算法得到的查詢執(zhí)行代價，得到一個標量值。其結果如圖12所示。

圖12 查詢代價比較

遺傳算法和Greedy算法求得的最佳QEP的代價均大于蟻群算法，并且隨著表個數的增加，其執(zhí)行代價比值也逐漸增加，Greedy算法的執(zhí)行代價增長幅度比遺傳算法高很多。當表的數目是50時，遺傳算法執(zhí)行代價是蟻群算法的10倍左右，Greedy算法執(zhí)行代價是蟻群算法的100倍左右，所以當表的數目較多時，遺傳算法和Greedy算法不適合用于多連接查詢的優(yōu)化。

2) 取多連接查詢的關系表的個數為5,10,15，…,50，分別得到蟻群算法、遺傳算法和Greedy算法的最優(yōu)QEP的運行時間，其結果如圖13所示。

圖13 最優(yōu)解時間比較

隨著表的個數增加3種算法求得最優(yōu)解的時間都有所增加，其中遺傳算法的增長速度最快，Greedy算法和蟻群算法的增長比較平緩，由于Greedy算法沒有迭代計算的過程，所以求解的時間最短。

隨著表數目由5～50變化時，上述3種算法的查詢代價和最優(yōu)解時間如表1和表2所示。

綜合比較可以得出，Greedy算法求解過程時間較短，但運行的查詢執(zhí)行代價過大，求解品質變差，求解結果變得不再可用；遺傳算法運行過程的執(zhí)行代價較小，但最優(yōu)解的執(zhí)行時間過長，查詢效率較低。所以，當表數目較大時，蟻群算法在求解品質和求解時間都比較好。

表1 查詢代價

表2 最優(yōu)解時間

5 結論

多連接查詢優(yōu)化是個復雜的問題，本文采用基于蟻群系統(tǒng)實現(xiàn)多連接次序的優(yōu)化，引入局部信息素更新規(guī)則和偽隨機變量，找出最優(yōu)的連接路徑。通過實驗結果表明，在大型的數據庫查詢中，可以利用蟻群算法提高求解性能和求解速度，這對數據庫查詢設計和實踐有重要的借鑒作用。

[1] 崔峰峰,南振岐.基于蟻群算法的分布式數據庫查詢優(yōu)化方法[J].計算機時代,2014(5):47-49.

[2] 胡楓.一種分布式數據庫多元連接查詢優(yōu)化算法及改進[J].計算機工程與應用，2011(16):125-127.

[3] VIJAY KUMAR T V.Vikram Singh and Ajay Kumar Verma.Distributed Query Processing Plans Generation Using Genetic Algorithm[J].International Journal of Computer Theory and Engineering,2012,3(1):38-45.

[4] ZHOU ZEHAI.Using Heuristics and Genetic Algorithms for Large-scale Database Query Optimization[J].Journal of Information and Computing Science,2010,2(4):261-280.

[5] CHEN POHAN,Seyed Mohsen Shahandashti.Hybrid of Genetic Algorithm and Simulated Annealing for Multiple Project Scheduling with Multiple Resource Constraints[J].Automation in Construction.2012,18(4):434-443.

[6] WEI L Y,ZHAO M.A Niche Hybrid Genetic Algorithm for Global Optimization of Continuous Multimodal Functions[J].Applied Mathematics and Computation,2013,160(3):649-661.

[7] 張大衛(wèi),李濤.基于量子蟻群算法的數據庫連接查詢優(yōu)化[J].微型電腦應用,2014(5):40-43.

[8] 李文俊,張愛林.數據庫多表查詢優(yōu)化技術[J].計算機系統(tǒng)應用,2014(6):54-59.

[9] SITARZ,PIOTR,POWALKA,BARTOSZ.Modal Parameters Estimation Usingant Colony Optimization Algorithmn[J].Mechanical Sysems and Signal Processing,2016(76/77):531-554.

[10]GAO,SHANGCE,WANG,YIRUI,CHENG,JIUJUN.Ant Colony Optimization with Clustering for Solving the Dynamic Location Routing Problem[J].Applied Mathemamatics and Computation,2016(285):149-173.

[11]DADANEH,BEHROUZ ZAMANI,MARKID,HOSSEIN YEGANEH,ZAKEROLHOSSEINI.Ali Unsupervised Probabilistic Feature Selection Using ant Colony Optimization[J].Expert Systens with Application,2016(53):27-42.

[12]LI B H,LU M,SHAN Y G. Parallel Ant Colony Optimization for the Determination of a Point Heat Source Position in a 2-D Domain[J].Applied Thermal Engineering,2015(91):994-1002.

[13]MI,NAN,HOU,JINGWEI,MI.Wenbao Optimal Spatial Land-use Allocation for Limited Development Ecological Zones Based on the Geographic Information System and a Genetic Ant Colony Algorithm[J].International Journal of Geographical Information Science,2015,29(12):2174-2193.

[14]XU BO,MIN.Huaqing Solving Minimum Constraint Removal (MCR) Problem Using a Social-force-model-based Ant Colonyalgorithm[J].Applied Soft Computing,2016,(43):553-560.

[15]TALAFUSE T P,POHL E A.A Bat Algorithm for the Redundancy Allocation Problem[J].Engineering Optimizaton 2016,48(5):900-910.

[16]張正柱，劉林真．基于WebService的煙花溯源查詢系統(tǒng)的設計與實現(xiàn)[J].重慶理工大學學報(自然科學)，2015(2)：82-85.

(責任編輯 楊繼森)

Research on Multi-Join Query Optimization Based on Ant Colony Algorithm

ZHANG Lan-yong, GENG Wen-jie, LIU Sheng

(College of Automation, Harbin Engineering University, Harbin 150001, China)

This paper introduced the ant colony algorithm (ACA) to the database query. It listed the basic principles and program process and improved the traditional ACA. The local pheromone update rule and pseudo-random proportion were introduced to the ACA, and then this paper built a multi-join query optimization model based on ant colony system (ACS), and experiments were carried out. The experiments show that this algorithm has the better effect on optimal solution quality and optimal solution time of multi-join query optimization problem when the number of tables is large in your database.

ant colony algorithm; multi-join query optimization; database query; optimal solution

2016-05-10；

2016-06-15

國家自然科學基金(51579047); 國家科技支撐計劃(2013BAG25B01)；毫米波國家重點實驗室開放課題(K201707);MPRD專項資助(IEP14001)；博士點基金(20132304120015)；中央高?；究蒲袠I(yè)務費(HEUCF160414)

張?zhí)m勇(1983—)，男，博士，講師，主要從事控制理論與控制工程、隨機信號處理等研究。

10.11809/scbgxb2016.10.015

張?zhí)m勇，耿文杰，劉勝.基于蟻群算法的多連接查詢優(yōu)化問題研究[J].兵器裝備工程學報，2016(10):72-79.

format:ZHANG Lan-yong, GENG Wen-jie, LIU Sheng.Research on Multi-Join Query Optimization Based on Ant Colony Algorithm[J].Journal of Ordnance Equipment Engineering,2016(10):72-79.

TP311

A

2096-2304(2016)10-0072-08