一種基于中間結(jié)果集的有效視圖維護(hù)算法

收稿日期：2007-11-07；修回日期：2008-01-04

基金項(xiàng)目：國(guó)家教育部科學(xué)技術(shù)研究重點(diǎn)項(xiàng)目(205014)；河北省教育廳科研計(jì)劃項(xiàng)目(2006143)

作者簡(jiǎn)介：張忠平(1972-)，男，CCF會(huì)員，副教授，碩導(dǎo)，博士后，主要研究方向?yàn)閿?shù)據(jù)倉(cāng)庫(kù)、網(wǎng)格技術(shù)、XML數(shù)據(jù)庫(kù)；張艷(1984-)，女，碩士研究生，主要研究方向?yàn)閿?shù)據(jù)倉(cāng)庫(kù)（fanxing6662000@163.com）；金曉丹(1983-)，女，碩士研究生，主要研究方向?yàn)閿?shù)據(jù)庫(kù)；何麗榮(1984-)，女，碩士研究生，主要研究方向?yàn)閿?shù)據(jù)庫(kù).*

(燕山大學(xué) 信息科學(xué)與工程學(xué)院 計(jì)算機(jī)軟件與理論系，河北 秦皇島 066004)

摘 要：物化視圖的引入大大提高了決策支持和查詢的響應(yīng)效率，如何進(jìn)行有效的視圖維護(hù)成為研究的重點(diǎn)。對(duì)現(xiàn)有物化視圖維護(hù)方法進(jìn)行了分析，提出了利用多個(gè)物化視圖的中間結(jié)果進(jìn)行視圖維護(hù)的思想。首先，結(jié)合單位空間增益、空間限制等因素，選擇多個(gè)物化視圖的公共表達(dá)式作為中間結(jié)果，并提出了確定中間結(jié)果集的具體算法；其次，利用已計(jì)算出的中間結(jié)果集進(jìn)行多個(gè)視圖的維護(hù)，給出了具體的維護(hù)算法；最后，通過分析和實(shí)驗(yàn)證明了該算法正確且效率有顯著提高。

關(guān)鍵詞：數(shù)據(jù)倉(cāng)庫(kù)；物化視圖；視圖維護(hù)；中間結(jié)果集

中圖分類號(hào)：TP311

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695(2008)10-2998-04

Efficient view maintenance algorithm based on intermediate set

ZHANG Zhong-ping，ZHANG Yan，JIN Xiao-dan，HE Li-rong

(Dept. of Computer Software Theory， College of Information Science Engineering， Yanshan University， Qinhuangdao Hebei 066004， China)

Abstract:Materialized view has remarkably improved the efficiency of decision supporting and OLAP queries in data warehouse environment. How to maintain the views effectively was becoming the emphasis of the research. The existing view maintenance methods were analyzed. The maintenance method of using intermediate set was raised to reduce the computing cost. First， considering the factor of unit gain space and the space limit， the common expressions of multiple views were selected out as the intermediate result， and the algorithm which was used to define the intermediate set was put forward. Then the algorithm of maintaining multiple views with this set was given. At last， the correctness and efficiency were given after the analysis and experiments.

Key words:data warehouse; materialized view; view maintenance; intermediate set

數(shù)據(jù)倉(cāng)庫(kù)是一個(gè)面向主題的、集成的、時(shí)變的、非易失的數(shù)據(jù)集合，支持部門管理的決策過程[1]。它將來(lái)自一個(gè)或多個(gè)分布的、異構(gòu)數(shù)據(jù)源的數(shù)據(jù)集成在一起，用于查詢和分析。物化視圖的引入大大地提高了查詢效率，當(dāng)數(shù)據(jù)源產(chǎn)生更新后，物化視圖也將發(fā)生相應(yīng)的變化。如何快速有效地進(jìn)行視圖維護(hù)已成為目前研究的重點(diǎn)。

