ѧ
JOURN AL OF SOFTWARE
1999ꡡ1010ڡVol.10No.101999



ʱ̬ݵıȷֶδ洢ԼЧ
Ƴ л־ʤ 

ժҪʱ̬ݿûݺ񱡹ŵص,ȷֶδ洢,һʷΪ3ʱ,ֽʡȴ洢.˷ֶδ洢ݽṹʱת㷨ѹ㷨.΢ʵòĶ,һʱ̬洢ܶȺʱ̬ѯٶһ.
ؼʡʱ̬ݿ,ֶδ洢,ʱת㷨,ѹ,ʱ̬洢ܶ.
ͼšTP311

Segmented Storage with various Chronons in Temporal Databases 
and Efficiency Analysis
TANG Chang-jie YU Zhong-hua YOU Zhi-sheng ZHANG Tian-qing XIANG Li-min
(Department of Computer Science Sichuan University Chengdu 610064)
Abstract Based on the usage frequency of the data in temporal database, the storage method with three historical segments is proposed in this paper. The object history is divided into three segments, and stored in different media with various chronons. The special data structure for segmented storage is discussed, the age transfer algorithm and the compress sampling algorithm are proposed. The performance study shows that the time and space efficiency are promoted one magnitudes.
Key words Temporal database, segmented storage, age transfer algorithm, compressed sampling, temporal storage density.
20,ʱ̬ݿϵͳ(TDBMS)оһֱΪ TDBMSиŬ.ʱ̬ݿ(temporal database,TDB)ּڱ汻ݿⱾʷ.ʷֻ׷,ɾصʹTDB,ʱЧʽϵ,һѳԼTDBMSķչ.
ʵû,TDBӦöк񱡹ŵص,ԽݵĲѯ,Ҫϸ;ʷԶݲѯ,Ҫ.һʵ,HBase˷ֶαȴ洢,һʷΪԶС3ʱ,,ͨʱת㷨ѹ㷨,зֽʡȵĴ洢,ݲֿ޷.ʱ̬洢ܶȺʱ̬ѯٶϻһʱЧ. ۷ֶδ洢ʱ̬ṹ㷨ʱЧ.
1ͳʱ̬ݿ洢ľ
1.1 ʱ̬ݿд洢
TDBоʱ̬ݿоصŵʱ̬,,Time Split B+ Tree,Append Only Tree,Checkpoint Index,Monotonic B+ Tree[1],,ʱ̬ݿԤģ֧͡־[2]ǰ[3]ͱʱ[4]ȷȡ˿ϲɹ.Ѿоʱ̬ݴ洢Ҫ.
A. ʷֶ,ʱΪ,TDBģͲһ[1].
B. ʱΪ,TDB=+ʷ,ձڸٽ(Ӳ),¼Чڽ,¼Ϊʷ,ת浽ٽ(Ŵ),ʷٷֶ[5]. 
Bŵ,û漰ʷݡTDBΪͳRDBʹʱ,нϸЧ[5].,ʷֶ,ʵ.ȱ,ڸٽеݲʷ,ֻʷһ˲.ʷӦ,ʱЧͬڷA,洢Ч.
,ʷֶ,õһʱ,¼Ϊʷ.
1.2ź͸
ʱ(chronon)ʱ̬ϵͳѡֵ֧Сʱ[1].ϵͳʱΪ0,Kʱӵʱ̼ΪK,ϵͳʱΪSys_T={0,1,2,,K,,Now,,MaxSysTime}.Sys_TӼ{t,t+1,t+2,,t+n=t'}Ϊ,Ϊ[t,t'],ʱnΪĳ.ʱ̬ݿμ[1].
Ϊ˶ʱ̬ݿʱЧ,и:
(1) ¼ʷƽȳΪƽʷ(span),ΪS.,1 000¼2 000ʷ,ƽʷS=2().ӳTDBм¼ʷĸ.
(2) TDBö¼,¼ȼΪL(Kֽ).
(3) ʷݰʱηִڶִ洢,JƽȡٶȼΪVJ(¼/s).
(4) ÿKֽϢʷȳΪʱ̬洢ܶ,ΪTemp_D(䳤/Kֽ)
(5) ϵͳÿܲѯϢʷȳΪʱ̬ѯܶ,ΪTemp_V(䳤/s).
1.3 ʷдȡ100¼ʱԴ
һеȴ۵ϵͳ:ʱC=1(s),¼ƽʱS=1(h),ÿ¼L=1(Kֽ),ƽȡٶV=500(Kֽ/s).ͳʷдȡ100ʱ̬¼ʱԴ:
洢ռM=100L=100(Kֽ) ȡʱ t=100/500=0.2(s)
ʱSpan=100S=100(h)ʱ̬洢ܶ Temp_D=Span/M=1(h/Kֽ)
ʱ̬ѯܶTemp_V=S/t=500(h/s),ÿܲѯ500Сʱʷ.
ʵ,ʱ̬洢ܶȺʱ̬ѯٶȲʵõҪ.ԭǵʷƺûʱ̬Զٵص,ʷԶϻ˹ʱͿռ.
2,ֶ,ֽʴ洢ṹ
Ϊʱ̬洢Ͳѯ,Hbaseģ[6,7],ǰѱʷʱ仮Ϊ3ʱ,һ洢ʽΪʷ,ͼ1ʾ.Ҫ.

