張 舉，耿海軍

(1.山西大學(xué) 軟件學(xué)院,太原 030006；2.網(wǎng)絡(luò)與交換技術(shù)國家重點實驗室,北京 100876)

0 引言

隨著數(shù)據(jù)庫技術(shù)的發(fā)展和完善，學(xué)校和企事業(yè)單位內(nèi)部積累了大量并且復(fù)雜的數(shù)據(jù)，但是，如何有效地利用如此海量的數(shù)據(jù)成為目前研究的重點和難點.傳統(tǒng)的數(shù)據(jù)庫系統(tǒng)在面對這樣龐大且復(fù)雜的數(shù)據(jù)時，在增刪改等基本處理操作上必然會耗費(fèi)大量的時間成本，將導(dǎo)致不能有效地利用和處理到大量數(shù)據(jù).因而，在用戶需求上傳統(tǒng)的數(shù)據(jù)庫系統(tǒng)的局限性日益明顯，數(shù)據(jù)的處理方式及聯(lián)機(jī)事務(wù)處理系統(tǒng)OLTP愈發(fā)滿足不了人們對數(shù)據(jù)庫系統(tǒng)的需求.越來越多的企業(yè)發(fā)現(xiàn)了數(shù)據(jù)庫系統(tǒng)潛在的問題，并且希望能夠?qū)τ脩籼峤坏臄?shù)據(jù)進(jìn)行多角度、多維度地展示和分析，從而對用戶的需求有更深入地了解，盡量讓自己的產(chǎn)品滿足用戶的需求，因此，如何從傳統(tǒng)數(shù)據(jù)庫中海量并且復(fù)雜的數(shù)據(jù)中獲取對決策支持有用且重要的信息，已經(jīng)成為現(xiàn)在數(shù)據(jù)庫系統(tǒng)研究的重點和關(guān)鍵，在深入研究了上述問題以后，數(shù)據(jù)倉庫[1]的概念被提出來了.

如今，世界上一些有名企業(yè)已經(jīng)設(shè)計出了自己的數(shù)據(jù)倉庫系統(tǒng).例如，IBM的數(shù)據(jù)倉庫產(chǎn)品DB2 UDB，Informix提出的IDS動態(tài)服務(wù)器，微軟的OLAP服務(wù)器，Sybase的數(shù)據(jù)倉庫平臺Sybase IQ.相繼推動了數(shù)據(jù)倉庫系統(tǒng)的廣泛發(fā)展.

隨著數(shù)據(jù)庫系統(tǒng)發(fā)展的日益加快和在各個領(lǐng)域的應(yīng)用日益廣泛，在數(shù)據(jù)庫系統(tǒng)中存放大量的信息也是不可避免的，但其中的部分信息已經(jīng)過，甚至有些數(shù)據(jù)已經(jīng)沒有價值，因此如何從大量并且復(fù)雜的數(shù)據(jù)庫系統(tǒng)中尋找對用戶有用的信息成為了數(shù)據(jù)庫系統(tǒng)設(shè)計的關(guān)鍵.隨著對該技術(shù)的深入研究，聯(lián)機(jī)分析處理(OLAP)被提出來，并且OLAP的發(fā)展和數(shù)據(jù)倉庫的發(fā)展互為動力，二者相互影響，相互促進(jìn)，經(jīng)過了數(shù)十年的發(fā)展，二者的基本模型和基本技術(shù)已經(jīng)趨于成熟.

數(shù)據(jù)倉庫中的一個重要問題是如何選擇實視圖.查詢結(jié)果存儲在數(shù)據(jù)倉庫的實視圖中，有效提高了查詢響應(yīng)速度.實枧圖技術(shù)已在數(shù)據(jù)倉庫、完整性約束、查詢優(yōu)化、決策支持等方面得到廣泛的應(yīng)用.實視圖技術(shù)加快了OLAP查詢響應(yīng)速度，但是同時也帶來了一定問題，一方面實視圖在存儲上需要占用一定空間[2]，另一方面當(dāng)基表發(fā)生改變時，對應(yīng)的實視圖也要發(fā)生改變.可以將部分視圖作為候選，并將其實體化，這樣，查詢的動作就是如何選擇這些實視圖.

但是，一方面在數(shù)據(jù)倉庫中有海量的視圖，想要存儲所有的視圖所要花費(fèi)的空間代價是不可想象的；另一方面當(dāng)基本的事實表需要更新時，實視圖也需要更新，視圖的維護(hù)代價顯然會有所增加，因此在實際應(yīng)用中想要實體化所有的視圖近乎是不可能的.由此可見實視圖選擇問題不能無限制的選擇跟新，需要在一定條件的限制下，實體化一組視圖，從而提高查詢性能[3].

