ѧ
JOURNAL OF SOFTWARE
1999 10 8 Vol.10 No.8 1999



ݲֿάһо
ľ
ժҪݲֿǴ洢ѯ;߷õļɻϢֿ,ϢԴڲͬصݿϢԴ.ʵ廯ͼݲֿд洢ҪϢʵ,ԭʼݷ仯ʱ,ݲֿеʵ廯ͼҲӦĸά.ݲֿʵ廯ͼά,On-line Analytical Process,OLAPѯĽ,ݲһµ.һMVCAmultiversion compensating algorithm㷨һ.MVCAð汾Ʒ,ò˼ӦЭݿݲֿ֮ĸά,ﵽ֤һµĿ.,ͨһʾ˵˸㷨ʵеľӦ.
ؼʡݲֿ,ʵ廯ͼ,ά,һ,MVCAmultiversion compensating algorithm.
ͼšTP311
Consistency Algorithm for Data Warehouse On-line Maintenance
LI Zi-muSUN Li-minZHOU Xing-ming
(Department of Computer Science Changsha Institute of Technology Changsha 410073)
Abstract A warehouse is a data repository containing integrated information for efficient querying and analysis, which data come from the databases or the other info-sources at different places. Materialized view is the primary information entity stored in the data warehouse. It must be refreshed when the corresponding data changed in the database. Consistency problem will be arisen during materialized views on-line maintenance because of the invention of OLAP query. In this paper, the authors introduce a new algorithm, MVCA (multiversion compensating algorithm), using multiversion and compensating techniques, along with acknowledgement mechanism to synchronize the maintenance process between the database and the data warehouse so as to ensure the data consistency. At the end of the paper, the authors illustrate the application of the algorithm by a typical example.
Key wordsData warehouse, materialized view, on-line maintenance, data consistency, MVCA(multiversion compensating algorithm).
ݲֿΪṩ֧,ԴݿϢԴֻݿ.ڵݿ,еݲֿƷõĶѻάԣϵͳѼ¼,̼ݲֿ,ʹBulk-loadڵˢݲֿ.Bulk-loadϵͳˢڼ,ݲֿⱻֹʹ,,ݲֿƷĹ˾ҹʱݲֿˢά.άʽ3Ҫ.
.Ź˾ҵȫ,ʱԽԽ,רŶϵͳиάġҹʱ䡱ԽԽȷ
.ӦõĲ,ǳʱ,άʽõʱҲԽԽ.Bulk-loadˢϵͳڼ,ݲֿǽֹʹõ,ϵͳάڴ峿ûʼʹݲֿ֮ǰ,,ʱһ濼ǵأ
.Bulk-loadʹϢʱ,һЩʵʱҪȽϸߵĹؼ,ս,ѻάʽǲܹܵ.
,ݲֿάܵԽԽ㷺.
1 Ĳо״
ݲֿά,ʵ廯ͼάһؼ.ָ,ݲֿΪûṩͬʱ,ݿеԭʼݷıʱ,ʵʱؽֱ仯ӳݲֿ,ʹӦʵ廯ͼõʱˢ.
ݲֿд洢ǲԭʼݵĿʵ廯ͼ,ȫûвѯ.ĳЩOLAPѯ硰ꡱ,ݲֿͨݿܸյĲѯ.ʵ廯ͼǽԭʼ֮ϵ,ĸάǻٵԭʼݵĸ.һOLAPѯõʵ廯ͼ,õԭʼ,ԭʼݺʵ廯ͼصģʵ廯ͼõ˸ԭʼݣ,ԭʼѱ޸,ֱ仯δӳӦʵ廯ͼʱ,ѯϵĲһ.
˹̹ѧD.Quassһ2VNL(two-version no-locking)㷨1,ð汾ʵ廯ͼάһ.2VNL㷨õǰ汾ӰӰ汾ֱʵ廯ͼĲѯά,ǰ汾ֻж,,ед͸²ȫӰӰ汾Ͻ.ӰӰ汾ύ,ǰ汾ϳ,ӰӰ汾Ϊǰ汾,ԺάµӰӰ汾Ͻ.2VNL㷨ڽݲֿάһԷĳ,ȴ3Ҫȱ.
.㷨ֻ汾,ڽа汾лʱ,Щѯ񽫲ɱرֹ,Ӷ.رǶOLAPַʱϳĲѯ,ĿԾ͸ˣ
.2VNL㷨ڶԲѯԤ,ֻĳЩԽӰӰ汾.Ԥⲻ׼ȷ걸,߶ĳЩѯ޷Ԥʱ,2VNL㷨޷.Ԥ˹,⽫άĳɱ,⣻
.㷨ֻ汾,ÿһ̶ʱл,άʽ㲻ڡսߡĶʵʱҪϸߵĹؼ.
ġMVCA汾㷨multiversion compensating algorithm,MVCA,ܹ֤ά״̬ûѯһ,ܺõؽЩ.MVCA㷨ΪMVCA-dwMVCA-db,ֱDW˺DBִ.ò˼2ݺӦ,ϿԭʼݵĶ汾,Ա֤ڶݲֿʵ廯ͼάͬʱ,OLAPѯҲܵõһµĽ. 
2 MVCA㷨
2.1 MVCAеϢ
db_upDB˷ݱ仯֪ͨ,3
ins(r,t)ڹϵrвԪt
del(r,t)ӹϵrɾԪt
mod(r,t1,t2)ڹϵrԪt2Ԫt1
dw_mvDWͼά̷Ĳѯ֪ͨ,صĽʵ廯ͼά
dw_olapDW˷ûѯ֪ͨ,صĽֱύOLAPӦã
db_mvDB˷dw_mvѯķؽ
db_olapDB˷dw_olapѯķؽ
dw_ackDW˷άȷ֪ͨ,DBյһϢ,ݿеϰ汾Ԫͱ־λӦ.
2.2 MVCA-dw㷨
MVCA-dw㷨DWͼάִе㷨.ǿECA㷨3ݶmodify֧,ʹʵ廯ͼά걸,ͨMVCA-dbӦƱ֤ûѯһ.㷨.
ʼi0,k0,Collect,UQS,Top
DB˷ϢӦ
db_up(U)
If Uins(r,t) then
ii+1QiV(r,t)QjUQSPjQj(r,t)
dw_mv(Qi)DBˣ
UQSUQSQiPi1TopTopins(r,t)
Else if Udel(r,t) then
ii1QiV(r,t)QjUQSPjQj(r,t)
dw_mv(Qi)DBˣ
UQSUQSQiPi1TopTopdel(r,t)
Else if Umod(r,t1,t2) then
ii1QiV(r,t1)QjUQSPjQj(r,t1)
dw_mv(Qi)DBˣ
Pi1ii1QiV(r,t2)QjUQSPjQj(r,t2)
dw_mv(Qi)DBˣ
Pi1UQSUQSQi1QiTopTopmod(r,t1,t2)
db_mv(Ai)
CollectCollectPiAiUQSUQSQi
If UQS thenMVMVCollect
RepeatSTop,dw_ack(s)DBˣ
Until Topм¼Ĳȫͳȥ}
db_olap(A*)
A*ύOLAPӦ.
ĳһʱDBݸµٶȽϿʱ,DW˷ĲѯҪ,UQSunanswered query setڼ¼ЩδյĲѯ.Collectһʱ,Ϊ˷ֹм״̬Ĳһ,ֻеdw_mvѯյ,DW˵ͼά̲Collectʵ廯ͼ.Vݲֿʵ廯ͼĶ,Vr1r2 ,Vr1,2,3ݣ2,3r2r1Ԫ2,3ʽӦĹϵ.QiDW˷DB˵Ĳѯ,ʽV.MVVӦʵ廯ͼԪļ.Topڼ¼DB˵ݸ²,ЩѾӳʵ廯ͼк,DW˵ͼά̽Top,֪ͨDB˽ɰ汾ݴݿ.
2.3 DB˵ݱʾ
ΪʹݲֿûĲѯõһ½,DB˵ˢʱ뽫ˢǰľֵ,ͬʱֲ谭DBûݿʹ,MVCAö汾ݿеˢݽпƺά.ݿԪÿmodify,Ӧһ°汾Ԫ,ɰ汾Ԫֻ߼ɾ,ֻյDWӦӦ֮ſɽɾ.ݿԪġdelete.ÿԪ麬hptpָ,ֱָɵİ汾ʹ°汾,һ־λflag¾ɰ汾,ܲ.flag4ֵֿܵ.
I insert.ǰԪǸղ,ֻеյDW˷ins(r,t)ʱ,ܽλΪġձ,ὲ.flagΪIԪ鲻ܲμDW˷dw_olapѯ㣨ΪûзӳӦʵ廯ͼУ,ǿԲdw_mvѯݿ.
D delete.ǰԪǸձɾģ߼ɾ,ֻеյDW˷Ӧdel(r,t)ʱ,ſɽԪɾ.flagΪDԪֻܲdw_olapѯ.
M modify.ɵԪ鱻ϴ˱,ǰԪΪɰ汾Cache򻺳.°汾dw_mvݿ,ɰ汾dw_olap.ֻյDW˷Ӧmod(r,t1,t2)ʱ,ſɽӦľɰ汾ɾ.ֻһ汾ʱ,°汾ɰ汾ʱ,flagΪġ.
ģ ձ.ձǵԪԲ.
2.4 MVCA-db㷨
DB,MVCA-db㷨ö汾ʷݽпά,ͨ־λӦȷݵһ².ΪDB˵ݿԶ,DB˲֪ԼЩݲDWʵ廯ͼļ.,ݿÿһ²,DB˶֪ͨݲֿ,ȷǷӰ쵽Ӧʵ廯ͼ.DB˶ݿĸ²3.
ins(r,t)ڹϵrвԪt
del(r,t)ӹϵrɾԪt
mod(r,t1,t2)t2rеԪt1.
Ӧ,DB˷DW˵Ϣǣ
db_upins(r,t)db_updel(r,t)db_upmod(r,t1,t2).
ЩϢǽӦĲ.Ϣ,DB˻ڴյDW˵Ϣ,MVCA-db㷨DW˷صĲͬϢӦĲ.
dw_mv(Qi)
㷨1.
(1) rQirQiʱ漰ĹءRepeat
ϵ,ʹ㷨1rԪ飻 tr,
(2) ʹöԪQi,Aiif t.flag=M then t°汾
(3) db_mv(Ai)DW.else if t.flagD thent
dw_olap(Q*) Until rԪȫɨ裮
(1) rQ* ,ʹ㷨2rԪ飻㷨2
(2) ʹöԪQ*㣻A*Repeat
(3) db_olap(A*)DWˣ tr,
dw_ack(s)if t.flag=ĻD thent
if sins(r,t) then t.flag= /* tflagΪ */else if t.flag=M thent
else if sdel(r,t) then ɾrеԪtɰ汾
else if smod(r,t1,t2) thenUntil rԪȫɨ裮
ɾrеԪt1
if t2.hp=t2.tp= /* ֻʣһ汾Ԫʱ */
then t2.flag=ģ
3 Ӧʾ
ڵ2,ѾMVCA㷨ϸ.ǽͨһʾ˵MVCAʵӦά,롰ꡱѯһ.
DB˵ݿϵr1r2.


