蔣國(guó)唯　王建軍

摘要：物化視圖能夠提高數(shù)據(jù)倉(cāng)庫(kù)的查詢(xún)響應(yīng)能力，但物化視圖集的選擇卻很復(fù)雜。該文提出了一個(gè)如何選擇物化視圖集的優(yōu)化遺傳算法，在有限的存儲(chǔ)空間下，使查詢(xún)性能和視圖維護(hù)代價(jià)較小。提出一個(gè)查詢(xún)維護(hù)代價(jià)模型，并優(yōu)化了交叉算子。實(shí)驗(yàn)結(jié)果表明，該算法在執(zhí)行代價(jià)上優(yōu)于經(jīng)典的遺傳算法。

關(guān)鍵詞：遺傳算法；物化視圖；代價(jià)模型；交叉算子

中圖分類(lèi)號(hào)：TP18 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）03-0203-04

1 背景

數(shù)據(jù)倉(cāng)庫(kù)[1]是面向主題的、非易失的、能夠反映歷史變化的、集成的數(shù)據(jù)集合。近年來(lái)，數(shù)據(jù)倉(cāng)庫(kù)廣泛應(yīng)用于各行各業(yè)，并且數(shù)據(jù)量迅猛增長(zhǎng)，查詢(xún)響應(yīng)所需時(shí)間也越來(lái)越長(zhǎng)，查詢(xún)優(yōu)化成為數(shù)據(jù)倉(cāng)庫(kù)中的一個(gè)研究熱點(diǎn)。查詢(xún)優(yōu)化主要包含索引優(yōu)化和物化視圖技術(shù)。

物化視圖選擇問(wèn)題是數(shù)據(jù)倉(cāng)庫(kù)領(lǐng)域的研究熱點(diǎn)之一。斯坦福大學(xué)的Harinarayan[2]在1996年最早提出物化視圖選擇問(wèn)題，此后貪婪算法BPUS（Benefit Per Unit Space）成了經(jīng)典的物化視圖選擇算法。該算法基于多維數(shù)據(jù)格，所得結(jié)果與最優(yōu)解的收益比不低于0.63。Shukla A在1998年提出了PBS（Pick By Size）算法[3]，解決了貪婪算法在維度很高的情況下計(jì)算最大收益效率過(guò)低、計(jì)算量大的缺點(diǎn)。GIA（Greedy Interchange Algorithm）算法是斯坦福大學(xué)的Gupta提出的[4]，它基于AND-OR圖。1997年J.Yang等人最先提出用遺傳算法解決物化視圖選擇問(wèn)題[5]，根據(jù)多視圖處理計(jì)劃（Multiple View Processing Plan，MVPP），通過(guò)合并可以“共享”的公共子視圖得到最好的多視圖處理計(jì)劃，然后從多視圖處理計(jì)劃里選取視圖物化。隨后利用遺傳算法解決物化視圖選取問(wèn)題成為熱點(diǎn)研究問(wèn)題[6]。類(lèi)似地，Kirkpatrick[7]提出了基于模擬退火算法的視圖選擇算法，模擬退火算法是一種基于Monte Carlo迭代求解法的啟發(fā)式隨機(jī)搜索算法，常常用于多維數(shù)的物化視圖選取問(wèn)題中。但是，基于模擬算法的視圖選擇效果依賴(lài)于正確的參數(shù)選擇，好的參數(shù)選擇往往需要進(jìn)行多次實(shí)際測(cè)試。

靜態(tài)物化視圖選擇算法如上所述，另有動(dòng)態(tài)物化視圖選擇算法。動(dòng)態(tài)算法在查詢(xún)過(guò)程中動(dòng)態(tài)的對(duì)物化視圖進(jìn)行增刪改操作，以滿足盡可能多的查詢(xún)需求，主要包括包括DynaMat算法、Chunk算法和Cache算法。

