о뷢չ
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999 36 8 Vol.36 No.8 1999



ݲֿжͼµά
ժҪݲֿͼάָݲֿеʵ廯ͼʵʱϢԴеݱ仯һ£ͬʱӰǰûݲֿʹ.Ϊ˽ͼͼάѯһ⣬ݲֿϵṹˡ⡱ģͣӦͼά㷨3VPAthree-version painting algorithm.⡱ǿݲֿϵͳԣΪѯṩ˸õ֧.3VPAò˼롢ͬȴƺͰ汾Ʒͨ롰⡱Ͽƣ֤ݲֿжͼ֮һԣһ֤ѯܹõһµĽ.
ؼʡݲֿ⣬ʵ廯ͼάѯһԣ⣬3VPA
ͼšTP311.13
MULTIPLE VIEWS ON-LINE MAINTENANCE IN DATA WAREHOUSE ENVIRONMENT
LI Zi-Mu, MO Qian, XU Ming, and ZHOU Xing-Ming
(National Laboratory of Parallel & Distributed Processing, National University of Defense Technology, Changsha 410073)
AbstractViews on-line maintenance in data warehouse environment means that the refresh-ments of materialized views are synchronized with that of data sources without disturbing user's normal use with data warehouse at the same time. Data warehouse base (DWbase) in data warehouse architecture and 3VPA(three-version painting algorithm) are presented to solve the consistency problem between multiple views on-line maintenance and drill-down query. The introduction of DWbase not only improves the scalability of data warehouse system but also provides better support for drill-down query. The combined control of DWbase and 3VPA, which uses compensating, synchronization, and version control techniques, ensures data consistency of multiple views on-line maintenance and drill-down query.
Key wordsdata warehouse, materialized view, on-line maintenance, drill-down, consistency, DWbase, 3VPA
1
ݲֿҪӦOLAP.ĳЩOLAPӦãѯû֪˺ݣ˽ЩصϸʱʱͨԴݿܸյĲѯ.ʱԴݿеϸѱ޸ģֱ仯δӳݲֿӦʵ廯ͼʱѯõϸݱݲһ.رǵѯõݲֿеĶʵ廯ͼвֻһʵ廯ͼЩ޸ĵԴʱݲһ͸.
23VPA㷨
ݲֿص㣬һָĽ3ݲֿϵṹͼ1ʾ.


ͼ1Ľ3ݲֿϵṹ


ͼ2ݲֿϵṹ
˹̹ѧݲֿϵṹ1ݣͼ2Ĳ֮ͬݲֿ͵ǰݿ֮䣬һΪݲֿ⣨DWbase¼ƻ⣩ݿ.һмϣݲֿ򽻵£뵱ǰݿ򽻵.뵱ǰݿ֮ǵģǰݿֻݿˣDBˣÿα仯֪ͨ⼴ɣ֮κζ.ݲֿ֮˫ģDW˷ݱ仯֪ͨDW˷ͼάѯѯղѯظDW.
2.1еݱʾ
ʵҲһݿ⣬ȫԴڵǰݿ⣬ֻеݡԭʼݵǰ3ԣͼ3ʾ

VNIVNDflagdbt


