基于退火遺傳算法的多連接查詢優(yōu)化應(yīng)用研究*

趙宇蘭

(山西大學(xué)商務(wù)學(xué)院 信息學(xué)院，山西 太原 030031)

0 引言

查詢優(yōu)化是數(shù)據(jù)庫技術(shù)的研究重點(diǎn)，而多連接查詢(Multi-Join Query,MJQ)是查詢優(yōu)化的一個(gè)技術(shù)難點(diǎn)。在分布式數(shù)據(jù)庫中，MJQ連接次序的選擇是影響查詢性能的關(guān)鍵因素，如何尋找多個(gè)關(guān)系的最佳連接次序，使得查詢的執(zhí)行代價(jià)最小，仍然是一個(gè)NP-hard問題。本文應(yīng)用退火遺傳算法來解決多連接查詢優(yōu)化問題，通過實(shí)驗(yàn)得到一組遺傳控制參數(shù)的最佳值，并比較了在連接關(guān)系個(gè)數(shù)不同情況下本文算法與基本遺傳算法的性能。

1 MJQ問題描述

在傳統(tǒng)的關(guān)系數(shù)據(jù)庫應(yīng)用中，單個(gè)查詢涉及的關(guān)系個(gè)數(shù)N通常比較小(N<10)，關(guān)系中包含的元組個(gè)數(shù)也不多。隨著現(xiàn)代數(shù)據(jù)庫應(yīng)用復(fù)雜性的需要以及數(shù)據(jù)量的急劇膨脹，單個(gè)查詢中包含的Join數(shù)也在增加，這為多連接查詢的優(yōu)化增加了難度。

MJQ問題可以采用查詢圖G=(V,E)描述，其中，R∈V為查詢圖中所有結(jié)點(diǎn)的集合，即基關(guān)系集；J∈E為查詢圖中無向邊的集合，即連接操作。

對于一個(gè)多連接查詢Q=(R1joinR2)AND(R2joinR3)AND(R3joinR4) AND(R4joinR5) AND(R5joinR2)，對應(yīng)的查詢圖如1所示。

圖1 MJQ圖

圖1的任何一種可能的連接序列可以轉(zhuǎn)化為一種連接樹。查詢Q的搜索空間為上述5個(gè)基關(guān)系的所有排列。n個(gè)基關(guān)系對應(yīng)的連接樹的數(shù)目T(n)在不排除笛卡爾積的情況下可以由如下遞歸形式表示[4]：

(1)

將基關(guān)系的連接次序考慮在內(nèi)，對于n個(gè)基關(guān)系，則存在T(n)=T(n)n種不同形態(tài)的二叉樹。一個(gè)MJQ對應(yīng)的所有可能的查詢語法樹，構(gòu)成了MJQ的計(jì)劃搜索空間[5]。

MJQ問題的求解目標(biāo)就是在計(jì)劃搜索空間中尋找邏輯等價(jià)的執(zhí)行代價(jià)最小的連接樹。由于查詢處理的代價(jià)與中間操作結(jié)果的元組數(shù)目相關(guān)，因此MJQ的執(zhí)行代價(jià)可以用MJQ過程中產(chǎn)生的中間結(jié)果的元組數(shù)的總和表示。

假設(shè)一個(gè)連接操作J=R1joinR2，在屬性值均勻分布的情況下，計(jì)算代價(jià)為：

(2)

其中，|R|表示關(guān)系R的元組數(shù)；C表示R1和R2的公共屬性集，ci為R1和R2的某個(gè)公共屬性；v(s,R)表示R中屬性s的不同取值的數(shù)目。

(3)

假設(shè)多連接查詢中包含n個(gè)基關(guān)系，則每個(gè)查詢計(jì)劃的執(zhí)行代價(jià)cost可以通過連接樹中所有中間關(guān)系Ji的元組數(shù)的總和進(jìn)行估算，估算公式為：

.(4)

MJQ優(yōu)化的目標(biāo)是找出查詢計(jì)劃集合C中的一個(gè)c0使其滿足

