一種基于中間結果集的有效視圖維護算法

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

基金項目：國家教育部科學技術研究重點項目(205014)；河北省教育廳科研計劃項目(2006143)

作者簡介：張忠平(1972-)，男，CCF會員，副教授，碩導，博士后，主要研究方向為數據倉庫、網格技術、XML數據庫；張艷(1984-)，女，碩士研究生，主要研究方向為數據倉庫（fanxing6662000@163.com）；金曉丹(1983-)，女，碩士研究生，主要研究方向為數據庫；何麗榮(1984-)，女，碩士研究生，主要研究方向為數據庫.*

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

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

關鍵詞：數據倉庫；物化視圖；視圖維護；中間結果集

中圖分類號：TP311

文獻標志碼：A

文章編號：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

數據倉庫是一個面向主題的、集成的、時變的、非易失的數據集合，支持部門管理的決策過程[1]。它將來自一個或多個分布的、異構數據源的數據集成在一起，用于查詢和分析。物化視圖的引入大大地提高了查詢效率，當數據源產生更新后，物化視圖也將發生相應的變化。如何快速有效地進行視圖維護已成為目前研究的重點。

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

1 相關工作

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

2 問題描述

21 視圖定義及其代價模型

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

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

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

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

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

本文用|Ri|來表示運算的代價，視圖V的代價為

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

其中：c為維護每條元組的代價常數；|Ri|表示關系Ri的元組數目。

22 問題描述

文獻[11]中提出一個增量表達式：

Δ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表示更新后的數據源Ri。該表達式共有n項，大大降低了訪問數據源的次數。

文獻[12]定義了一種delta表達式，可以使得計算視圖變化量的代價降到最低，它將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)。設在某個劃分中Pi包含的關系為{Rs，Rt，…，Ru}，則定義Pi，P′i分別表示更新前和更新后Pi中所有關系的自然連接，即

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

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

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

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))

特別地，當P1={R1}，P2={R2}，…，Pn={Rn}時，上式與表達式(1)相同，每個delta表達式惟一對應一棵delta傳播樹。設視圖V=R1 R2 R3，當P1={R1}，P2={R2}，P3={R3}時，其delta表達式如式(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)

當P1={R1R2}，P2={R3}時，其delta表達式如式(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)分別為表達式（2）（3）所對應的delta傳播樹。其中，節點的權值為對應關系Ri中元組數目，路徑長度為各節點的父節點的度數減1。

由上可知，圖1(a)(b)所對應傳播樹的增量計算代價分別為

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|)

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

3 基于中間結果集的視圖維護

31 算法描述

在對數據倉庫中的視圖進行維護時，對單個視圖維護的代價最小，不一定能達到全局總代價最小，BinPartition算法只是對單個視圖的維護達到了最小計算代價，并沒有考慮到全局優化問題。

假設有兩個視圖V1、V2，其定義如下：

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

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

用BinPartition算法維護時，視圖V1、V2分別能達到計算代價最小，但從整個視圖維護的代價來看，它們的公共表達式R2R3被重復計算了兩次，這樣造成了總計算代價的增加。

若使視圖V1、V2共享該子表達式，并對其進行物化，這樣在增量維護時，只需要計算一次該表達式，同時可以設

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

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

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

311 確定視圖中間結果集的算法

盡管物化視圖的引入能夠提高查詢性能，但它也帶來了大量的存儲空間等開銷；因此，應當結合多方面因素，考慮選擇物化哪些視圖才能降低維護代價。為此，引入以下定義：

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

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

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

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

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

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

算法1 DVISA(V，SpaceLim)

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

Output: 中間結果集M。

begin

M←;

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

/*計算兩個或兩個以上視圖的公共表達式 */

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

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

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

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

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

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

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

If S(M)＜SpaceLim Then

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

/*滿足空間限制的表達式作為中間結果并物化*/

return M.

end

312 基于中間結果集的視圖維護算法