十幾年以來(lái)，人們對(duì)物化視圖選擇問(wèn)題進(jìn)行了大量而深入的研究，在這方面的研究也比較活躍的有國(guó)內(nèi)的國(guó)防科技大學(xué)、復(fù)旦大學(xué)以及香港科技大學(xué)等。國(guó)內(nèi)的學(xué)者也提出了許多物化視圖選擇算法的改進(jìn)算法。王宜貴建立了代價(jià)估算模型，以物化視圖的存儲(chǔ)代價(jià)和查詢(xún)的時(shí)間開(kāi)銷(xiāo)作為衡量標(biāo)準(zhǔn)，改進(jìn)了基于遺傳算法的物化視圖優(yōu)化算法[8]。王自強(qiáng)、孫霞提出增強(qiáng)遺傳算法[9]。趙秀麗提出蟻群算法[10]，采取對(duì)信息素的全局和局部更新，并局部搜索每次迭代的最優(yōu)解。龔安提出蟻群-遺傳算法[11]，利用遺傳算法的較強(qiáng)全局搜索能力優(yōu)化蟻群算法每次的搜索結(jié)果，并且在進(jìn)行信息素更新時(shí)同時(shí)考慮最差路徑和最優(yōu)路徑上的信息素，改進(jìn)后的算法最優(yōu)解的收斂速度提高了，解決了存在于蟻群算法中的“早熟”停滯現(xiàn)象。徐海濤提出了一種混合算法，混合算法結(jié)合了模擬退火算法和遺傳算法的優(yōu)點(diǎn)[12]，解決物化視圖的選擇效果很好。

數(shù)據(jù)倉(cāng)庫(kù)中的物化視圖選擇影響查詢(xún)效率和OLAP分析質(zhì)量，目前基于遺傳算法的物化視圖選擇問(wèn)題已成為重要的研究熱點(diǎn)問(wèn)題。

2 遺傳算法

遺傳算法基于達(dá)爾文的“自然選擇，適者生存”原理，是一種模擬生物演化過(guò)程的搜索最優(yōu)解算法[13]。遺傳算法主要包括三個(gè)重要操作，即選擇、交配和變異，從任意一個(gè)代表問(wèn)題可能潛在的解集的初始種群出發(fā)，經(jīng)過(guò)不斷逐代演化最終進(jìn)化到最適應(yīng)環(huán)境的群體。遺傳算法的主要幾個(gè)步驟如下所述。

1）二進(jìn)制編碼。多維視圖格模型中，一個(gè)視圖格對(duì)應(yīng)一個(gè)n位的基因編碼，n是視圖格的總節(jié)點(diǎn)個(gè)數(shù)。某一位的編碼是0，那么該位對(duì)應(yīng)的節(jié)點(diǎn)不必物化；若編碼是1，該位對(duì)應(yīng)的節(jié)點(diǎn)需要物化。比如視圖格包含節(jié)點(diǎn)v1，v2…v8，如果基因編碼為11000001，那么應(yīng)該選擇節(jié)點(diǎn)v1，v2，v8進(jìn)行物化。

2）適應(yīng)度函數(shù)。適應(yīng)度一般是物化視圖的收益值。定義如下適應(yīng)度函數(shù)：

3）隨機(jī)生成初始種群。初始化N個(gè)染色體。

4）各種遺傳算法算子。選擇算子設(shè)定為2個(gè)染色體中適應(yīng)度較大者用于繁殖下一代。交叉算子設(shè)定為交換二進(jìn)制編碼交叉點(diǎn)之前的二進(jìn)制位，交叉點(diǎn)后面的二進(jìn)制位保持不變。變異算子操作是二進(jìn)制編碼的某一位或者某幾位以一定概率取反。例如染色體11010100和染色體11101010，交叉操作在第4位得到11100100與11011010，變異操作在第2位則為10010100 與10101010。

遺傳算法的流程圖如下圖：

遺傳算法的求解能力很強(qiáng)，并且它和最優(yōu)解的收益比非常高，有著迅速的全局搜索能力，這優(yōu)于蟻群算法的局部搜索能力強(qiáng)，遺傳算法搜索結(jié)果也優(yōu)于貪心算法等啟發(fā)式算法。然而不當(dāng)?shù)倪z傳算子會(huì)導(dǎo)致遺傳算法收斂速度很慢，而且隨機(jī)性特點(diǎn)使得算法收斂慢，對(duì)算法的性能造成影響。