ݲֿӦʵ廯ͼĶΪVA,Z(r1r2),VԪ鼯ΪMV1,2,2,2ݣ.ںһʱ,DB˵ݿ3².
del(r1,2,4)
mod(r2,4,5,2,4,7,8)
ins(r2,4,9,6).
ݲֿʵ廯ͼάڼ䣨ΪյDB3²Ϣ֮һOLAPѯQ.
Q select X,Y,Z
fromr2
where Z in
(select Z
fromV)
OLAPѯQֳ˳ִеӲѯQQ*Q䷵صĽΪ .
Q䣺 select ZQ* select X,Y,Z
from Vfromr2
where Z in 
ڲʹMVCA㷨,ִQ,ڴʱݲֿVԪ鼯ΪMV={1,2,2,2ݣ,,Q䷵صĽΪ2ִСꡱѯQ*,ʱDB˵ݿѾ˸²,ԭr2еԪ4,5,2ѾԪ4,7,8,r2вٺZ2Ԫ,Q*ִɺ󷵻صĽΪ.Ǵ,ȷĽӦǣ4,5,2.Ȼ,OLAPѯݵĲһ.DW˵ʵ廯ͼкZ2Ԫ,DB˵ݿȴû֮Ӧԭʼ.ԭ,Qõݲֿδµʵ廯ͼ,Q*ʹݿиº.
,ǽMVCA㷨Ӧõݲֿά,¼ʱ˳˵MVCAֲһ.
DBˣTiΪʱ꣩
T1r1Ԫ2,4ݵflagΪDdb_updel(r1,2,4) 
T2r2Ԫ4,5,2Cache,4,7,8ݴԭ4,5,2ݵλ,ã4,7,8ݵflagΪMdb_upmod(r2,4,5,2,4,7,8)
T3r2в4,9,6,flagΪIdb_upins(r2,4,9,6).
DBݿ֮,r1r2ͳΪʽ 


DWˣ
T4յdb_updel(r1,2,4)dw_mv(Q1), 
Q1V( r1,2,4)A,Z(2,4r2)
P11
UQSQ1
Topdel( r1,2,4)
T5յdb_upmod(r2,4,5,2,4,7,8)dw_mv(Q2),
Q2V( r2,4,5,2)Q1( r2,4,5,2)
A,Z(r14,5,2)A,Z(2,4ݣ4,5,2)
P21
dw_mv(Q3),
Q3V(r2,4,7,8)Q1(r2,4,7,8)
A,Z(r1 4,7,8)A,Z(2,4ݣ4,7,8)
P31
UQSQ1,Q2,Q3
Topdel( r1,2,4),mod(r2,4,5,2,4,7,8)
T6յdb_upins(r2,4,9,6)dw_mv(Q4),
Q4V(r2,4,9,6)Q1(r2,4,9,6)Q2(r2,4,9,6)Q3(r2,4,9,6)
V(r2,4,9,6)Q1(r2,4,9,6)(V(r2,4,9,6)Q1(r2,4,9,6))
(V(r2,4,9,6)Q1(r2,4,9,6))
V(r2,4,9,6)Q1(r2,4,9,6)
A,Z(r14,9,6)A,Z(2,4ݣ4,9,6)
P41
UQS Q1,Q2,Q3,Q4
Topdel(r1,2,4),mod(r2,4,5,2,4,7,8),ins(r2,4,9,6)
T7ûOLAPѯQ,ִQ,MVеõZ2,OLAPDB˷ꡱѯdw_olap(Q*),Q*X,Y,Z(Z=2(r2)).
DBˣ
T8յdw_mv(Q1),ӦMVCA-db㷨,A12,8,2,6ݣdb_mv(A1)
T9յdw_mv(Q2),ӦMVCA-db㷨,A21,2,2,2ݣdb_mv(A2)
T10յdw_mv(Q3),ӦMVCA-db㷨,A31,8,2,8ݣdb_mv(A3)
T11յdw_mv(Q4),ӦMVCA-db㷨,A41,6,2,6ݣdb_mv(A4)
T12յdw_olap(Q*),ӦMVCA-db㷨,A*4,5,2ݣdb_mv(A*).
DWˣ
T13յdb_mv(A1)
Collect2,8,2,6ݣ
UQSQ2,Q3,Q4
T14յdb_mv(A2)
Collect2,8,2,6,1,2,2,2ݣ
UQSQ3,Q4
T15յdb_mv(A3)
Collect2,6,1,2,2,2,1,8ݣ
UQSQ4
T16յdb_mv(A4)
Collect1,2,2,2,1,8,1,6ݣ
UQS
MV1,2,2,2ݣCollect 1,8,1,6ݣʵ廯ͼάɺ
ȷ;
dw_ackdel(r1,2,4);
dw_ackmod(r2,4,5,2,4,7,8);
dw_ackins(r2,4,9,6);
T17յdb_mv(A*)4,5,2ύOLAPӦãOLAPꡱѯȷ.
DBˣ
T18յdw_ackdel(r1,2,4); r1гɾ2,4ݣ
T19յdw_ackmod(r2,4,5,2,4,7,8);r2гɾ4,5,2,
4,7,8ݵflagΪģ
T20յdw_ackins(r2,4,9,6);r2У4,9,6ݵflagΪģ
˿Կ,MVCA㷨֤DW˵ʵ廯ͼõȷάMV1,8,1,6ݣ,ұ֤ڶʵ廯ͼάͬʱ,ûݲֿġꡱѯQҲõһµĽ4,5,2,.
4 
ݿӦõĲչ,ǶݲֿҲվ.ݲֿѻάάһȻĹ,24(Сʱ)7()ĹģʽһݲֿҪչ.MVCA㷨ݲֿάһһ,ݲֿ״̬¹,ȫ㡰ս֧֡ȶʵʱҪȽϸߵĹؼӦ,ΪָԱṩʱġһµսϢ.
ͨѶϵ:ľ,ɳ410073,ɳѧԺѧϵ
߼飺ľ,1971,ʿ,ҪоΪݲֿ,ݿЭͬ,ټ.
,1968,ʿ,ҪоΪֲм,ټ.
,1938,,ʿʦ,йѧԺԺʿ,ҪоΪݿЭͬ,ֲм,ܼϵṹ.
ߵλɳѧԺѧϵɳ410073
E-mail: doctor2@nudt.edu.cn
ο
1Quass C. Materialized views in data warehouses Ph.D. Thesis. Stanford University, 1997
2Srinivasan V. On-line processing in large-scale transaction systems Ph.D. Thesis. University of Wisconsin-Madison, 1992
3Zhu-ge Y. View maintenance in a warehousing environment. In: Proceedings of ACM SIGMOD Conference. URL: http: //www-db.stanford.edu/warehousing/warehouse.html, 1995
1998-05-05յԭ,1998-09-01յ޸ĸ