使用DVISA算法計算出中間結果集M后，下面將利用該集合進行多個視圖的增量維護。設視圖集V中的視圖均由關系{R1，R2，…，Rn}定義，首先根據各數據源的變化量，對M中的視圖表達式進行增量維護，其維護方法使用BinPartition算法；其次，對視圖集V中每個視圖vi，檢索中間結果集M中是否包含有其部分表達式，若有，則以Δmi及定義視圖的其余數據源的變化量ΔRi作為葉子節點，|mi|和|Ri|作為權值構造Huffman樹；否則，直接使用定義視圖的各數據源變化量ΔRi作為葉子節點，|Ri|作為權值構造Huffman樹。最終得到視圖vi的增量。根據上述思想，可以給出基于中間結果集的多視圖維護算法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:根節點分別為Δv1， Δv2，…，Δvj的j棵Huffman樹。

begin

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

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

(a)計算Δmi;

(b)將ΔRs，…，Δmi，…，ΔRu作為葉子節點，將|Rs|，…，|Rx…Ry|，…，|Ru|作為權值;

else

將ΔRs，…，Δ，Rx，…，ΔRy ，…，ΔRu作為葉子節點，|Rs|，…，|Rx|，…，|Ry|，…，|Ru|作為權值;

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

b)構造二叉樹的森林F={T1，T2，…，Th}。其中：Ti只有一個根節點。

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所有關系的變化量;

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

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

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

until F中只剩下一棵樹/*構造Huffman樹*/

d)return F.

end

算法VMABIS生成j棵以Δvj為根節點的Huffman樹，它們具有最小計算費用的，且當視圖集V的表達式有較多公共部分時，其總維護代價將大大減小。

32 算法分析

在DVISA算法中，利用B(v，M)來選擇出能夠降低整個視圖集維護代價的中間結果。當B(v，M)為正時，表明物化該中間結果v后，能使整個視圖集的維護代價降低；反之，不能降低維護代價。由于數據倉庫的空間有限，利用定義3選出單位空間增益最大的視圖，以提高空間的利用率。算法的時間復雜度為O(n ln n+n)，且該算法結構簡單，較易實現。

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

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

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

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

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

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

從時間復雜性來看，文獻[12]中提出的基于delta表達式的動態規劃算法其時間復雜度為

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

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

4 實驗結果

針對本文提出的算法，筆者進行了對比實驗。數據倉庫的安裝環境為Oracle8.1.7數據庫系統、ProLiant DL380G3 /SX2.4 GHz /512 MB。實驗采用專門用于數據倉庫性能測試的TPC-D[14]數據庫作為測試數據集，考慮到系統配置以及對實驗時間的控制，本實驗沒有采用TPC-D數據庫建議的1 GB的數據量，在測試中只選取了40％的記錄作為測試數據。根據它定義的標準關系模式和數據，定義以下四個視圖：

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算法的性能與重新計算、文獻[11]中的算法及文獻[2]中的BinPartition算法進行了比較。當基本關系產生2％、6％、10%、14％的變化量時（相對于總數據量），使用它們進行視圖維護需要的時間如圖2所示。

由圖2可知，重新計算所需時間最長；文獻[11]中的算法使整個視圖維護時間降低了近一半；BinPartition算法又在它的基礎上降低大約10％；本文提出的VMABIS算法則在BinPartition算法的基礎上平均又降低了約12％，且隨著數據源變化量所占比例的增加，該算法的維護效率更加顯著，因此，本算法更加適用于數據源變化量較大的數據倉庫。綜上所述，本文提出的視圖維護算法優于文中提及的其他視圖維護算法。

5 結束語

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

隨著當今信息時代數據量的不斷增大，且Web數據庫以及面向對象數據庫技術的不斷成熟，未來將對Web倉庫以及面向對象數據倉庫中的增量更新問題進行研究。

參考文獻：

［1］INMON W H.數據倉庫[M]．4版.王志海，譯，北京：機械工業出版社，2006:20.

[2]王新軍，洪曉光，王海洋.數據倉庫中多數據源物化視圖的一種有效更新算法[J].計算機研究與發展， 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，FINKEL 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]林小靜，薛永生.數據倉庫中物化視圖選擇策略[J].計算機工程與設計，2007，28(13):3056-305.

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