經(jīng)典的GA算法在演化初期選擇壓力（最佳個(gè)體選中的概率與平均選中概率的比值）大，選中適應(yīng)度高的個(gè)體，這些個(gè)體會(huì)控制演化過(guò)程，進(jìn)而得出局部最優(yōu)解，造成群體收斂早熟。在演化后期群體適應(yīng)度值的差異較小，對(duì)應(yīng)選擇壓力減小，收斂速度也降低很多。

針對(duì)上面描述的問(wèn)題，本文提出了基于遺傳算法的改進(jìn)物化視圖選擇算法，我們通過(guò)新的代價(jià)模型、修改進(jìn)化算子，用預(yù)處理算法生成初始解來(lái)對(duì)經(jīng)典GA進(jìn)行優(yōu)化。

3 代價(jià)模型

物化視圖的使用并不是萬(wàn)能的，也有其缺陷：

1）物化視圖也要在數(shù)據(jù)庫(kù)中存儲(chǔ)，一定的存儲(chǔ)空間占用也是必需的。

2）數(shù)據(jù)倉(cāng)庫(kù)不定期更新，新加入的數(shù)據(jù)在物化視圖中沒(méi)有存儲(chǔ)，因此物化視圖需要維護(hù)更新，必須要保持和基礎(chǔ)數(shù)據(jù)表中的數(shù)據(jù)同步。

因此，哪些視圖被物化是一個(gè)復(fù)雜的問(wèn)題，需要按照查詢(xún)的實(shí)際需求，并將存儲(chǔ)代價(jià)、視圖維護(hù)代價(jià)和查詢(xún)代價(jià)三個(gè)因素全部納入考慮范圍，以選擇需要物化的視圖。本文提出了一種查詢(xún)維護(hù)代價(jià)模型。

本文采用物化視圖的線性代價(jià)模型。設(shè)與查詢(xún)q相對(duì)應(yīng)的視圖是v，那么q的執(zhí)行代價(jià)與v的元組數(shù)成正比。若物化視圖v，那么v中的元組數(shù)就是q的查詢(xún)代價(jià)；若沒(méi)有物化v，且v的某個(gè)父視圖被物化了，那么父視圖中元組的個(gè)數(shù)便是q的執(zhí)行代價(jià)；但如果v沒(méi)有被物化，并且其父視圖也不在物化視圖集中，那么系統(tǒng)必須將事實(shí)表中的所有元組全部遍歷來(lái)回答q，這種情況下事實(shí)表中所有元組的個(gè)數(shù)將等于q的執(zhí)行代價(jià)。顯然第一種情況下q的執(zhí)行代價(jià)最小，q執(zhí)行代價(jià)最大的是最后一種情況。

設(shè)數(shù)據(jù)倉(cāng)庫(kù)查詢(xún)集為Q，Q={q1，q2，q3，...qn}，對(duì)應(yīng)的視圖集V={V1，V2，V3，...Vm}。Q（S）表示物化視圖的查詢(xún)代價(jià)，U（S）為維護(hù)時(shí)間代價(jià)，g為查詢(xún)q的提交頻率，h為視圖V的更新頻率。

定義1 查詢(xún)總代價(jià)。當(dāng)數(shù)據(jù)倉(cāng)庫(kù)中的物化視圖集為V時(shí)，Q中全部查詢(xún)的總代價(jià)是每個(gè)查詢(xún)代價(jià)和該查詢(xún)提交頻率gi的乘積的總和。即

[Q（S）=i=1mgi*Q（qi，vi）]

定義2 維護(hù)總代價(jià)。當(dāng)更新數(shù)據(jù)源表時(shí)，也要對(duì)應(yīng)地修改物化視圖，以保證數(shù)據(jù)一致性，修改物化視圖的開(kāi)銷(xiāo)稱(chēng)為物化視圖的維護(hù)代價(jià)。當(dāng)數(shù)據(jù)倉(cāng)庫(kù)中的物化視圖集為V時(shí)，視圖集V的維護(hù)代價(jià)是每個(gè)視圖的維護(hù)代價(jià)和更新頻率hi的乘積的總和。即

[U（S）=i=1mhi*U（qi，vi）]

定義3 存儲(chǔ)總代價(jià)，即為每個(gè)視圖存儲(chǔ)代價(jià)的總和，即

[M（S）=i=1mM（vi）]