ͼ3еԪṹ
УVNI(version number of insertion)һԪʱʵ廯ͼFVİ汾ţ
VND(version number of deletion)ɾԪʵ廯ͼFVİ汾ţ
flag־λ־٣
IԪǸղģ
DԪѱ߼ɾ汾лʱŽɾ
dbt(database tuple)ԴݿԭʼԪ飻
ð汾źͱ־λķʷݣǽпά.
2.23VPA㷨
3ϵṹ3VPA㷨ܹ֤DWжͼ֮һԣҲܱ֤ͼάѯһԣһܺõؽ2VNLٵά걸2.3VPAΪ3VPA-vm3VPA-mp3VPA-dwbֱ֣DW˺ͻִ.ò˼3ݡͬȴƺͰ汾ƣ4ݷڡ⡱Ĳ£Эݿ⡢ݲֿˢ²ûѯ.Ļԭ£
(1) ڵǰݿмһMonitorģ飬ⱨDBݵı仯DBݵκα仯insert/deleteMonitorһϢ֪ͨ⣻
(2) յDB˷ݱ仯֪ͨ󣬶ԻеӦ£ȻһӦϢDWˣIntegratorתӦViewMgrVM֪Merge ProcessMPЩʵ廯ͼθй.
(3) ÿVMһԶͼάֱ̣ĳʵ廯ͼĳһ汾ĸά.VMӦʵ廯ͼӦȡĸ²󣬲ActionList (AL)䴫͸MP.
(4) MP˽DWʵ廯ͼĶͰ汾.άͬ汾ViewUpdateTableVUTͨVUTDWжͼˢ²ͬԱ֤ͬ汾ŵʵ廯ͼ֮ʼһµ.
(5) DWˣÿʵ廯ͼ3ͬİ汾Current Version(CV)Next Version(NV)Future Version(FV).CVûʼǿɼģһȶֻ汾ĳ״̬һµ.NVһм汾ά˰汾VMٽԻݱ仯ֻ֪ͨǵȴԼǰάѯĽӦALݸMP.NVĸȫɺ֮佫һµģĳ״̬Ҳһµ.ʱǱɿɼԺûµOLAPѯ汾ִ.ʱлCVOLAPѯɣɽа汾л.FVDWԾİ汾ά˰汾VMԻݱ仯֪ͨҪάѯ⣬ӦALMP.3汾֮Ĺϵǣver(FV)=ver(NV)+1=ver(CV)+2.
(6) 汾лʱNVȡԭCVΪCVFVȡԭNVΪNVһµFVVM.ӦCVӦġʱݽ.
2.3½ṹ㷨ص
µ3ݲֿϵṹ3VPA㷨µص㣺
(1) ûʱʹݲֿ⣬ݲֿⲻרŵĶʱ͸άʱ䣬߿ͬʱУϵͳĿԣ
(2) ݲֿеĶʵ廯ͼ֮䣬ԼԴ֮ʼһµģ֧ѯҷظûĲѯһµģ
(3) 汾лƽᵼκ
(4) ݿϵͳ䣬ʹֻһģ鼴뵽ݲֿϵͳУݲֿϵͳеݿԿԽOLTPܻ½
(5) ǿϵͳԣݲֿδڻнУܴͳݿṹƵԼ.
33VPAͰ汾л
3VPAй漰6Ϣͣ
DB˵Monitorݱ仯֪ͨUΪ֮һ
ins(rt)ڱrвԪt del(rt)ӱrɾԪt
ⷢDW˵ݱ仯֪ͨеĲUȫӦdbupеĲ
DW˵ķάѯ֪ͨһ汾ŲN˲ѯķؽάģ汾ΪNʵ廯ͼVx
ⷢɲѯĽ֪ͨ
DW˷ѯ֪ͨҲһ汾ŲNѯDWǻĸ汾ʵ廯ͼ.
ⷢɲѯĽ֪ͨIntegratorյ֪ͨ󣬽ֱύûOLAPѯʵ廯ͼά.
㷨漰ı
AVNActive Version NumberAVNǵǰFVİ汾ţAVNver(FV)
UQSNUnanswered Query Setڼ¼лNŰ汾ͼOLAPѯ.ûһNŰ汾OLAPѯQʱUQSNUQSN{Q}˲ѯɺUQSNUQSN{Q}
3.13VPA-dwb㷨
еȫԴݿ⣬ʱһԪVNI1VND󣨷ΪޣʵпԽʼΪһᵽİ汾ţflagΪI.
3VPA-dwbͨ־λͰ汾ŶԻеݽпάȷݵһԲ.DBMonitorԭʼݱ仯֪ͨˢԼĿݣ𽫴˱仯֪ͨIntegrator.㷨£
ϢеϢӦ

if Ui=ins(rt) then
 Ԫt' t'.VNI = AVN t'.VND =ޣ t'.flag = It'.dbt = t