ͼ13ʱں
(1) 3ʱ.6ʱ̱OB(OldAgeBegin),OE(OldAgeEnd),MB(MidAgeBegin),ME(MidAgeEnd),CB(CurrAgeBegin),Now(CurrAgeEnd)ʱ̬Լ0=OB<MB OE<CB ME<Now.[OB,OE],[MB,ME],[CB,Now]ֱΪŴִ.
(2) .[MB,OE][CB,ME]ֱΪŴ-ںͽ-ִ,еʷʷʱиһ.ʱתģԶƽתƹгڵʷ.
(3) ȡֽʴ洢.ûɷֹŴִòͬʱ.ִ͹Ŵݷֱ𱣴ڴ桢Ӳ̺CDROM(Ŵ).ڴΪ͹ŴøٻM_Cache,O_Cache,ߴСʹƵͬ,ĬΪ101.
(4) ʹƵ. ϵͳʵŴʷʷִʷʹƵ.ʼֵΪŴýִ=110100.
ҪȫװڶAges,ΪAgesݳԱ.
ûMidAgeBegin(MB),OldAgeEnd(OE)Ŵ-ڳ3е,ԻֹŴͽ.CurrAgeBegin(CB),MidAgeEnd(ME)Լ-ִMid-CurrLenе߿ԻִֽԼ-ִ.
ʷ롰TDB=+ʷʽ[1,5]űʵĲͬ.HBaseģ͵ĵǰڲǿ,[CB,Now]ʷ,Ᵽ֤ܸٷǰжϵ,ʷеĹԺҪܵʱת㷨֤˶ʱڡʵƽЧĹ.
1:ǰʱ̶̬ػʱ,3þʱ̻ʱ.
Set Ages.MidAgeBegin=Ago (5 years)
Set Ages.Old_Mid_Len=60 Days
Set Ages.CurrAgeBegin=12-31-1996
1ִʱΪ׼,5֮ǰʱΪĿʼʱ,2ùŴ-Ϊ[MB,MB+60 Days].Ago(5 years)һʱ̬,TDBMSϵͳڲ귨תΪִʱ̵5ǰһʱ.Ago()ֵʱǶ̬.ʱת㷨ɶ̬.
1еYears,Months,DaysΪTDBԤ䳤Ⱥ,12-31-1996Ϊϵͳʱֵ,TDBMSԶذѳȺչΪʱ.,Days=243600(s).ϵͳʱԶתΪ0ʱ̿ʼʱ.
3ʱת㷨
ʱת㷨ʷܰȫƽȵعݵĹؼ.1ʾ,ʱֵ͹ڿʱ仯.¡ڵʱ̬ϵڡ.Խ-ִΪ,ڱ仯תƷĹϵ.
-ִ,ֱǾɡ¹Ϊ[CB,ME][CB,ME].4˵ȫ4=24,CB<ME,CB<ME6:
(1) CB<ME<CB <ME(2) CB<CB <ME<ME (3) CB<CB <ME <ME
(4) CB <ME <CB<ME (5) CB <ME<CB<ME (6) CB <CB<ME<ME 
һ,֪ǰ3ֵĹΪCB<CB,ִʼʱֵCBʱϺ.ʵ,Ҫʷ[CB,CB]ʷתƵʷ.3ֵĹΪCB <CB,һûǿƸıʱų,Ҫʷ[CB,CB]ʷƵڴĵʷ.
ʷͨϵͳԤĴ,(һСڹڳȵһ)ʱתģ,еĳڲԶƶƵȷʱ.C++ķд㷨ִ-ݹɴ.
㷨1. Curr_MidAge Transfer Algorithm (ִ-ת㷨)
: ִʷʷ.
: ִʷʷ.
Ч: еĳڲתƵӦʱ.
HBaseCurr_MidAge_Transfer(CurrAge,MidAge) ΪHBaseĳԱ
{ CB_Old=CurrAge.GetOld_CB(); λȡɵġִʼ
CB_New=CurrAge.GetNew_CB(); λȡµִʼ
ME_Old=MidAge.GetOld_ME(); λȡɵġյ
ME_New=MidAge.GetNew_ME(); λȡµĽյ
if (Old_CB<New_CB) ִʼʱȻ
{ for (each Record in([Old_CB,New_CB]CurrAge)) ιڼ
{ Record.Verify(); Уʷ
If ( Record.Is_not_in(MidAge)) 
{ MidAge.Append(Record); ׷Ӹü¼ʷ
CurrAge.DeleteRecord(Record)); δִʷɾü¼
};
} End of for
MidAge.CompressNewData(); νʷѹ,Ľ(1)
}  end of if
else if (New_CB<Old_CB) μ(2)
{ while (Record.Is_in ([New_CB,Old_CB]MidAge))
{ if (Record.Is_not_in(CurrAge))
CurrAge.ExpandChronon_Append(Record); θƵִʷ, (3)
};   end of while
}  End of else
};