定義4 查詢(xún)維護(hù)代價(jià)模型。在一定存儲(chǔ)空間rmax約束下，查詢(xún)總代價(jià)和維護(hù)總代價(jià)之和Ttotal（S）為總代價(jià)。即

[Ttotal（S）=Q（S）+U（S）=i=1mgi*Q（qi，vi）+i=1mhi*U（qi，vi）] 式3-1

4 算法優(yōu)化

4.1 初始解構(gòu)造

遺傳算法中，初始解非常重要，它決定著最優(yōu)解的質(zhì)量。可是初始種群隨機(jī)產(chǎn)生是大多數(shù)的GA研究基礎(chǔ)，隨機(jī)產(chǎn)生需要很長(zhǎng)的搜索時(shí)間，而且發(fā)現(xiàn)最優(yōu)解的可能性還降低了。首先，預(yù)處理算法在物化視圖集總存儲(chǔ)代價(jià)M（S）

Begin

S=[φ]；

While （ M（S）

根據(jù)式3-1，對(duì)于S中的每個(gè)視圖計(jì)算它的查詢(xún)維護(hù)代價(jià)；

設(shè)C表示相對(duì)于S查詢(xún)維護(hù)代價(jià)最小的視圖；

If （M（S）+M（C）

S=S∪C；

End If

End while；

Return S；

End

4.2 編碼

利用遺傳算法尋優(yōu)求解問(wèn)題中，焦點(diǎn)問(wèn)題是編碼，編碼在很大程度上影響著算法的性能，遺傳操作方法和適應(yīng)度函數(shù)的計(jì)算是根據(jù)編碼方式改變的。常見(jiàn)的編碼方式有格雷碼編碼、二進(jìn)制編碼、符號(hào)編碼和十進(jìn)制編碼。目前遺傳算法研究普遍采用二進(jìn)制編碼，所以本文也采用二進(jìn)制編碼。

多維數(shù)據(jù)格模型的格是一種有向無(wú)環(huán)圖，例如在一個(gè)簡(jiǎn)單的借閱主題的數(shù)據(jù)倉(cāng)庫(kù)，該多維數(shù)據(jù)模型包括了3個(gè)維度Time，Book，Person以及一個(gè)Borrow Information事實(shí)表。那么OLAP 查詢(xún)可能是關(guān)于時(shí)間與借閱者分組的借閱信息查詢(xún)，也可能是按照借閱者分組與圖書(shū)分組的借閱信息查詢(xún)。3個(gè)維度有8種組合方式，記T，B，P代表3個(gè)維度，沒(méi)有在分組條件中的記為All。視圖間的依賴(lài)關(guān)系如圖2所示，沿箭頭方向可達(dá)的兩個(gè)視圖之間都存在依賴(lài)關(guān)系。

利用廣度優(yōu)先遍歷將多維數(shù)據(jù)格中的節(jié)點(diǎn)進(jìn)行遍歷排序，圖2節(jié)點(diǎn)遍歷后的順序是：（ALL，ALL，ALL），（T，ALL，ALL），（ALL，B，ALL），（ALL，ALL，P），（T，B，ALL）， （T，ALL，P），（ALL，B，P），（T，B，P）。

采用二進(jìn)制編碼，每一個(gè)節(jié)點(diǎn)只有兩種狀態(tài)，“1”表示對(duì)應(yīng)的節(jié)點(diǎn)需要物化；“0”表示對(duì)應(yīng)節(jié)點(diǎn)不物化。若節(jié)點(diǎn)對(duì)應(yīng)的編碼是00010001，那么第一個(gè)節(jié)點(diǎn)（ALL，ALL，ALL）對(duì)應(yīng)二進(jìn)制編碼為0，代表對(duì)應(yīng)的視圖不需要物化，而第四個(gè)節(jié)點(diǎn)（ALL，ALL，P）對(duì)應(yīng)的二進(jìn)制編碼為1，表示對(duì)應(yīng)的視圖應(yīng)該被物化，其余節(jié)點(diǎn)依次類(lèi)推。

4.3 適應(yīng)度函數(shù)