1 實視圖的選擇的代價模型和問題描述

1.1 實視圖的選擇的代價模型

作為優(yōu)化數(shù)據(jù)庫查詢方向的關(guān)鍵點，實視圖的選擇代價模型和問題描述尤為重要，因此，數(shù)據(jù)庫性能很大程度上受對于已選視圖以何種方式實現(xiàn)物化的影響.雖然對此有著各異的嘗試，但時至今日，仍未找到一種最優(yōu)解，物化視圖選擇問題現(xiàn)已被證明列為：NP-Hard問題.

查詢代價，維護(hù)代價，空間代價[4]，這是物化視圖要考慮的三個方面.

其一，物化視圖技術(shù)是一種以空間換時間的技術(shù)，必須占據(jù)存儲空間.過多的視圖物化必定占據(jù)過多的存儲空間，這一不可避免的矛盾決定了物化視圖在數(shù)量上的有限性.

其二，對于物化視圖原數(shù)據(jù)的變化，為保持一致，以其為基礎(chǔ)的物化視圖必須保持同步的更新，但是如果面對大數(shù)據(jù)量的復(fù)雜情況，在同步更新上的代價是不可想象的.

所以考慮到空間和維護(hù)代價等多方面因素，如何對視圖進(jìn)行最優(yōu)物化的重要性不言而喻，其中的關(guān)鍵則是如何維護(hù)響應(yīng)性能上的最優(yōu)和最小開銷之間的平衡.

圖1顯示了視圖數(shù)量，磁盤使用空間，維護(hù)成本及維護(hù)時間的約束四者之間的關(guān)系.從圖1可以看出隨著實視圖數(shù)量的增加，查詢時間逐漸縮短，但是對使視圖的維護(hù)代價和實視圖占用的存儲空間逐漸增加.但是科學(xué)技術(shù)在不斷的革新和進(jìn)步，磁盤的費(fèi)用也在大幅下降，存儲大量的數(shù)據(jù)成為可行條件，在存儲空間上的限制不再是考慮的主要約束條件.因此，本文討論的主要問題是，基于一定的維護(hù)成本，選擇一組視圖進(jìn)行實現(xiàn)，并最小化視圖的查詢成本.Gupta and Mumick[5]首次提出了維護(hù)代價限制條件下的實視圖選擇，這個問題解決起來比起空間代價限制更加困難，因為隨著選擇的實視圖數(shù)目的增加，維護(hù)代價可能會減少，而不是單調(diào)增加.

圖1 物化視圖數(shù)目與磁盤空間，視圖維護(hù)，查詢響應(yīng)時間的關(guān)系圖

“數(shù)據(jù)主要通過星形模型和雪花模型存儲在數(shù)據(jù)倉庫中. 其中，中心表和輔助表是星形模型中的主要構(gòu)成”[6].前者數(shù)據(jù)量較大，但沒有冗余；而后者則比較小.下面將以農(nóng)產(chǎn)品數(shù)量安全智能分析與預(yù)警關(guān)鍵技術(shù)支撐系統(tǒng)及示范系統(tǒng)為例說明星型模型的存儲，該系統(tǒng)的主題主要包括生產(chǎn)，價格，銷售.我們以生產(chǎn)主題為例說明數(shù)據(jù)的存儲.生產(chǎn)主題事實表主要是生產(chǎn)表p，表中主要內(nèi)容為生產(chǎn)的數(shù)量，維表主要包括時間維度t,地點維度l,產(chǎn)品維度i,如果不考慮每個維度上的層次，在上面的多維數(shù)據(jù)集中用戶可能有23種查詢，每種查詢都是針對事實表，只是group by語句不同，并且每種查詢都是針對事實表進(jìn)行的.假設(shè)我們要查詢玉米在各個地區(qū)的產(chǎn)量.我們定義的SQL語句為：

Select sum(產(chǎn)量) from p,i where 農(nóng)產(chǎn)品名稱=”玉米” group by l ;

由上面的多維數(shù)據(jù)集構(gòu)成的立方體的格如圖2所示.

其中視圖tli代表基表稱為基本方體，任何視圖都可以由它得到，all為頂點方體，表示三個維的匯總.

下面為實視圖選擇代價模型的一些定義：

定義1每個節(jié)點對應(yīng)三個權(quán)值查詢頻率fv，更新頻率uv，讀取代價rv.每條邊對應(yīng)兩個權(quán)值quv ,muv.其中，muv代表在視圖v中對視圖u的更新成本，而quv代表在視圖v中查詢視圖u的成本.