(1) Compress_NewDataMidAgeĳԱ,ѹ,ϸڽһڽ,ʱɽΪʲô,Trueƽ.
(2) (New_CB<Old_CB)һֻǿʱ,ʱ([New_CB,Old_CB]MidAge)ɾRecord,ڴȡ.
(3) չʱӦִʱ.,MidAgeCurrAgeеʱӷֱΪmonthDay,MidAgeеԪ(Temperature=8,[96.1,96.2])ʾ961ƽ¶Ϊ8,չʱӺΪ(Temperature=8,[96.1.1,96.2.1]),ʾ961ÿ¶Ϊ8.
1. еʱΪN,ʱת㷨ļΪO(N).
֤:ʱת㷨forѭ,ѭRecord in([Old_CB,New_CB])ȡֵĴN,ѭеĲɾóC1,ͬ,Whileѭ,ѭȡֵĴN,ѭCurrAge.ExpandChronon_Append(Record)չʱ̬ʱ,Ľ(3)ʾ.ֻǰϸ,óC2,ܵļN(C1+C2),ԼΪO(N). 
4ʱʱ̬ݵŨ
ӦöʷϢҪԶԽص.Ϊ,˱ʱ.ĿTDBĸ[6],ʷзչΪȴ洢Ļ.Hbase,ִʷʷ͹ŴʷʱӷֱΪSecond,DayYear.ûͨTDML޸ʱĬֵ.,ͨCurrAge.Set(Chronon, 1 Hour)԰ִʱΪ1Сʱ.ʱᵼ˱ʱȴ洢,ʱתƹеѹչ,ʷЧʵĹؼ.
ʱ̬ݵŨ(ֳΪѹ)ʱתƹн.ݴִת,ӽŴתʱ,TempoTransfer㷨еCompressNewDataԶûԤѡķѹ.ѹλóȡֵͳƷ.
(1) λóȡ.û涨ȡλPercent,0 Percent 100,Percent=50Ϊ͵е㷨.ݴִתʱ,㷨1,ͨӳԼ,еCompressNewData(bounding)ͬ(㷨2),ע㷨еġƶMove_One_New_Record_To_WorkSpaceѶƵĿĵ,ͬʱҪɾȥԴ.
㷨2. λöȡ㷨
MidAgeCompressNewData() //ʷMidAgeĳԱ
{ SmallChronon=CurAgeChrono;  //ִʷʱ;
BigChronon=MidAge.Chrono; //ʷʱ;
ArraySize=BigChronon/SmallChronon;//ʱѹ
WorkSpace=new RecordType [ArraySize]; //Ҫռ
TotalLeftRec=GetTotalNewRecNum(); //ļ¼
Finish=False;Count=0; //ʼѭ
While (not Finish)
{ Move_One_New_Record_To_WorkSpace ();
RecordLifeSpan=GetNewRecordLifeSpan(); //ȡ¼¼
Count=Count+RecordLifeSpan/SmallChronon; //Ҫ1
TotalLeftRec- - ; //ļ¼1
If (Count=ArraySize)//һ顢ʼ
{ Sample=Take_Sample(WorsSpace,Percent); //ָ
MakeCompresedFlag(Sample);//ѹ
MidAge.Append(Sample);//׷ӵʷ
Count=0;//׼ѭ,ѹһ
Clear(WorkSpace); //׼ѭ
};
Finish=(TotalLeftRec==0);
//Ҫ,ʣµĲһ,һѹ
}
}
(2) ֵ.Ӽ˵.
2:ִʷʱΪ,ʷʱΪ,Ϊ10,ʱת㷨ȰѹƵʷ,ȻCompressNewData.,ݺϴδѹȡļ¼,ÿ7һƵռ7վֵ,Ȼƻؽʷ,7һתʱ.ֻ㷨2޸Take_Sample()Ϊ7վֵ.
(3) ͳƷ.Take_Samleвͳƺ,ֵֵСֵعֵȵ.HBase,ûָ,ֱOLEƷͳӦģ.
ʱתƳаʱ̬Ũ.ʷеִʷǱ׼ʱ̬ݿⷽʽ,ʷŴʷеѾȡӹŨ,ĳ̶ֳϾмݲֿɫ.ڴ,ʱתƼʵݿݲֿ޷.
5봫ͳ洢ʽıȽ
Ϊ˱ȽʱЧ,зźԼ.
TDBѰʷƻֳʷʱTi,i=1,2,3ֱʾִ͹Ŵ.
(1) ʷTi=[Bi,Ei],ӦøΪPi,0Pi 1,P1+P2+P3=1.
(2) ʷTiʱΪCi.Ti,ÿ¼ƽʷȼΪSi.
(3) TiʱӦĴ洢ƽȡٶΪÿVi¼.
(4) ʷ΢в(ӽʵ):
ʹƵP1=0.9,P2=0.07,P3=0.03;ÿ¼L=1(Kֽ);
ʱC1=1,C2=1,C3=1;
¼ƽʱS1=1Сʱ,S2=1,S3=1.
ƽȡٶV1=10 000(ڴ),V2=500(Ӳ),V3=50(Ӳ).
ʷ´ȡ100¼ʱԴ.ʹø,100¼зֲTiʱ100Pi¼,ʷΪ100PiSi.µ? ͶǴi=1i=3.100¼,:
ܿΪS=100 PiSi;
ȡʱΪt=100 (Pi/Vi)();
ܴ洢ռM=100L(Kֽ);
ʱ̬洢ܶTemp_D=S/M=( PiSi)/L;
ʱ̬ѯܶTemp_V=S/t=( PiSi)/((Pi /Vi)).
Щʽṩ˵ʷ¸ܵķ.޸Pi, Si,ViĴС,ܵõͬ.
ͳ洢ǵʷ[1,5],ʷƿɿʷƵ.ʷ,T2=,T3= ,P1=1,P2=0,P3=0(ִֻʷ׶);V1=V2(Ӳ̴洢),ʷ˻Ϊʷ.ʷƹʽ,õʷµĽ1еĽһ.
HBase΢еĲʽ,ֲͬ´ȡ100¼ԴȽϼ1.,ʷƵʱ20,ʱ̬洢ܶ24,ʱ̬ٶ58.кTDBMSڲcacheЧӦ[7]ʱ̬תƵĴ.ԭ,һϵͳвʱת(,һһλһһ);һ,ʷ,ڲ,һֻռ5%,ָ1,ʱת㷨ļΪO(N),ʱת㷨ʱ,Ժ.
1 ȡ100¼ıȽ