文獻(xiàn)[2]中提出了一種有效的視圖維護(hù)算法——BinPartition算法。該算法針對(duì)單個(gè)視圖達(dá)到了最小計(jì)算代價(jià)；但是數(shù)據(jù)倉(cāng)庫(kù)中存有多個(gè)物化視圖，利用該算法不一定能達(dá)到全局最優(yōu)。為此，本文提出利用物化視圖中間結(jié)果集進(jìn)行視圖維護(hù)的思想。結(jié)合增益、空間限制等多方面因素，選出單位空間增益最大的公共子表達(dá)式作為中間結(jié)果，并將這些子表達(dá)式物化，供所有視圖進(jìn)行增量維護(hù)計(jì)算時(shí)共享，并提出確定中間結(jié)果集的算法；接著，根據(jù)已計(jì)算出的中間結(jié)果集對(duì)所有視圖進(jìn)行增量維護(hù)，并提出了新的視圖維護(hù)算法；最后，經(jīng)過深入分析和實(shí)驗(yàn)證明該視圖維護(hù)算法正確且效率有很大提高。

1 相關(guān)工作

關(guān)于視圖增量維護(hù)問題研究[2~10]目前已有不少解決方法，Zhuge等人提出了只針對(duì)單一數(shù)據(jù)源的物化視圖增量維護(hù)算法——ECA (eager compensating algorithm )算法[3]。該算法基于FIFO(first in first out)隊(duì)列模型，采用補(bǔ)償查詢來(lái)解決更新問題。其后，Y.Zhuge打破了單數(shù)據(jù)源的限制，又提出了Strobe算法[4]，但該算法需在數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)源之間來(lái)回地多次傳送查詢結(jié)果。Agrawal等人[5]提出的Sweep算法，它能確保物化視圖與數(shù)據(jù)源在該更新發(fā)生后的狀態(tài)一致，但是對(duì)數(shù)據(jù)源每一次更新引起的維護(hù)都必須等到前一次的更新完成后才能開始，這使得很多數(shù)據(jù)源處于空閑狀態(tài)。Griffin等人[6]提出了一種動(dòng)態(tài)規(guī)劃算法能夠找到最優(yōu)的增量表達(dá)式，但是該表達(dá)式隨著基本表數(shù)目的增加，性能會(huì)變差。Liu Bin等人[10]提出了近鄰分組及條件分組的方法，該方法減少了維護(hù)查詢次數(shù)，但使每個(gè)維護(hù)查詢變得較為復(fù)雜。

2 問題描述

21 視圖定義及其代價(jià)模型

假設(shè)數(shù)據(jù)倉(cāng)庫(kù)由n個(gè)數(shù)據(jù)源S1，…，Sn組成，每個(gè)數(shù)據(jù)源與數(shù)據(jù)倉(cāng)庫(kù)之間的通信是可靠的，且是FIFO，即它們之間的數(shù)據(jù)不會(huì)丟失且按發(fā)送的次序進(jìn)行傳遞。為簡(jiǎn)單起見，設(shè)Si只有單一關(guān)系Ri(1≤i≤n)，各數(shù)據(jù)源都是關(guān)系數(shù)據(jù)模型且相互獨(dú)立、完全自治，各源關(guān)系的更新自動(dòng)執(zhí)行，并將結(jié)果獨(dú)立地傳遞給數(shù)據(jù)倉(cāng)庫(kù)。

在數(shù)據(jù)庫(kù)關(guān)系表上可以定義多種視圖，如選擇—投影—連接(select-project-join，SPJ)視圖、聚集視圖等。本文考慮由SPJ表達(dá)式定義的視圖。由n個(gè)關(guān)系表定義的視圖V的表達(dá)式如下所示：

∏Attrsσcond(R1R2…Rn )

其中：Attrs為投影運(yùn)算的屬性列表；cond為選擇運(yùn)算的條件列表；視圖可被看做是所有定義視圖的數(shù)據(jù)源之間的條件連接，因此，視圖V的表達(dá)式又可以簡(jiǎn)寫為

V =R1R2 …Rn

本文用|Ri|來(lái)表示運(yùn)算的代價(jià)，視圖V的代價(jià)為

cost(V)=c(|R1|+|R2|+…+|Rn|)

其中：c為維護(hù)每條元組的代價(jià)常數(shù)；|Ri|表示關(guān)系Ri的元組數(shù)目。

22 問題描述

文獻(xiàn)[11]中提出一個(gè)增量表達(dá)式：

ΔV=(ΔR1R2…Rn)∪(R′1R2…Rn)∪…∪