在遺傳算法演化過(guò)程中外部信息基本不被納入考慮因素，僅考慮適應(yīng)度函數(shù)（fitness function），搜索最優(yōu)解是根據(jù)種群中每個(gè)個(gè)體的適應(yīng)度值來(lái)進(jìn)行的。個(gè)體在當(dāng)前環(huán)境下的生存能力也是由個(gè)體的適應(yīng)值決定。因此選取合適的適應(yīng)度函數(shù)非常重要，好的適應(yīng)度函數(shù)使遺傳算法的收斂速度加快，進(jìn)而找到最優(yōu)解。概而論之，適應(yīng)度函數(shù)是根據(jù)目標(biāo)函數(shù)變換而來(lái)的。

物化視圖選擇問(wèn)題可以描述為：在存儲(chǔ)空間限制條件的情況下，尋找一個(gè)視圖集V，使得"查詢(xún)維護(hù)代價(jià)和最小"。所以算法的目標(biāo)函數(shù)可以取這個(gè)代價(jià)和。很多研究把查詢(xún)代價(jià)最小作為算法的目標(biāo)函數(shù)，我們同時(shí)考慮了物化視圖集的查詢(xún)代價(jià)和維護(hù)代價(jià)，取目標(biāo)函數(shù)為

[Ttotal（S）=Q（S）+U（S）=i=1mgi*Q（qi，vi）+i=1mhi*U（qi，vi）]

由于遺傳算法的適應(yīng)度函數(shù)通常設(shè)計(jì)成最大化，而視圖選擇的目標(biāo)是查詢(xún)代價(jià)和維護(hù)代價(jià)和最小，目標(biāo)函數(shù)是最小問(wèn)題。遺傳算法要求，在優(yōu)化過(guò)程中目標(biāo)函數(shù)的變化方向應(yīng)該和群體演化過(guò)程中適應(yīng)度函數(shù)變化方向一致。因此考慮對(duì)目標(biāo)函數(shù)作如下轉(zhuǎn)換。

4.4 選擇算子

選擇是在計(jì)算比較群體中個(gè)體的適應(yīng)度的基礎(chǔ)上，選擇適應(yīng)度高的的個(gè)體，并淘汰適應(yīng)度低的個(gè)體，然后把優(yōu)化的個(gè)體直接遺傳到下一代或者通過(guò)配對(duì)交叉產(chǎn)生新的個(gè)體再遺傳到下一代。選擇算子嚴(yán)格單調(diào)減少群體多樣性，保證了遺傳算法的“優(yōu)勝劣汰，適者生存”的進(jìn)化現(xiàn)象，遺傳算法收斂的速率和效果在很大程度上取決于選擇算子。

選擇應(yīng)該是動(dòng)態(tài)的、全局的和自適應(yīng)的，而不應(yīng)是局限的。這樣才能體現(xiàn)生物遺傳融入環(huán)境因素的特征。提高計(jì)算效率、避免杰出基因缺失和提高全局收斂性是選擇操作的主要目的。父代群體就是子代生存的社會(huì)環(huán)境，每個(gè)子代個(gè)體必然受整個(gè)社會(huì)形態(tài)影響——時(shí)代的影響，社會(huì)環(huán)境往往在個(gè)體生存過(guò)程中起著更為深刻廣泛的作用。子代隸屬于社會(huì)，而不僅屬于父代。

基于上述思想，本文中采用一種混合策略的選擇算子。首先，將最高適應(yīng)度個(gè)體直接不作改變遺傳到下一代，這樣在進(jìn)化過(guò)程中可以保證某一代的最優(yōu)解不被交叉和變異操作所破壞，加快遺傳算法的收斂過(guò)程。隨后采取競(jìng)爭(zhēng)法，即隨機(jī)地選擇兩個(gè)個(gè)體，比較其適應(yīng)度值，保留適應(yīng)度值大的；若兩個(gè)個(gè)體的適應(yīng)度值相同，任意保留其中一個(gè)。重復(fù)此過(guò)程，直到配對(duì)庫(kù)達(dá)到存儲(chǔ)空間限制。競(jìng)爭(zhēng)法保證了配對(duì)庫(kù)中的個(gè)體有較好的分散性，同時(shí)又保證了加入配對(duì)庫(kù)中的個(gè)體具有較大的適應(yīng)值。

4.5 交叉算子

