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



ʵʱݿϵͳеǶ

ժҪͳԭһƽ̹ݿɵ,ִоACID(Atomicity, Consistency, Isolation, Durability).Ȼ,ʵʱӦû,Щȴ̫.һ֧ʵʱӦõǶģ,ǶԼȷԱ׼,ضǶʵʱȼ벢Э.
ؼʡģ,Ƕ,ȼ,,ȷ, ʵʱݿ.
ͼšTP311
Nested Transactions in Real-time Database Systems
LIU Yun-shengLI Guo-hui
College of Computer Science and Technology Huazhong University of Science and Technology Wuhan 430074
Abstract In the traditional transaction model, a trans action is a flat sequence of the database operations and the executions of trans actions have the ACID(Atomicity, Consistency, Isolation, Durability) properties. But under the real-time environment, these appear unsuitable. A nested transac tion model to support real-time applications is proposed and the properties and the correctness stanadards of nested transactions are presented in this pap er. The priority assignment strategies and the concurrency control protocol for nested real-time transactions are discussed with emphasis.
Key words Transaction model, nested transaction, pri ority assignment, concurrency control, transaction correctness, real-time d atabase.
ʵʱӦҪԶϵͳ(ݿ)״̬Ǩ,ضλʱ㴥ض Ļ.(triggered)ĻӦҪǴ(triggering) һһ򴥷.ҪṩǶ, Ƕĵ㷨Э鼰ִеȷԱ׼.
һ˵,ǶԴҪ¼:
1 ̬ĻӦҪΪ;
2 ڷֲʽӦû,һԻֳɸ,ڲͬĽڵϷֹ ִ,Щԭ;
3 һЩӦ,٣long-lived򿪶ˣopen-endedΪϵ ͳԴҪƿ.԰ѳ򿪶񻮷ֳɸ߼϶,ʹռõ Դܱǰͷ;
4 ӦڽṹʽҪһΪһ.
1 Ƕģ
1.1 Ƕ
ڴͳƽ̹ԭģ,һһƽĲ,ûڲṹ,ACID( Atomicity,Consistency,Isolation,Durability).ĵȺͲɴл ȷԱ׼.Ƕͬ.
1. ʽذһΪǶ. ߳Ϊ,߳Ϊ丸,p(t1,t2)ʾt1Ϊt2ĸ,c(t 2,t1)ʾt2t1.
ֿɰ.ͬ첽ַʽ.ͬʽ ,񱻴ִʱ,ڵȴ״̬,ֱִ.첽ʽ, ͬʱִ.
2. ִйдһΪΪǶ ,ΪNTE.
NTE=Eid(TID,SYN),
EidΪ¼ʶ,TIDΪıʶ,SYNΪ۵Ĵʽ.
һtϵǶ¼ɵļϳΪtǶ¼,ΪNTE t.
3. t1Ϊt2,Ϊp*(t1,t2),ҽ 
p(t1,t2)Ūt(p(t1,t)p*(t,t2)).
ʱ,Ҳt2Ϊt1ĺ,Ϊc*(t2,t1).
4. һ¼¼1ݳΪ ľ,ΪHt,
Ht=Et,tEtOEtTEtCEtNTEtEEt,
УtΪʱϵ,OEtΪĶ¼,TEtΪ¼,EEtΪⲿ¼, CEtΪʱ¼1,NTEtΪǶ¼.
5. ݿT,һtTΪ,ҽ
tT(ttp(t,t)).
6. ݿT,һtTΪҶ,ҽ 
tT(ttc(t,t)).
7. һݿT,t1,t2T,ҽ
c*(t1,t2)p*(t1,t2)(tT(p*(t,t1)p*(t,t2),
t1,t2λͬһ,ΪR(t1,t2).
8. ݿT,t1,t2T,ǳt1,t2Ϊ ,ΪS(t1,t2),ҽ
Rt1,t2!p*(t1,t2)!p*(t2,t1).
Ƕģ,ͬԴǶ׹ϵγνṹ.ͼ1һǶt 1,rA,wBݷֱʾݶAдݶB.t1ִһЩд ͬt11,t11ִ֮첽һt12,t 11ִt111.

1.2 Ƕִ
ڴͳƽ̹ԭ,һ,˳ִɵύѽӳݿ ,ز۶ݿⲿκκۼ.Ƕ,һز۲ һҪ丸ز,ִвԭ,زʱ, ѡ:(1) ִи;(2) ִС/;(3) ܸز ;(4) ز.Ƕύز۾봫ͳԭͬ:
(1) ύ:һύζ߼,ݿĸֱ ĸύʱӳݿ.
(2) ز۹:һӣزʱ,еĺһز.
(3) ɼԹ:һܷеݶ;ύ, ĸĿɱ丸,ֵܱ.
ύز۹֤˺۵Ըزϵ,ɼԹ򼰺 ۵ĲЭ֤ݿһ.
ڴͳԭ,һĿʼ(BEGINt)ύ(COMMITt)ز(ABO RTt)ûбȻϵ,Ƕ,.и tp,tc,HΪǵľ1.
 (1) Ըزϵtc AD tp,
tc AD tp:(ABORTtpH)(ABORTtcH).
(2) Ըڿʼϵtc BD tp,
tc BD tp:(BEGINtcH)(BEGINtptBEGIN tc).
(3) ύ-ֹϵtp CD tc,
tp CD tc:(COMMITtpH)(ABORTtctCOMMIT tpCOMMITtctCOMMITtp).
1.3 Ƕȷ
ǶȷԵĸ漰ķ֮ͳĶΪ,ף1,2жԴ ϸ,:ʱȷԡṹȷԡΪȷԼȷ.ף1,2 ,ʱȷԺͽṹȷɵȺͨһĲ㷨,ʹʱ Ժͽṹ()õʵ,Щ,׸.Ϊ ȷԼȷ,СǶ׿ɴл֤.
9. T={t1,t2,...,tn},DtΪtĺ, T={ti1,ti2,...,tim}mnΪTһִм,ΪT=PES (T),ҽ
tT(tT(tDt(tT))).
һTִк,ݿ״ֱֵ̬ΪDBS(T)RV(T),һ t1,t2,...,tk,ִкݿ״ֱֵ̬ΪDBS(t1,t2,...,t k)RV(t1,t2,...,tk).
10. T={t1,t2,...,tn},һִǶ ɴл,ҽ
T={ti1,ti2,...,tim}T(T=PES(T)DBS(ti1,t i2,...,tim)=DBS(T)RV(ti1,ti2,...,tim)=RV(T)).
ִеǶ׿ɴл֤ݿһ.α֤Ƕ׿ɴл. 
2 ǶʵʱĴ
ͳûνĵ,ȷ˳.˵ĵ, ӦڲƵķ,Դľ.ʵʱĴҪ ɡ벢,һȼɲȷ,ĵȰȼоͱȽϼ ,Ĺؼȼɲ벢ЭĿ.
2.1 ȼ
ʵʱݿϵͳ,ȼĹؼֹ.ĽֹӦ ӦʱҪʱ.ÿǽֹڵȼɲ Ժ,ÿȼCPUʱϵͳԴ.Ƕ,ÿӣ һϵͳԴĵλ,,ʹһθݸĽֹֹ ,ȼ.
* ͳһֹڣSD
òԵҪ˼ǻڽֹȼ.ȼǶ׽ṹ ı,ͬʱ,еĺһĽֹ.Ըе еκʱ̶õͬȼ.
tΪһǶ,еĺͬĽֹڼȼ.
t(p*(t,t)(d(t)=d(t)(pr(t)=pr(t))),
d(t)ʾtĽֹ,pr(t)ʾtȼ.
* úĽֹ
÷Ҫ˼ǰҪɵĹġֹڡ .Уslackʱ3ڸ֮ķҲǰı .ͬʱ,Ҳͣʵʱ񡢹ʵʱӲʵʱ.ǰ ʽúġֹڡ:
dv(tc)=min(dg(tc),dg(tp)-Cadj-A).
dg(t)ǰ۵ĸûûⲿҪȷtĽֹ.AΪ ύӳٻֲʽµͨӳ,CadjǷӳڶϵͳԴҪͻĵ ʱ:
(a) 첽ִ,ǶԴķûгͻ(ǲ Դĳͻ),ڸĽֹ֮ǰ,Ͳᵼ¸ ֹ,,Cadj=0;
(b)  첽ִжǶԴķʴڳͻ;  ͬ.ʱ,ܱȴ.,Ϊ 㹻ʱֹ֮ǰ,ʱ䵽Ľֹ֮ʱ ӦôڹƸҪõʱ.ݸ,Cadjµ趨:
(1) ͬʱΪ,һĿʱ:
Cadj=ES(s)+sl(tp)*(ES(s)(ES(s)+ES(tc))).

ES(s)ʾtpɴtcǲֹҪʱ,ES(tc)Ϊt cҪʱ,sl(tp)ΪtpĿʱ.
(2) tpΪ,tcΪ,tpȫʱtc,Cadj=ES(s).
(3) tpΪ,tcΪ,tpȫʱԼ,Cadj=ES(s)+sl(tp) .
ڸĸˡֹڡ֮,ǿԷȼpr(t)=F(dv( t)),ȻȼеȺͲ.
2.2 
ǰύͿɼԹ,ʵʱԺǶ׽ṹص,һְ ȼز۵ĲЭ,:
1 tһѱסݶoʱ,ؼ̳ ,˺ύǰ,ٶoĳͻȡ.Ϊ˱֤һ Ƕڲݿһ.
2 ֵ֮ĳͻͳЭ鴦.
T,ݶotT,L(t,o,R),L(t,o,W),L(t,o)ֱʾtoĶд ۶д,ȼΪpr(t).
Эʽ:
IF tT(!L(t,o))
THENtסݶo
ELSE IF tT(!L(t,o,w))tΪoĶ
THEN tסo
ELSE IFtT(L(t,o)R(t,t)) /*סoΪtļ */
THEN IFtT(L(t,o)P*(t,t)) /*סoΪt */
THEN t̳жo,ttύǰܷo
ELSE
ABORT t
ELSE IFtT(L(t,o)!R(t,t)) /*סot ļ*/
THEN IF tȼסoķǼȼ
THEN زסoķǼ
IFtT(L(t,o)R(t,t))
THEN IF tT(!L(t,o)p*(t,t))
THEN t̳
ELSE ABORT t
ELSE tסo
ELSE ABORT t
1. һT={t1,t2,...,tn},ִв ǰĽṹϵЭ,Ƕ׿ɴл.
֤:ΪԸزϵ,ݿĸ ֻеĸύʱӳݿ,ͱ֤һ ִеЧͬһִмPES(T)ִ.ƹ(1)֤˸񲢷ִ ʱݿһ,ƹ(2)ֵ֤񲢷ִʱݿһ .,TִЧͬPES(T)һִеЧ,ִǶ ׿ɴл.
3 
ͳԭģͶ͵ӦЧģʵʱӦû£ܴڽṹϵĸԣҪṩģӦʵʱӦõ󣬱ⷽĹҪУһǶģͼԣǶʵʱȼɲԣǶ׵ṩһǶĲЭ顣
ʵʱӦû,ԭȼɼĵȺͲн϶. ǵǶ,Ƕ׽ṹʹĴ봫ͳԭкܴĲ ,,ǶĻָһӵ,Щǽоص.

оõȻѧ͹Ԥл.
, 1940,,ʿʦ,ҪоΪִʵʱʱڴȣݿ 뼼伯ʵ,ݿϢϵͳʵʱӦ,ѧ֧Ż.
,1973,ʿ,ҪоΪʵʱݿϵͳ. 
ͨѶϵ:,人 430074,ѧѧ뼼ѧԺ
ߵλѧѧ뼼ѧԺ 人430074
ο
[1] ,.ʵʱݿϵͳȷ.Ӧ,1995,12(6):18 
(Liu Yun-sheng, Hu Guo-ling. The correctness of real-time database sys tems. The Computer Application and Software, 1995,12(6):18)
[2],Ramamritham K,Stankovic J.ʵʱݿ.ѧ,1995,6( 10):614621
(Liu Yun-sheng, Ramamritham K, Stankovic J. About real-time database transacti ons. Journal of Software, 1995,6(10):614621)
[3] Abbott R K, Garcir-Molina H. Scheduling real-time transactions: a performance evaluation. ACM Transactions on Database Systems, 1992,17(3):513560
1997-10-14յԭ,1998-06-22յ޸ĸ