(R′1R′2…△Rn)(1)

其中： R′i= Ri ∪ΔRi表示更新后的數(shù)據(jù)源Ri。該表達(dá)式共有n項(xiàng)，大大降低了訪問數(shù)據(jù)源的次數(shù)。

文獻(xiàn)[12]定義了一種delta表達(dá)式，可以使得計(jì)算視圖變化量的代價(jià)降到最低，它將n個(gè)關(guān)系分為k部分{P1，P2，…，Pk}。其中：1≤k≤n，且∪ki=1Pi={R1，R2，…，Rn}，Pi≠(1≤i≤k)，Pi∩Pj =(i≠j)。設(shè)在某個(gè)劃分中Pi包含的關(guān)系為{Rs，Rt，…，Ru}，則定義Pi，P′i分別表示更新前和更新后Pi中所有關(guān)系的自然連接，即

Pi=RsRt…Ru

P′i=Rs′Rt′…R′u

設(shè)delta({R1，R2，…，Rn})為n個(gè)連接表達(dá)式的變化量，即為Δ(R1，R2，…，Rn)，則有如下表達(dá)式：

delta({R1，R2，…，Rn})= (delta(P1)(P2)

…(Pk) )∪((P′1)delta(P2)

…(Pk) )∪…∪( (P′1)(P′2)

…delta (Pk))

特別地，當(dāng)P1={R1}，P2={R2}，…，Pn={Rn}時(shí)，上式與表達(dá)式(1)相同，每個(gè)delta表達(dá)式惟一對(duì)應(yīng)一棵delta傳播樹。設(shè)視圖V=R1 R2 R3，當(dāng)P1={R1}，P2={R2}，P3={R3}時(shí)，其delta表達(dá)式如式(2)所示。

delta({R1，R2，R3})=(delta({R1})R2R3)∪(R1delta

({R2})R3)∪(R′1R′2delta({R3}))(2)

當(dāng)P1={R1R2}，P2={R3}時(shí)，其delta表達(dá)式如式(3)所示。

delta({R1，R2，R3})=(delta({R1，R2})R3)∪

( R′1R′2delta({R3}) )(3)

圖1(a)(b)分別為表達(dá)式（2）（3）所對(duì)應(yīng)的delta傳播樹。其中，節(jié)點(diǎn)的權(quán)值為對(duì)應(yīng)關(guān)系Ri中元組數(shù)目，路徑長(zhǎng)度為各節(jié)點(diǎn)的父節(jié)點(diǎn)的度數(shù)減1。

由上可知，圖1(a)(b)所對(duì)應(yīng)傳播樹的增量計(jì)算代價(jià)分別為

cost (Δ(R1R2R3))=c(2|R′1|+|R2|+|R′2|+2|R3|)≈

c(2|R1|+2|R2|+2|R3|)

cost (Δ(R1R2R3))=c(2|R′1|+|R2|+|R′2|+|R3|) ≈

c(2|R1|+2|R2|+|R3|)

可見，計(jì)算同一個(gè)視圖變化量，可以有多種不同的delta表達(dá)式，對(duì)應(yīng)多棵不同的delta傳播樹，且不同的樹具有不同的維護(hù)代價(jià)。文獻(xiàn)[2]中證明了在所有的delta傳播樹中性能最優(yōu)的為Huffman樹，并給出了具體的BinPartition算法。當(dāng)圖1(b)中的|R1|和|R2|均小于|R3|時(shí)，該Delta傳播樹即為Huffman樹，此時(shí)，維護(hù)該視圖的代價(jià)最小。但是，該算法只是針對(duì)單個(gè)視圖達(dá)到了最小計(jì)算代價(jià)，并不一定使整個(gè)數(shù)據(jù)倉(cāng)庫(kù)視圖維護(hù)的性能達(dá)到最優(yōu)。下面將提出共享中間結(jié)果集的視圖維護(hù)算法，它選擇并物化多個(gè)視圖的公共表達(dá)式，以提高整個(gè)數(shù)據(jù)倉(cāng)庫(kù)視圖維護(hù)的效率。

3 基于中間結(jié)果集的視圖維護(hù)

31 算法描述