else /* Ui=del(rt) */
ҵԪt'ʹt'.dbt = t;
if t'.VNI=AVN then ɾt' ;
else { t'.flag = D;
t'.VND = AVN;}}
͵DWˣ

if N=AVN then
{/* QNkǻFVάѯ */ 
QNkʱ漰Ĺϵ 
ʹ㷨1r'еԪעۣ} 
else /* QNkǻNVάѯ */
{ , ʹ㷨2r' еԪ; }
ʹöԪdbtQNk, ANk
͵DWˣ

if N=AVN1 then { /* ǻNVѯ */
, ʹ㷨2r' Ԫ飻}
else /* ǻCVѯ */
{,ʹ㷨3r' еԪ飻}
ʹöԪdbt㣬
͵DWˣ
㷨1.
Repeat
t'.dbtr
if t'.flag=I then t'; }
Until t'.dbtrԪȫɨ.
㷨2.
Repeatt'.dbtr
if t'.VNIAVN-1 then
 if t'.flag=I then t';
else if t'.flag=Dt'.VND=AVN+then
t';}}
Until t'.dbtrԪȫɨ.
㷨3.
Repeatt'.dbtr
if t'.VNIAVN-2 then t';}
Until t'.dbtrԪȫɨ.
ʵ廯ͼ3汾ֱдΪ˱֤汾άʱֻܿԼӦݱ仯֮޹ص״̬.ֻܱ֤CVNVFVڻж֮Ӧһµ״̬.
3.23VPA-vm㷨
3VPA-vmDWͼάVMִе㷨.ͨţɶAL.ϵͳʱÿʵ廯ͼֻ汾CVFVNVFVֻһVMͼά.ϵͳа汾£ϵͳеʵ廯ͼ3汾ÿʵ廯ͼVxVMVMNVxVMFVxֱάNVFV.
VMFVxִȫ3VPA-vm㷨VMNVxڲٽջⷢݱ仯ִ֪ͨжdwbup¼Ĵ.㷨£ִд㷨VMNx
ʼ
ԻⷢϢӦ

 then mi/* ±ֶĵһ */
if Uiins(rt) then  kk1

 ˣ
WASNxWASNxQNkPNk1
else if Uidel(rt) then {kk1

 ˣ
WASNxWASNxQNkPNk-1

DeltaNxDeltaNxPNkANkWASNxWASNx-QNk
nk;/* ʱnΪֶһ */
if  then  ͵MP
ĳһʱDBݸµٶȽϿ죬DW˰汾лʱVMάѯҪWASNxwaiting for answer setڼ¼Щδյάѯ.DeltaNxһʱڼ¼ʵ廯ͼVNxĸ².,¼˴UmUnӦʵ廯ͼVNxȡĸ².Vݲֿʵ廯ͼĶ壬磨r1Ԫ2,3ʽӦĹϵ.QNkDW˷˵άѯʽV.
3.33VPA-mp㷨
MPάVUTFV汾NV汾3VPA-mpVUTִе㷨ά汾ͬĶʵ廯ͼ֮һ.SPA㷨1˼룬֮ͬǣ3VPA-mpа汾VMõǾв˼3VPA-vm㷨㷨VUTÿһпԴݿеĶ²Ӧ.㷨£
ʼ
յRELNi
if  then CollectCollectREL\+N\-i;
else 
յ
 if then
 VUTNһsУVUTNs,xݶӦUmUnVNx

.color=white;
else VUTNs,x.color=black; }
еProcessAction(); s=s+1; }
else ProcessAction(); 
procedure ProcessAction()
 VUTNs,x.color=red;
if VUTN1Ϊձ then ProcessRow(s); 
procedure ProcessRow(s)
 if xVUTNs,x.color=white then return;
if x,s'<s,ʹ(VUTNs,x.color=redVUTNs',x.color=red) then return;
ڪxVMN if VUTNs,x.color=red then VUTNs,x.color=gray;

VUTNs,x.color=grayif NextRed(s,x,N)0 then ProcessRow(NextRed)(s,x,N);
VUTNɾsУreturn; 
㷨УRELNiڼ¼Uiصʵ廯ͼģIntegratorÿյⷢUi󣬱ȷRELNiֵ䴫͸MP.ALLRELNs¼UmUnЩйصʵ廯ͼʱVUTһ£VUTNΪձʱALLRELNsҲΪռ.WTNsռʵ廯ͼĶ.ڶ漰ĸ²ֻܲһRELNiӦALMPMPյ֮ǰ޷ȷ֮ӦĵALLRELNsݣֻһʱCollectÿεRELNi.
ProcessActionУVUTN1жϣΪNVĸǻCVģFVĸǻNVģֻеǵǰһ汾ȶ󣨼VUTN1Ϊձʱſǰһ汾ʵ廯ͼݺ͵ǰ汾Ķһµǰ汾ʵ廯ͼ.ProcessRowе(ɴܵ.NextRed(s, x, N)صǽVUTNs, xcolorΪredб.
3.4汾л
DWˣлNV汾ͼάѾɣΪձһCVOLAPѯҲȫɣʱɽа汾л.DWˣ汾лҪִеĲ£
(1) AVNAVN1ɾCV汾ʵ廯ͼɱӦVMɾVUTCV
(2) CVNVNVFVVUTCVVUTNVVUTNVVUTFV
(3) ÿʵ廯ͼVxһµFV汾VMFVxάMPһµĿյVUTFV
ڻˣ֮Ӧǡݡ.VNDAVN2flag=DԪӻɾ.
4
ݲֿάѾΪҪо.3ݲֿϵṹ3VPA㷨ǿϵͳԣʹݿݲֿרעԼOLTPOLAPӦãݲֿϵͳ.ڲ汾άݲֿˢºͲѯͬʱУϵͳĸ²ֹκڽеĲѯϵͳרʱϵͳиάȱ㣬ϵͳĿ.
modifyԿɾ룬ҲԵдĶԴ˲
ڡFV,NV,CVֱʾʵ廯ͼ3ͬ汾ver(FV),ver(NV),ver(CV)ֱʾFVNVCV3汾ʵ廯ͼİ汾.
r'ǻⰴͼ3ĽṹrӦı
ݵΪ
߼飺ľУ19717ʿооΪݲֿ⡢ݿЭͬ. ĪٻУ19726ʿооΪݿЭͬ. У1965ʿڣоΪݿЭͬݿ⡢ܼϵṹ. У1938ʿʦпԺԺʿоΪݿЭֲͬм㡢ܼϵṹ.
ߵλľĪٻ졡Ƽѧֲصʵҡɳ410073
ο
1Zhuge Y, Wiener J, Molina H G. Multiple view consistency for data warehousing. In: Proceedings of the International Conference on Data Engineering, Brimingham, 1997. 289300
2Quass D, Widom J. On-line warehouse view maintenance for batch updates. In: Proceedings of the ACM SIGMOD Conference, Tuscon, Arizona, 1997
3Zhuge Y, Molina H G, Hammer J, Widom J. View maintenance in a warehousing environment. In: Proceedings of ACM SIGMOD Conference, San Jose, USA, 1995. 316327
4Bober P M, Towards practical multi-version locking techniques for on-line query processingPh D dissertation, University of Wisconsin-Madison, 1993
յڣ1998-09-22
޸ڣ1999-05-17