交叉是把兩個(gè)父代個(gè)體的部分結(jié)構(gòu)以一定概率Pc替換重組生成新個(gè)體的操作。交叉是遺傳算法中起核心作用的操作，可以組合出新的個(gè)體。交叉是遺傳算法區(qū)別于別的進(jìn)化算法的重要特征。

經(jīng)典遺傳算法運(yùn)用隨機(jī)配對(duì)的方式、固定的交叉概率和傳統(tǒng)的交叉算子進(jìn)行配對(duì)，導(dǎo)致優(yōu)秀基因有可能在遺傳算法前期得不到保留，也會(huì)使遺傳算法的收斂速度變慢；在演化后期，根據(jù)優(yōu)勝劣汰原理，只保留了少量的優(yōu)良的個(gè)體，這些個(gè)體往往具有相同或高度類(lèi)似基因，近親繁殖是無(wú)效的交叉操作，很難產(chǎn)生出新的個(gè)體，因此遺傳算法不能跳出局部極值點(diǎn)，會(huì)呈現(xiàn)早熟現(xiàn)象。綜上所述，本文提出改進(jìn)的自適應(yīng)交叉算法，根據(jù)適應(yīng)度集中程度自適應(yīng)調(diào)整種群的交叉概率。

其中，Pc0是初始交叉概率，fmax是個(gè)體適應(yīng)度最大值，favg是個(gè)體適應(yīng)度平均值，fmin是個(gè)體適應(yīng)度最小值，f是兩個(gè)個(gè)體中較大的適應(yīng)度值。

該方法以最大適應(yīng)度f(wàn)max、平均適應(yīng)度f(wàn)avg和做小適應(yīng)度f(wàn)min來(lái)衡量種群適應(yīng)度的集中程度。favg/fmax>[α]且fmin/fmax>[δ]判斷為種群集中。最初種群分散，Pc取初始交叉概率值，不會(huì)破壞種群的優(yōu)良模式。經(jīng)過(guò)多次遺傳操作后，個(gè)體差異減小，滿足條件favg/fmax>[α]，fmin/fmax>[δ]，Pc適當(dāng)增大，可以使算法跳出局部極值。試驗(yàn)表明，改進(jìn)的自適應(yīng)交叉算子比傳統(tǒng)的算法更容易避免局部收斂。

4.6 變異算子

變異模擬自然界生物體的基因突變現(xiàn)象，可以改變?nèi)旧w的物理性狀和結(jié)構(gòu)。變異是一種局部隨機(jī)搜索，能避免由交叉算子和選擇算子引起的某些信息的永久性丟失，變異操作能夠使遺傳算法具有局部的隨機(jī)搜索能力，保證遺傳算法的有效性；變異操作可以保持遺傳算法群體的多樣性，有助于防止早熟收斂。

在遺傳算法中，變異算子將所選個(gè)體某一位或某些位基因座上的基因值按變異概率Pm取反操作。對(duì)應(yīng)當(dāng)前個(gè)體的當(dāng)前位生成一個(gè)偽隨機(jī)數(shù)r，取值范圍為[0，1]，若r小于Pm則將該位取反，否則保持不變。

通常變異概率Pm取值很小，位長(zhǎng)、種群規(guī)模等因素都會(huì)影響Pm取值，一般情況Pm選取0.001～0.1（或取l/L，L是位串長(zhǎng)度）。

4.7 改進(jìn)算法步驟描述

經(jīng)典遺傳算法在編碼方案中沒(méi)有使用約束條件，考慮到數(shù)據(jù)倉(cāng)庫(kù)的存儲(chǔ)空間有限，不能將所有的視圖物化。因此改進(jìn)算法中加入約束條件：有限的存儲(chǔ)空間。算法描述如下。

Step1 按照4.1構(gòu)造初始解；

Step2 計(jì)算最初群體中每個(gè)個(gè)體的適應(yīng)度值；

Step3 確定下一代個(gè)體，具體操作按照4.4中的選擇策略；

Step4 交叉操作，按照4.5中的交叉概率Pc進(jìn)行；

Step5 變異操作，按照4.6中的變異概率Pm進(jìn)行；

Step6 若視圖存儲(chǔ)容量達(dá)到rmax，則執(zhí)行Step7，否則執(zhí)行Step2；