cost(c0)≈mincost(c),c∈C.

(5)

2 利用模擬退火算法對遺傳算法進(jìn)行改進(jìn)

基本遺傳算法(Simple Genetic Algorithm，SGA)的形式化定義為8元組：SGA=(C，P0，E，M，Ps，Pc，Pm，T)，其中，C為染色體編碼方法，P0為初始種群，E為染色體的適應(yīng)度函數(shù)， M為群體規(guī)模，Ps為選擇算子，Pc為交叉算子，Pm為變異算子，T為算法終止條件[5]。為了避免遺傳算法過早收斂，楊藝等在SGA算法中引入了模擬退火機(jī)制，形成了退火遺傳算法(Simulated Annealing-Genetic Algorithm，SA-GA)。SA-GA算法的主要實(shí)現(xiàn)步驟見表1。

表1 SA-GA算法的實(shí)現(xiàn)步驟

3 SA-GA算法在MJQ優(yōu)化中的應(yīng)用

3.1 生成有效連接樹

假設(shè)R為查詢圖G所有基關(guān)系集，J為連接操作序列集合，根據(jù)查詢圖G構(gòu)造一棵連接樹的算法?？紤]到連接樹生成過程中，沒有連接屬性的關(guān)系存在笛卡兒積，影響算法的效率，因此，加入啟發(fā)式信息來避免產(chǎn)生無效連接樹。

連接樹生成算法實(shí)現(xiàn)過程如下：

Create_tree()

{計(jì)算J中連接操作的個(gè)數(shù)n

FOR 1 .. n DO

{ LTree=R中包含J的左關(guān)系結(jié)點(diǎn);

RTree=R中包含J的右關(guān)系結(jié)點(diǎn);

IF LTree<>RTree

以LTree為左子樹，RTree為右子樹，Ji 為根結(jié)點(diǎn)，建立連接子樹SubTree;清除R中的LTree和RTree;插入到R中;

END IF

END FOR

END Create_tree

3.2 設(shè)計(jì)適應(yīng)度函數(shù)

由于連接樹的代價(jià)越小，其對應(yīng)的執(zhí)行計(jì)劃越優(yōu)，查詢效率越高。本算法依據(jù) (2)(3)(4)式中MJQ代價(jià)模型設(shè)計(jì)適應(yīng)度函數(shù)，其表達(dá)式如下：

E(Ji)=(1/cost(Ji)).

(6)

其中，E(Ji)為第J代種群中染色體Ji的適應(yīng)度函數(shù)值。

3.3 生成初始種群

SA-GA算法的演化過程在不斷變化的種群中完成，因此初始種群的生成和種群規(guī)模會直接影響算法的效率。對于查詢圖G，生成初始種群的過程如下：

FOR i=1 .. p_size DO

Create_tree();

按照3.1染色體編碼規(guī)則生成一個(gè)染色體;

加入染色體到初始種群p0;

ENDFOR

4 實(shí)驗(yàn)設(shè)計(jì)和結(jié)果分析

4.1 實(shí)驗(yàn)設(shè)計(jì)

實(shí)驗(yàn)過程分三個(gè)步驟進(jìn)行：

1) 測試初始種群規(guī)模對查詢計(jì)劃執(zhí)行代價(jià)值的影響。

2) 算法執(zhí)行300代，分析歷代適應(yīng)度函數(shù)變化趨勢，測試算法的收斂性。

3) 對SA-GA和SGA進(jìn)行對比實(shí)驗(yàn)，驗(yàn)證SA-GA算法的有效性。

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

1) 不同初始種群p_size下的SA_GA性能比較

隨機(jī)生成10個(gè)關(guān)系，測試不同種群規(guī)模下算法執(zhí)行5次的計(jì)劃生成代價(jià)均值。其他控制參置為：進(jìn)化代數(shù)Max為300，交叉概率Pc1=0.9、Pc2=0.4，變異概率Pm1=0.1、Pm2=0.006，退火初始溫度T0=2 000，溫度冷卻參數(shù)β=0.6。運(yùn)行結(jié)果如表2。