圖2 數(shù)據(jù)立方體格圖

定義2一個視圖v的查詢成本q(v，M)，等于利用M去查詢視圖v的最小查詢成本，其中，M為數(shù)據(jù)倉庫中的物化視圖集.即：

q(v,M)=min{q(v,vm),vm∈M}.

(1)

定義3當(dāng)視圖集M被物化后，視圖v的查詢頻率為fv，則總查詢代價等于V(G)中每個視圖的查詢代價的加權(quán)和.

(2)

定義4一個視圖v的維護(hù)成本m(v，M) ，等于從物化視圖集M去更新視圖v的最小維護(hù)成本.即：

m(v,M)=min{m(v,vm),vm∈M}.

(3)

定義5當(dāng)視圖集M被物化后，視圖v的更新頻率為gv，則總的維護(hù)成本如下：

(4)

以圖2中的數(shù)據(jù)為例說明上述定義:

q(t,M)=100+20=120

q(l,M)=100+25=125

q(all,M)=min(100+10+10,100+25+10)=120

u(tl,M)=100

AssumeQ(tli)=100U(tli)=100

q(tl,tli)=400+100=500

q(t,tli)=min(400+100+20,400+200+80)=520

q(l,tli)=min(400+100+25,400+200+100)=525

q(all,tli)=min(400+100+20+10,400+100+25+10,400+200+100+10,400+200+80+10,400+200+90+15,400+250+50+10,400+250+120+15)=530

1.2 問題描述

本文需要的解決的問題可以描述為：

minQ

s.t.

U≤Ω，其中Ω為維護(hù)代價約束.

即總維護(hù)成本在不超出限定的維護(hù)成本的前提下，選擇出一組被實體化的視圖.

2 實視圖選擇

遺傳過程是遺傳算法的核心，它有優(yōu)勝劣汰、交叉遺傳、小概率變異等優(yōu)勢，進(jìn)而可以有效的維護(hù)種群的多樣性、穩(wěn)定性，保證優(yōu)勝劣汰.過程如下：

1)遺傳編碼：在具體算法中，將視圖用0和1編碼表示，其中1代表該視圖已被實體化，而0則相反.這樣，向量(0 1 0 1 0 0 1)就代表第二，第四及第七視圖已被實體化.

2)初始種群的生成：先后使用深度優(yōu)先和隨機(jī)的方法生成.

3)選擇算子：采用輪盤賭選擇策略.

4)交叉算子：對選擇的種群之間隨機(jī)相互交叉匹配，產(chǎn)生子代種群.

為保護(hù)最優(yōu)解并加快劣質(zhì)解的淘汰速度，本文采用Srinivas提出的自適應(yīng)遺傳算法(AGA)[7]中可根據(jù)適應(yīng)度的變化而變化的交叉概率Pc.

交叉概率Pc的計算公式為：

(5)

其中，k1,k2為常數(shù)且小于1，f代表種群適應(yīng)度，f＇代表兩個中的較大者.

5)變異算子：此處采用Srinivas提出的自適應(yīng)遺傳算法(AGA)[7]中的變異概率Pm.變異概率Pm的計算公式為：

(6)

其中，各符號意義同公式(5).

從已有的關(guān)于遺傳算法的文獻(xiàn)中我們得知，若要保證遺傳算法的性能保持在一個較高的水平，Pc和Pm需要保持在0.5

6)適應(yīng)度函數(shù)：適應(yīng)度函數(shù)主要用于評估個體的優(yōu)越性和劣勢. 其值如果較大則表示個體具有更大的生存機(jī)會，相反則該個體更容易消亡.對于我們的問題，必須考慮查詢收益和維護(hù)代價的限制，但是維護(hù)代價的限制比起空間代價的限制復(fù)雜得多，這是因為當(dāng)一個視圖被實體化后，它的維護(hù)代價不僅取決于它自身而且取決于其他的物化視圖.解決此類復(fù)雜問題的較好方法是在適應(yīng)度函數(shù)中引入懲罰函數(shù)，當(dāng)維護(hù)代價滿足條件時，懲罰函數(shù)不會起任何作用，當(dāng)維護(hù)代價不滿足條件時，懲罰函數(shù)將會降低適應(yīng)度函數(shù)的值.當(dāng)引入懲罰函數(shù)后，維護(hù)代價將不再是限制條件.Lee and Hammer在[8]中提出了維護(hù)代價限制條件下利用靜態(tài)懲罰算子構(gòu)造的懲罰函數(shù)來解決實視圖選擇(我們將其算法簡稱為LEE算法).但是靜態(tài)算子的選擇對結(jié)果的影響比較大，不容易確定.因此我們利用Vassilios Petridis提出的動態(tài)懲罰函數(shù)[9]來解決視圖選擇問題.