Step7 將種群中最優(yōu)適應(yīng)度值的個(gè)體輸出。

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

為了驗(yàn)證算法效果，我們對(duì)算法進(jìn)行了試驗(yàn)。實(shí)驗(yàn)測(cè)試數(shù)據(jù)是某零售業(yè)銷(xiāo)售記錄組成的數(shù)據(jù)倉(cāng)庫(kù)，含有1個(gè)事實(shí)表和6個(gè)維表，其中共有候選視圖28=256個(gè)，初始交叉概率Pc= 0.65，變異概率Pm= 0.06。我們對(duì)經(jīng)典遺傳算法和改進(jìn)遺傳算法的執(zhí)行時(shí)間進(jìn)行了比較。兩種算法的執(zhí)行結(jié)果如圖3所示。

改進(jìn)算法建立了代價(jià)估算模型，在有限的存儲(chǔ)空間條件下，把物化視圖的維護(hù)開(kāi)銷(xiāo)與查詢(xún)開(kāi)銷(xiāo)的代價(jià)和作為衡量標(biāo)準(zhǔn)，并優(yōu)化了交叉算子，實(shí)驗(yàn)證明該算法是有效可行的，并且執(zhí)行代價(jià)比經(jīng)典GA算法要小。

參考文獻(xiàn)：

[1] Inmon W H. Building the Data Warehouse[M]. America： Wiley， 2005.

[2] Harinarayan V， Rajaraman A， Ullman J. Implementing data cubes efficiently[J]. in the Proceeding of SIGMOD， ACM Press， 1996： 205-216.

[3] Shukla A， Deshpande P M， Naughton J F. Materialized View Selection for Multidimensional Datasets[C]. Proceedings of the 24th VLDB Conference，New York， USA：ACM Press， 1998： 448-459.

[4] Gupta H， Harinarayan V， Rajaraman A. Index Selection for OLAP[C]// Gray A， Larson， Per-Ake. ICDE'97， Proceedings of the 13th International Conference on Data Engineering. Birmingham， UK： IEEE Computer Society Press， 1997： 189-255.

[5] Zhang C， Yang J. Genetic algorithm for materialized view selection in data warehouse environments[C]// Proceedings of the 8th International Conference on Data Warehousing and Knowledge Discovery， Florence： Springer-Verlag， 1999： 116-125.

[6] Homg J T， Chang Y J， Liu B J， Applying evolution algorithms to materialized vew selection in a data Warehouse[J]. Soft Computing， 2003， 7（23）： 574-581.

[7] Derakhshan R， Dehne F， Korm O， Stantic B. Simulated annealing for materialized view selection in data warehouse environments[M]//Hamza M H. Proc. of the 24th IASTED Intl Conf. on Database and Applications. Innsbruck： IASTED/ACTA Press， 2006： 8-94.

[8] 王宜貴. 數(shù)據(jù)倉(cāng)庫(kù)中查詢(xún)優(yōu)化研究[D]. 南京： 東南大學(xué)， 2006.

[9] 王自強(qiáng)， 孫霞， 張賢德. 數(shù)據(jù)倉(cāng)庫(kù)中用于視圖選擇的增強(qiáng)遺傳算法[J]. 小型微型計(jì)算機(jī)系統(tǒng)， 2007， 28（2）： 367-371.

[10] 趙秀麗，數(shù)據(jù)倉(cāng)庫(kù)中物化視圖選擇問(wèn)題的研究[D].天津：河北工業(yè)大學(xué)，2007.

[11] 龔安， 竇萬(wàn)蕊， 王彥. 基于蟻群-遺傳算法的物化視圖選取策略[J]. 微計(jì)算機(jī)應(yīng)用， 2010， 31（1）： 16-20.

[12] 徐海濤， 鄭寧. 數(shù)據(jù)倉(cāng)庫(kù)中物化視圖選擇的一種混合算法[J]. 計(jì)算機(jī)工程與設(shè)計(jì)， 2005， 26（10）： 2752-2755.

[13] 玄光男， 程潤(rùn)偉. 遺傳算法與工程設(shè)計(jì)[M]. 汪定偉，譯.北京： 科學(xué)出版社， 2000， 1.