在對(duì)數(shù)據(jù)倉(cāng)庫(kù)中的視圖進(jìn)行維護(hù)時(shí)，對(duì)單個(gè)視圖維護(hù)的代價(jià)最小，不一定能達(dá)到全局總代價(jià)最小，BinPartition算法只是對(duì)單個(gè)視圖的維護(hù)達(dá)到了最小計(jì)算代價(jià)，并沒有考慮到全局優(yōu)化問題。

假設(shè)有兩個(gè)視圖V1、V2，其定義如下：

V1=R1R2R3(4)

V2=R2R3R4(5)

用BinPartition算法維護(hù)時(shí)，視圖V1、V2分別能達(dá)到計(jì)算代價(jià)最小，但從整個(gè)視圖維護(hù)的代價(jià)來(lái)看，它們的公共表達(dá)式R2R3被重復(fù)計(jì)算了兩次，這樣造成了總計(jì)算代價(jià)的增加。

若使視圖V1、V2共享該子表達(dá)式，并對(duì)其進(jìn)行物化，這樣在增量維護(hù)時(shí)，只需要計(jì)算一次該表達(dá)式，同時(shí)可以設(shè)

V1=R1(R2R3)

V2=（R2R3）R4

這樣便可以提高整體性能。但是當(dāng)|Δ(R2 R3)|遠(yuǎn)遠(yuǎn)大于|Δ(R1 R2)| 時(shí)，共享該子表達(dá)式也并不是一個(gè)好方法。因此，必須先確定物化哪些中間結(jié)果才能降低視圖的維護(hù)代價(jià)。

311 確定視圖中間結(jié)果集的算法

盡管物化視圖的引入能夠提高查詢性能，但它也帶來(lái)了大量的存儲(chǔ)空間等開銷；因此，應(yīng)當(dāng)結(jié)合多方面因素，考慮選擇物化哪些視圖才能降低維護(hù)代價(jià)。為此，引入以下定義：

定義1 視圖v的增益B(v，M)。是指中間結(jié)果集分別為M與M∪{v}時(shí)的總維護(hù)代價(jià)之差，即

B(v，M)=ni=1cost (Δvi|M)-ni=1cost(Δvi|M∪{v})

定義2 視圖v的大小S(v)是指視圖v及其物化視圖所需的存儲(chǔ)空間[13]。

定義3 視圖v的單位空間增益BS(v，M)是指中間結(jié)果集為M時(shí)，視圖v的增益B(v，M)與其所占存儲(chǔ)空間S(v)的商，即

BS(v，M)=B(v，M)/S(v)

根據(jù)上述定義及輸入視圖集，首先計(jì)算出至少由兩個(gè)視圖表達(dá)式共用的部分表達(dá)式ci組成集合C；然后根據(jù)定義1計(jì)算增益B(ci，M)，并選出該值為正的表達(dá)式ci；接著利用定義3計(jì)算出這些子表達(dá)式的單位空間增益BS(ci，M)，并將ci按照該值降序排列；最后選出滿足空間限制值SpaceLim且單位空間增益值最高的若干個(gè)中間結(jié)果來(lái)物化，形成中間結(jié)果集M。根據(jù)上述思想，可以給出確定視圖中間結(jié)果集DVISA(determine view intermediate set algorithm)算法。具體算法描述如下：

算法1 DVISA(V，SpaceLim)

Input:V={v1，v2，…，vj}，SpaceLim;

Output: 中間結(jié)果集M。

begin

M←;

C←{ci| v1∧…∧vj};

/*計(jì)算兩個(gè)或兩個(gè)以上視圖的公共表達(dá)式 */

對(duì)于ci∈C，計(jì)算B(ci，M);

if B(ci，M)>0 then /*選出增益為正的表達(dá)式*/

BS(ci，M)=B(ci，M)/S(ci);

將ci按BS(ci，M)值的降序排列;

A[j]←ci，0≤j≤i;

/*將選出的表達(dá)式，按增益值降序排列存入數(shù)組A中*/

for all A[j](j初始化為0)

If S(M)＜SpaceLim Then

M←M∪{A[j]}， C← C -{A[j]};

/*滿足空間限制的表達(dá)式作為中間結(jié)果并物化*/

return M.

end

312 基于中間結(jié)果集的視圖維護(hù)算法