ȡʱ(s)ʱܿ(h)洢ռ(Kֽ)ʱ̬洢ܶ(h/Kֽ)ʱ̬ѯܶ(h/s)
ʷ0.0832 41810024.18291 312
ʷ0.21001001500

 
ʱЧ汾.һ,ʱת㷨ݽѹ,Ӧ,,ʹʱ̬ϢܶȼӴ.,ûʷݵǺ񱡹ʱ,ڸٽн.
עͣоõȻѧ͹ҽѧعԱ
߼飺Ƴܣ1946,,ҪоΪݿ
л1966,ʿ,ҪоΪ.ݿ
־ʤ1945,,ʿʦ,ҪоΪͼݿ
죺1971,ʦ,ҪоΪݿ
1961,ʿ,ҪоΪݿ
ߵλ:Ĵѧϵ ɶ 610064
E-mail: chjtang@scu.edu.cn
ο
1Tansel A, Clifford J, Dadia S et al. Temporal Databases Theory, Design and 
Implementation. Redwood, CA: Benjamin/ Cummings Publishing Company, 1997. 418
455
2ʦ,С.ʷݿ֧־ߵо.о뷢չ,1998,35(4):329322
(Zhang Shi-cao, Yan Xiao-wei. A study of historical database for decision 
making. Computer Research and Development, 1998,35(4):329322)
3Tang Chang-jie, Yin Bo-wen. The premonitory dependency of historical database and
its mathematical properties. Science in China (series A), 1989,32(6):758768
4Ƴ,ӻ.ʱ̬ݿıʱ.:ű.ȫ12ݿļ.
人:ѧ,1994. 419423
(Tang Chang-jie, Wu Zi-hua et al. The time axis with variable granularity in 
temporal database. In: Feng Yu-cai ed. Proceedings of the 12th Conference of 
Database in China. Wuhan: Huazhong Polytechnic University Press, 1994. 419423)
5Ahn I, Snodgrass R. Partitioned storage for temporal databases. Information 
Science, 1989,(49):103146
6Tang Chang-jie, Xiong Min. The temporal mechanisms in Hbase. Journal of Computer 
Science and Technology, 1996,11(4):365371
7Ƴ,.ݿϵͳڲṹCʵ.ɶ:ӿƼѧ
,1995.3763
(Tang Chang-jie, Zhang Tian-qin et al. The inner structure of database 
management system and its implementation in C Language. Chengdu: Press of
University of Electronic Science and Technology of China, 1995. 3763)
ոڣ1998-07-14޸ڣ1998-10-20