p=a(g)*d(s)+b(g).

(7)

(8)

(9)

d(s)=max{U(M)-E,0}.

(10)

其中G為最大遺傳代數(shù)，g為當(dāng)前遺傳代數(shù)，A,B是懲罰因子，并且A,B應(yīng)盡量大，這樣可以很容易區(qū)分出有效解和無效解.因此適應(yīng)度函數(shù)為:

f(x)=Q(φ)-Q(M)+p*v.

(11)

當(dāng)為有效解時v=0，反之v=1.

Improve-GA算法代碼如下：

Begin

隨機(jī)產(chǎn)生初始種群G(0);

t=0;

repeat

用適應(yīng)性函數(shù)評估G(t)中的每個個體;

t=t+1;

while G(t)<=population_size

{

從G(t-1)中選擇兩個個體;

按照交叉概率Pc執(zhí)行雜交(crossover)操作;

按照交叉概率Pm執(zhí)行變異(mutation)操作;

將結(jié)果賦給G(t);

}

until t <=max_gen;

End

雜交操作的代碼如下：

輸入：種群G

Begin

隨機(jī)選擇在種群G中的兩個個體g1(u1,u2,u3,…,un)，g2(v1,v2,v3,…,vn);

根據(jù)上述公式計算Pc；

產(chǎn)生一個范圍在0-1之間的隨機(jī)數(shù)c；

產(chǎn)生一個范圍在0-n之間的隨機(jī)數(shù)number；

If(c

For(int j=number;j<=n;j++)

{

t=g1(xj);

g1(xj)=g2(yj);

g2(yj)=t;

}

g1’=g1;

g2’=g2;

End

變異操作的代碼如下：

輸入：種群G

begin

for every individual in do

for every bit in the individual do

Mutate the bit with the probability pm;

end for

圖3 查詢代價和維護(hù)代價之間的關(guān)系

end for

end

3 實驗研究

本文進(jìn)行了一系列的模擬實驗.實驗環(huán)境用的操作系統(tǒng)為Windows 10，編程語言使用C++，所用的數(shù)據(jù)庫為SQL Server 2017.

對維護(hù)成本為0.5 Umin- Umin的條件下(Umin為當(dāng)所有視圖都被實體化后的最小維護(hù)成本)，對LEE和Improve-GA兩種算法的查詢成本進(jìn)行了對比，如圖3所示.從圖中可以看出，當(dāng)維護(hù)成本較小時，LEE和Improve-GA在性能上差距很小，但是隨著維護(hù)成本的增加，Improve-GA表現(xiàn)出了更好的性能.

實視圖選擇算法會隨著節(jié)點數(shù)目的增加其性能會大大降低，因此我們比較了當(dāng)節(jié)點數(shù)目增加時Improve-GA算法和LEE算法對應(yīng)的性能.

當(dāng)限定維護(hù)代價為0.7Umin時，查詢代價隨節(jié)點數(shù)目變化的關(guān)系如圖4所示.從圖4可以看出，當(dāng)節(jié)點數(shù)目在4-16變化時，隨著結(jié)點數(shù)目的增加Improve-GA的查詢代價較小.

圖4 查詢代價與視圖節(jié)點數(shù)目圖5 執(zhí)行時間與視圖節(jié)點數(shù)目

當(dāng)限定維護(hù)代價為Umin時，查詢代價隨節(jié)點數(shù)目變化的關(guān)系如圖5所示.從圖5可知，查詢代價的執(zhí)行時間基本曾線性變化，Improve-GA算法的執(zhí)行時間較短.由圖4和圖5可以得出結(jié)論如下：隨著節(jié)點數(shù)目的增加LEE算法的性能越來越差，而Improve-GA算法性能比較優(yōu)越，從而說明Improve-GA算法的使用范圍更廣.

4 結(jié)語

選擇視圖實體化算法是數(shù)據(jù)倉庫中的研究熱點之一.在這個過程中，有些算法側(cè)重于對視圖存儲空間影響的研究，但隨著存儲技術(shù)及相關(guān)硬件產(chǎn)品成本的降低，這一影響因素的重要性已經(jīng)下降了.因此，本文提出以成本一定為前提，選擇一組使查詢成本最小的視圖實體化.通過實驗比較了Improve-GA算法和LEE算法，從而證明了算法的可行性和有效性.