使用DVISA算法計(jì)算出中間結(jié)果集M后，下面將利用該集合進(jìn)行多個(gè)視圖的增量維護(hù)。設(shè)視圖集V中的視圖均由關(guān)系{R1，R2，…，Rn}定義，首先根據(jù)各數(shù)據(jù)源的變化量，對(duì)M中的視圖表達(dá)式進(jìn)行增量維護(hù)，其維護(hù)方法使用BinPartition算法；其次，對(duì)視圖集V中每個(gè)視圖vi，檢索中間結(jié)果集M中是否包含有其部分表達(dá)式，若有，則以Δmi及定義視圖的其余數(shù)據(jù)源的變化量ΔRi作為葉子節(jié)點(diǎn)，|mi|和|Ri|作為權(quán)值構(gòu)造Huffman樹；否則，直接使用定義視圖的各數(shù)據(jù)源變化量ΔRi作為葉子節(jié)點(diǎn)，|Ri|作為權(quán)值構(gòu)造Huffman樹。最終得到視圖vi的增量。根據(jù)上述思想，可以給出基于中間結(jié)果集的多視圖維護(hù)算法VMABIS (view maintenance algorithm based on intermediate set)。具體算法描述如下：

算法2 VMABIS (V，M，{ΔR1，ΔR2，…，ΔRn})

Input:V={v1，v2，…，vj}，{ΔR1，ΔR2，…，ΔRn}，M;

Output:根節(jié)點(diǎn)分別為Δv1， Δv2，…，Δvj的j棵Huffman樹。

begin

a)對(duì)于mi∈V，且vi=Rs…Rx…Ry…Ru，

If(mi=Rx…Ry)Then

(a)計(jì)算Δmi;

(b)將ΔRs，…，Δmi，…，ΔRu作為葉子節(jié)點(diǎn)，將|Rs|，…，|Rx…Ry|，…，|Ru|作為權(quán)值;

else

將ΔRs，…，Δ，Rx，…，ΔRy ，…，ΔRu作為葉子節(jié)點(diǎn)，|Rs|，…，|Rx|，…，|Ry|，…，|Ru|作為權(quán)值;

/*檢索M中是否包含vi的部分表達(dá)式*/

b)構(gòu)造二叉樹的森林F={T1，T2，…，Th(huán)}。其中：Ti只有一個(gè)根節(jié)點(diǎn)。

c)do

(a)選取| root(Ti)|和| root(Tj) |最小的Ti和Tj;

(b)T′. LeftChild←Ti;T′.RightChild←Tj;

(c)root(T′) ←Ti和Tj所有關(guān)系的變化量;

| root(T′) | ←| root(Ti) |+| root(Tj) |;

(d)F←F-{Ti，Tj};

(e)F←F∪{T′};

until F中只剩下一棵樹/*構(gòu)造Huffman樹*/

d)return F.

end

算法VMABIS生成j棵以Δvj為根節(jié)點(diǎn)的Huffman樹，它們具有最小計(jì)算費(fèi)用的，且當(dāng)視圖集V的表達(dá)式有較多公共部分時(shí)，其總維護(hù)代價(jià)將大大減小。

32 算法分析

在DVISA算法中，利用B(v，M)來(lái)選擇出能夠降低整個(gè)視圖集維護(hù)代價(jià)的中間結(jié)果。當(dāng)B(v，M)為正時(shí)，表明物化該中間結(jié)果v后，能使整個(gè)視圖集的維護(hù)代價(jià)降低；反之，不能降低維護(hù)代價(jià)。由于數(shù)據(jù)倉(cāng)庫(kù)的空間有限，利用定義3選出單位空間增益最大的視圖，以提高空間的利用率。算法的時(shí)間復(fù)雜度為O(n ln n+n)，且該算法結(jié)構(gòu)簡(jiǎn)單，較易實(shí)現(xiàn)。

在VMABIS算法中，設(shè)視圖集V={v1，v2，…，vj}為待維護(hù)的視圖集合，用cost(Δvi)來(lái)表示它用BinPartition算法維護(hù)的代價(jià)，那么視圖集V在該算法下的維護(hù)代價(jià)為

cost(V)=ji=1cost(Δvi)(6)