表2 不同種群p_size下的運(yùn)行結(jié)果

從表2數(shù)據(jù)看出，當(dāng)p_size=100 時(shí)，SA_GA算法的性能要優(yōu)于p_size=30和p_size=50，并與p_size=150時(shí)差別不大，因此p_size=100為較好的選擇。

2) 測試歷代適應(yīng)度函數(shù)變化趨勢

以10個(gè)關(guān)系的連接操作為例，初始種群規(guī)模100，其他參數(shù)同1)，算法執(zhí)行5次取均值，經(jīng)過300代遺傳，適應(yīng)度函數(shù)變化趨勢如圖2。

圖2 適應(yīng)度函數(shù)變化趨勢

從圖2可知，算法經(jīng)過200代遺傳后適應(yīng)度函數(shù)值趨于穩(wěn)定，連續(xù)保持最佳100代，執(zhí)行代價(jià)為5 695，計(jì)劃生成時(shí)間為0.785 698秒。實(shí)驗(yàn)結(jié)果證明算法具有良好的收斂性，可以得到最優(yōu)解。

3) SA-GA與SGA的對比分析

測試關(guān)系個(gè)數(shù)分別為2～30時(shí)，SA-GA和SGA的計(jì)劃執(zhí)行代價(jià)、計(jì)劃生成時(shí)間和查詢響應(yīng)時(shí)間。對于不同關(guān)系個(gè)數(shù)情況下的查詢，兩種算法各執(zhí)行10次取平均值。圖3是不同關(guān)系個(gè)數(shù)下兩種算法計(jì)劃執(zhí)行代價(jià)對比圖。圖4是不同關(guān)系個(gè)數(shù)下兩種算法的響應(yīng)時(shí)間對比圖。圖5是不同關(guān)系個(gè)數(shù)下兩種算法計(jì)劃生成時(shí)間對比圖。

圖3 兩種算法的計(jì)劃執(zhí)行代價(jià)對比

圖4 兩種算法的查詢響應(yīng)時(shí)間對比

圖5 兩種算法的計(jì)劃生成時(shí)間對比

實(shí)驗(yàn)結(jié)果表明，當(dāng)連接的關(guān)系數(shù)小于4時(shí)，兩種算法的計(jì)劃執(zhí)行代價(jià)和計(jì)劃生成時(shí)間基本相同。但隨著連接的關(guān)系數(shù)的增加，SA-GA算法的查詢優(yōu)化效果明顯好于SGA，查詢響應(yīng)時(shí)間降低了近50%。這是因?yàn)椴捎米赃m應(yīng)交叉和變異概率，增加了種群的多樣性，有效地平衡了算法的全局與局部搜索能力，大幅度地降低了計(jì)劃執(zhí)行代價(jià)。

不足的是，SA-GA算法的計(jì)算復(fù)雜度要高于SGA算法，因此，計(jì)劃生成時(shí)間要比SGA算法長。但由于SA-GA算法能生成比SGA算法更優(yōu)的查詢執(zhí)行計(jì)劃，且執(zhí)行代價(jià)更低，響應(yīng)時(shí)間更短，可以在可接受的計(jì)劃生成時(shí)間內(nèi)得到近似于最優(yōu)的計(jì)劃。

5 總結(jié)

針對遺傳算法局部搜索能力不強(qiáng)，容易過早收斂的弊端，將模擬退火機(jī)制引入到種群的交叉、變異過程中，以期獲得全局最優(yōu)解。仿真實(shí)驗(yàn)驗(yàn)證了退火遺傳混合算法在MJQ中的有效性。實(shí)驗(yàn)結(jié)果表明，連接關(guān)系數(shù)越多，該算法的尋優(yōu)效果越顯著。但是，由于遺傳算法本身的局限性，遺傳算子的設(shè)計(jì)以及兩種變異的變異率對算法的影響還需要做更多的研究與改進(jìn)。