ѧ
JOURNAL OF SOFTWARE
1999ꡡ1011ڡVol.10No.111999



ﻯͼ׶ģʽ
  ⡡
ժҪһֻڲˮߴʽĶﻯͼ(materialized views)ַ,Ƚɸѡ,ù,ﻯͼз,ʹÿһеͼ֮ûǶ׶ϵ.ÿһеͼûźƻƵˮģʽд,ԴﵽԶﻯͼʵֵĿ.
ؼʡﻯͼ,,ˮ,ݲֿ,ֲʽݿ.
ͼšTP311
A Three-stage Model of Incremental Maintenance of Multi-materialized Views
WANG Teng-jiao1 WANG Hai-yang2 HONG Xiao-guang2 DONG Ji-run2
1 (Department of Computer Science and Technology Beijing University Beijing 100871)
2(Department of Computer Science Shandong University Ji'nan 250100)
Abstract A new method is presented in this paper, which is about incremental maintenance of multi-materialized views based on parallel pipeline process. In this process, the authors classify all the materialized views first by using choosing methods, then by classified topological sorting, so that no nested definitions of relations exist among these views. Finally, in order to maintain the incremental multi-materialized views, they process in parallel all the views by utilizing pipeline model of semaphore process mechanism.
Key wordsMaterialized views, topological sorting, pipeline, data warehouse, distributed database.
ֲʽݿݲֿеﻯͼǽԻݿĳβѯͼش洢ڱعվ,ԺйصĲѯʱ,Բطʻݿﻯͼֱӵõ.Ŀǰ,ⷽо1,2Ҫڵﻯͼ,ӦдﻯͼҪǼԴ,ǵﻯͼ֮ϵʱ,ԵøΪҪ.ʴ,һµĶﻯͼ׶ģʽ.
1 ﻯͼ
,ף2еĸﻯͼַ.R1,R2,...,RnݿеĹϵ;Cﻯͼѡ-ͶӰ-(SPJ);INS(Ru,T)ʾԪ鼯T뵽ϵRu;DEL(Ru,Cd)ʾϵRuCdԪɾ;AͼVеԼ;A+ʾAΨһȷԼ;(Cd)Cdʹõı;(C)Cʹõı.
1(Z-ͼ:Vz). VzͼV±任õV:ͼV׷ԼZ=((Cd)Ȧ(C))-A+,Ӧ,ÿԪtV׷ӣZͬızk,1kܣZV.zkZ-.
2(ϵRiZ-ͶӰ:). CͼV,ϵRiZ-ͶӰ:Rzi=Gi(Vz),Gi=Z=((Cd)Ȧ(C)A+)ɦ(Ri),1in.
3(ͶӰ-ӳ(PJM)). Z-ͼVzͶӰ-ӳ䶨ΪPJMVz=Rz1Rz2...Rzm.ÿһԪ̡PJMVz,һеһ,C̣ʹæ̼ͼ.
ԦZ-ĳʵ,C̣ǿ,
1 ͶӰͬϵõԪﻯͼV;,
2 ͶӰͬϵõԪ鲻ﻯͼV.
ԦZ-۽кʵ,C̣.Ħ̿PJMɾ.
(1)͵Ԫpos(V),ȷϢ;(2)͵Ԫneg(V),Ϣ,ni.
4Ϣ:L(V)). L(V)Z-ͼVzԪõȷϢneg(V)еԪõķϢĽ.ɶCͼVõϢĻ.
1. ǿͼV,Z-VzPJM(Vz),R1ӦɾCD,ԪtzVzͼеҽL(V)H:R1(R1(tz)...Rn(Rn(tz))C(tz)CD(R1(tz)),HΪԪtzгֵZ-,R1ָͼеĳϵ.
2. ǿͼV,Z-VzPJM(Vz),R1ӦɾCD,ԪtzVzӦͼɾȥҽL(V)H:R1(R1(tz)...Rn(Rn(tz))C(tz)CD(R1(tz)),HΪԪtzгֵZ-,R1ָͼеĳϵ.
1. οɼıҪ,һɾοɼģ2,ÿһԪtVһ12е.
ɾ˼·ͬ,ҪǻݿûбﻯͼеԪ.
2 ﻯͼе׶ģʽ
׶ģʽɸѡͲˮߴ.бֵͼʱ˵1ᵽĴ,ˮģʽL(V)ŻƽŻ.豾عվﻯͼM,V1,V2,...,VM.ݿ޸U1,2,...,n.
2.1 ɸѡСӼ
ɸѡСӼ,V1,V2,...,VMɾ޸UԲӰ쵽ͼ.
min-subset={V1,V2,...,VM}
unchange=
updated=(1)Ȧ(2)...Ȧ(n)/*(i)ʾn޸ĵĹϵ*/
for i=1 to M loop
if (C(Vi))updated then/*(C(Vi))ʾͼViʹõĹϵ*/
unchange=unchange{Vi}
end if
end loop
min-subset=min-subset-unchange
2.2 
2.1ڵõСӼеﻯͼmmM,½ΪV1,V2,...,Vm.mﻯͼпܻڶǶ׹ϵ,бҪСӼеͼз,Ҫ㷨.
: ͼG=V,E.
: ༯class.
top:=null;
for i=1 to n do/*һ㣨ڴΪ0ջ.*/
if i.count=0 then stack:=top; top:=i;
endfor
j:=1;
do while topnull /*ջڵĶΪһ,ٽµջ,ֱջΪ*/
classj:=;
do while topnull
del-point:=top; top.count:=*; top:=top.stack;
classj:=classjݡ{del-point};
ptr:=del-point.link;
do while ptrnull
K:=ptr.vertex; K.count:=K.count-1; ptr:=ptr.link;
enddo
j=j+1;
enddo
top:=null;
for i=1 to n do
if i.count=0 then i.stack:=top; top:=i;
endfor
enddo
neߵͼ,Ϊ0ʱΪO(n),ͼ޻,ȼ1Ĳdo while topnullйִe,ܵʱ临ӶΪO(n*e).
2.3 ˮߴģʽ
Ĵ,ĳclassiеĶ㼯ͼ,֮ûǶ׶ϵ,,һˮߴģʽбĳclassеͼ.
ĳclassiеĶ㣨ﻯͼm.U={1,2,...,n}Ƕݿ޸.ǰѸݦiVjĹ̶ΪUPDATE(i,Vj),ģʽ,ÿUPDATE̴ʱ䲢ͬ.һֻڲ㷨źƻ֤ȷ.
V1㷨.
ʼ: for each iU do
commit UPDATE(i,V1);
send DONE(i,V1) message to V2;
end for;
send FINISH message to V2;
para begin
receiving ACK message from V2 do:
stop itself algorithmic execution;
para end.
һͼVu(1um)㷨.
ʼ: committed:=0;
para begin
receiving DONE(i,Vu-1) message from Vu-1 do:
L1: if committedi-1 then goto L1;
commit UPDATE(i,Vu);
committed:=committed+1;
if VuVm then send DONE(i,Vu) message to Vu+1;
para end;
para begin
receiving FINISH message from Vu-1 do:
L2: if committedn then goto L2;
if VuVm then send FINISH message to Vu+1;
else send ACK message to Vm-1;
para end;
para begin
receiving ACK message from Vu+1 do:
send ACK message to Vu-1;
stop itself algorithmic execution;
para end.
и㷨ʱ,ÿUPDATE̴ʱͬ,Ϊt0,ˮnʱΪT=nt0+(m-1)t0,,Ϊһʱ.
ע⵽L(V)ļ,˵ǰﻯͼV,,UPDATE(i,Vu)ûʹVu仯,ôִUPDATE(i+1,Vu)ʱ,Ͳ¼L(Vu).ǽL(V)ŻʱUPDATE(i,Vu)Ľ,Ӷظ.
3  
һֶﻯͼ׶ģʽ,ģʽܹݶﻯͼ֮ϵзദ,Ч˲Ϣﻯͼķ,˷ֲʽݿ⼰ݲֿеͨŷúά.
ĿоõɽʡȻѧ.
߼飺,1973,ʿ,ҪоΪݿϵͳ.
,1965,,ҪоΪݿ,Ϣϵͳ.
,1964,,ҪоΪ/ֲʽݿ.
,1935,,ҪоΪݿ,Ϣϵͳ.
ߵλԡѧѧϵ  100871
󡡺⡡ɽѧѧϵ ϡ250100
ͨѶϵ:ԣ 100871,ѧ27¥326
ο
1 Ashish Gupta, Blakley J A. Using partial information to update materialized view. Information Systems, 1995,20(8):641662
2 Tompa F W, Blackley J A. Maintaining materialized view without accessing base data. Information Systems, 1988,13(4):393406
1998-10-06յԭ,1998-12-21յ޸ĸ