定義了中間結(jié)果集M={m1，…，mk}后，單個(gè)視圖vi的代價(jià)為cost (Δvi|M)，表示中間結(jié)果集M被物化后計(jì)算視圖vi增量Δvi的代價(jià)。顯然，cost (Δvi|M)≤cost (Δvi)，特殊的，當(dāng)M=vi時(shí)，cost (Δvi|M)=0。此時(shí)，視圖集V的代價(jià)為

cost(V)=ki=1cost(Δmi)+ji=1cost(Δvi|M)(7)

其中：ki=1cost(Δmi)為維護(hù)中間結(jié)果集的代價(jià)，ji=1cost(Δvi|M)表示中間結(jié)果集M被計(jì)算并物化后，維護(hù)視圖集V的代價(jià)。

由于中間結(jié)果集的元組數(shù)與整個(gè)關(guān)系的元組數(shù)相比很小，它的計(jì)算代價(jià)也非常小，且cost (Δvi|M)≤cost (Δvi)，因此，整個(gè)視圖集的計(jì)算代價(jià)也將減小。如表達(dá)式(4)和(5)中定義的視圖V1，V2，在它們維護(hù)之前，其中間結(jié)果Δ(R2R3)已被計(jì)算并物化，且共享該中間結(jié)果，因此，在整個(gè)維護(hù)過程中，只需要計(jì)算一次，這樣就大大降低了視圖的維護(hù)代價(jià)。

從時(shí)間復(fù)雜性來(lái)看，文獻(xiàn)[12]中提出的基于delta表達(dá)式的動(dòng)態(tài)規(guī)劃算法其時(shí)間復(fù)雜度為

O(ni=1Cin×B(i))≈O(2n×B(n))

其中：n為關(guān)系數(shù)。當(dāng)n較大時(shí)，其開銷很大，而本文提出的VMABIS算法，其時(shí)間復(fù)雜度即為O(n+n log n)，相對(duì)于前者，其時(shí)間復(fù)雜度顯著降低。

4 實(shí)驗(yàn)結(jié)果

針對(duì)本文提出的算法，筆者進(jìn)行了對(duì)比實(shí)驗(yàn)。數(shù)據(jù)倉(cāng)庫(kù)的安裝環(huán)境為Oracle8.1.7數(shù)據(jù)庫(kù)系統(tǒng)、ProLiant DL380G3 /SX2.4 GHz /512 MB。實(shí)驗(yàn)采用專門用于數(shù)據(jù)倉(cāng)庫(kù)性能測(cè)試的TPC-D[14]數(shù)據(jù)庫(kù)作為測(cè)試數(shù)據(jù)集，考慮到系統(tǒng)配置以及對(duì)實(shí)驗(yàn)時(shí)間的控制，本實(shí)驗(yàn)沒有采用TPC-D數(shù)據(jù)庫(kù)建議的1 GB的數(shù)據(jù)量，在測(cè)試中只選取了40％的記錄作為測(cè)試數(shù)據(jù)。根據(jù)它定義的標(biāo)準(zhǔn)關(guān)系模式和數(shù)據(jù)，定義以下四個(gè)視圖：

V1=CUSTOMERORDERSLINEITEMSUPPLIENATIONREGION

V2=PARTSUPPLIERPARTSSUPNATIONREGION

V3=CUSTOMERORDERSLINEITEM

V4=NATIONCUSTOMERORDERSLINEITEM

本文將VMABIS算法的性能與重新計(jì)算、文獻(xiàn)[11]中的算法及文獻(xiàn)[2]中的BinPartition算法進(jìn)行了比較。當(dāng)基本關(guān)系產(chǎn)生2％、6％、10%、14％的變化量時(shí)（相對(duì)于總數(shù)據(jù)量），使用它們進(jìn)行視圖維護(hù)需要的時(shí)間如圖2所示。

由圖2可知，重新計(jì)算所需時(shí)間最長(zhǎng)；文獻(xiàn)[11]中的算法使整個(gè)視圖維護(hù)時(shí)間降低了近一半；BinPartition算法又在它的基礎(chǔ)上降低大約10％；本文提出的VMABIS算法則在BinPartition算法的基礎(chǔ)上平均又降低了約12％，且隨著數(shù)據(jù)源變化量所占比例的增加，該算法的維護(hù)效率更加顯著，因此，本算法更加適用于數(shù)據(jù)源變化量較大的數(shù)據(jù)倉(cāng)庫(kù)。綜上所述，本文提出的視圖維護(hù)算法優(yōu)于文中提及的其他視圖維護(hù)算法。

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

本文提出了選擇并確定物化視圖集中間結(jié)果的算法，以及基于中間結(jié)果集的多視圖維護(hù)算法。前者綜合考慮了物化中間結(jié)果所帶來(lái)的增益以及整個(gè)數(shù)據(jù)倉(cāng)庫(kù)存儲(chǔ)空間限制等因素，合理地選擇出單位空間增益最高的若干個(gè)中間結(jié)果來(lái)物化，形成中間結(jié)果集；后者則是基于已計(jì)算出的中間結(jié)果集，使用VMABIS算法進(jìn)行視圖維護(hù)，通過分析及實(shí)驗(yàn)表明該算法正確，且有效地縮短了計(jì)算多個(gè)視圖增量的時(shí)間，大大提高了整個(gè)數(shù)據(jù)倉(cāng)庫(kù)視圖集的維護(hù)效率。

隨著當(dāng)今信息時(shí)代數(shù)據(jù)量的不斷增大，且Web數(shù)據(jù)庫(kù)以及面向?qū)ο髷?shù)據(jù)庫(kù)技術(shù)的不斷成熟，未來(lái)將對(duì)Web倉(cāng)庫(kù)以及面向?qū)ο髷?shù)據(jù)倉(cāng)庫(kù)中的增量更新問題進(jìn)行研究。

參考文獻(xiàn)：

［1］INMON W H.數(shù)據(jù)倉(cāng)庫(kù)[M]．4版.王志海，譯，北京：機(jī)械工業(yè)出版社，2006:20.

[2]王新軍，洪曉光，王海洋.數(shù)據(jù)倉(cāng)庫(kù)中多數(shù)據(jù)源物化視圖的一種有效更新算法[J].計(jì)算機(jī)研究與發(fā)展， 2004，41(5):874-879.

[3]ZHUGE Y， GARCIA M H， WIENER J，et al.View maintenance in a warehousing environment[M].New York:ACM Press，1995:316-327.

[4]ZHUGE Y，GARCIA M H，WIENER J L.The strobe algorithms for multi-source warehouse consistency[C]//Proc of the 4th International Paralled and Distributed Information Systems. Washington DC: IEEE Computer Society，1996:146-157.

[5]AGRAWAL D， ABBADI A， SINGH A，et al.Efficient view maintenance at data warehouses[M]. New York: ACM Press，1997:417-427.

[6]GRIFFIN T，LIBKIN L.Incremental maintenance of views with duplicates[M]. New York:ACM Press，1995.

[7]PALPANAS T， SIDLE R， COCHRANE R，et al.Incremental maintenance for non-distributive aggregate functions[C]//Proc of the 28th International Conference on Very Large Data Bases.[S.l.]:VLOB Endowment， 2002:802-813.

[8]CHAO Ching-ming.Incremental maintenance of object-oriented data warehouses[J].Information Systems，2004，160(1-4):91-110.

[9]GUPTA H，MUMICK I S.Incremental maintenance of aggregateand outerjoin expressions[J].Information Systems，2006，31(6):435-464.

[10]LIU Bin，RUNDENSTEINER E A，F(xiàn)INKEL D.Maintaining large update batches by restructuring and grouping[J].Information Systems，2007，32(4):621-639.

[11]GUPTA A，MUMICK I S，SUBRAHMANIAN V S.Maintaining views incrementally[M]. Washington DC: ACM Press，1993:157-166.

[12]KI Y L，JIN H S，MYOUNG H K.Efficient incremental view maintenance in data warehouse[M]. GA:ACM Press，2001:349-356.

[13]林小靜，薛永生.數(shù)據(jù)倉(cāng)庫(kù)中物化視圖選擇策略[J].計(jì)算機(jī)工程與設(shè)計(jì)，2007，28(13):3056-305.

[14]RAAB F.TPC benchmarkTM D(decision support)[C]. San Jose: Trans Processing Performance Council，1995.