ѧ
JOURNAL OF SOFTWARE
1999 10 7ڡNo.7 Vol.10 1999



ʶоʵ
ࡡ¾
ժҪʶķӰǶִЧʵҪ֮һ.Ƕģ£ʶ.ԴΪ,һϵʵЧķ.,λʶʵӦƵݿϵͳKDOODB(KeDa object oriented database).ܲԵĽ.
ؼʡݿ,,Ƕ,ʶ,.
ͼšTP311
Research and Implementation of Transaction Identifier
WANG Yi-jie WANG Yong-jun HU Shou-ren
National Laboratory of Parallel and Distributed Processing Changsha Institute of Technology Changsha 410073
AbstractThe assignment of transaction identifiers is one of the important factors influencing the per-formance of nested transactions. In this paper, the requirements which the transaction process poses on the transaction identifiers under the nested transaction model are analysed. Based on this, a series of efficient and practical assignment strategies are proposed, and the bit-based transaction identifier strategy is implemented in the object-oriented database systemKDOODB (KeDa object oriented database). At last, the performance evaluation results are given.
Key wordsDatabase, transaction process, nested transaction, transaction identifier, assignment.
ʶtransaction identifierķӰǶ13ִЧʵһҪ,ͬʱҲһױӵ,ʶķ䲻ռùĴ洢ռʹʱ.Ŀǰ,ԽԽϵͳʼṩǶ֧,ǻûгֿʶķ.
Ǵʶ,Ƕģ͵ľص,һϵʵáЧʶԣλʶԡĽʶԺŻʶ.ǽνṹйϢЧؼ¼ʶ.봫ͳĻ͹ϣĲ,Ǽ˶Դ洢ռʹʱЧ,ǶЧ.ͨģԳ,ǽ˱Ƚȫ.λʶԾƵݿϵͳKDOODB(KeDa object oriented database)ʵ,ΪKDOODBϵͳЧ춨˼ʵĻ.
1 ʶ
ͨ,ϵͳָͻ.ǶʶԹΪ
1ֱӴıʶõ丸ıʶ
2ʶνṹĿȺ͹ṩõ֧֣ԿȺ͹ûƣ
3ʶ洢ṹܹṩ㹻ʶʶĿûƣ
4ʶжǷ-ϵ
5ʶҳ߲ķǹͬȣ
6ʶ洢ṹӦ,ȿɱ,ܹô洢ռ,Чش洢ʶͶ̱ʶ.
2 ʶ
2.1 
ǶʶԵоһִͳĻΪ.ֻ,ʶһɱ䳤ȵʾ.ڶ,ʾʶһԪع,ε𽥽,ʾʶԪظ.ÿһµ,ʶ丸ʶһֵֵԪع.ԱȽϼ,Ҳ˶ĳЩ󣨼145.,Ĵ洢ռ俪ܴ.4ֽڵĳ,λڵNжٸ,ÿNıʶҪ4Nֽڱʾ,⽫ɼĿռ˷.
2.2 λʶ
˶ĳЩ,˵,һЩȽϺõ.,Ҳһȱ㡪Ĵ洢ռ˷.ڡﳤ̡ܶԭָ,˻λʶ.Դ洢ռʹλΪλ,Գ4ֽڣΪλǵ,ӶЧر˴洢ռ˷.
ڻλʶ,ıʶ丸ıʶ,һʶɸԪع,ÿԪνṹеһӦ.ÿԪһλıбʾ,ɱ뵥Ԫ,뵥ԪֵܺͼΪԪصֵ.뵥ԪĻλĳԤȶ,һ뵥ԪܹʾֵΧҲԤȶ.Ԫصֵһ뵥ԪıʾޣnǱ뵥Ԫĳ,2n1ʱ,ñ뵥ԪΪȫ־ȫ㣩,һµı뵥Ԫ.Ԫصֳֵ뵥ԪĹͬʾޣ22n1,ٷһµı뵥Ԫ.,ֱҪΪֹ.ʶĵ1ڱʾԪӦı뵥ԪĿ.
ʵ,ڻλʶԣͼ1ʾ,ʶһϵб뵥Ԫ,߼ɸ,ÿбʾһԪ.ͨжϱ뵥ԪľݣǷȫ־ȷеĿʼʶĵ1뵥Ԫʼ,жÿһ뵥Ԫ,ֱҵ1δȫ־ı뵥Ԫ,Ϊֹǵ1Уһ뵥Ԫ־ŵ2еĿʼ,.ÿ뵥ԪֵӾ͵õӦֵ.пԱʾĲֵͬĿΪN2n1NΪ뵥ԪĿ.

ͼ1λʶԵʶṹ
λʶ˶ʶĸ.
1,ʶĵ1,õԪӦı뵥ԪĿSumȻ,ĵڣSum-12뵥Ԫ,жǷȫ־,ǰSum-1뵥Ԫͱʾ丸ıʶ,ڣSum-23뵥ԪжǷȫ־,ֱҵδȫ־ı뵥ԪΪڣSum-k 뵥Ԫ,ôǰSum-k뵥Ԫʾ丸ıʶͼ1ʾ
2ڶԱеĳȺ͸ûκ,Կ֧Ⱥ͹ȵνṹ
3ڶԱеĳȺ͸ûκ,ṩʶ޷Χƣ
4ͨжϳʶǷʶȷǷ-ϵ
5ӵ2пʼ,αȽʶı,ֱֵ1ͬıΪֹ,ҵ߲ǹͬȣ
6ʶĴ洢ṹȿɱ,λΪλж̬ռ,뵥Ԫ,ܹӳֵô洢ռ,Чش洢ʶͶ̱ʶ.
2.3 Ľʶ
λʶ˶ĸ,λΪλʹô洢ռ,ȽЧر˴洢ռ˷.ͨ۲Ƿ,ʶԪֵԽ,ȫ뵥ԪĿԽ.ʵ,ڱʾʶԪֵʱ,ֻ¼ȫ뵥ԪĿ,ؽȫ뵥Ԫһһг.Ϊ,ڻλʶԵĻ,˸Ľʶ.
λʶ,ڸĽʶ,ӦÿԪصıɱ뵥Ԫͱ뵥Ԫ.Ԫصֵһ뵥ԪıʾޣnǱ뵥Ԫĳ,2n-1ʱ,򽫱뵥Ԫֵ1,Ԫصֵȥʾޣ2n-1޸ĺԪֳֵ˱뵥Ԫıʾ,ٽ뵥Ԫֵ1,Ԫصֵȥʾޣ2n-1.,ֱҪΪֹ.ñ뵥Ԫ¼һеı뵥Ԫȫ뵥Ԫĸ,λڱ뵥Ԫǰ棨ͼ2ʾ.뵥ԪɼԪ,ԪֵܺͼΪԪصֵ,ԪĳҲԤȶ.ֵһԪıʾޣmǼԪĳ,2m-1ʱ,򽫸üԪΪȫ־ȫ㣩,һµļԪ.ֳֵԪĹͬʾޣ22m-1,ٷһµļԪ.,ֱҪΪֹ.ʶĵ1ڱʾĲΣʶԪظ.

ͼ2ĽʶԵı
ΪȷʶĳԪصֵ,,ԪصǰmλmǼԪĳȣ,Ԫȫ־,mλ,ֱҵһδȫ־ļԪ,ѶļԪֵӾ͵õ˼ֵNumȻ,nλnǱ뵥Ԫĳȣ,õ뵥ԪֵNUô,ԪصֵΪ2n-1(Num1)NU.пԱʾĲͬԪֵĿΪk2m-12n-1kǼԪĸ.
ĽʶԽϺõ˶ʶĸ.
1,ʶĵ1,õĲLȻ,ģL1,͵õ丸ıʶ
2ͨչ뵥ԪĳȣӼԪĿ,֧Ⱥ͹ȵνṹ
3ͨչ뵥Ԫĳ,ṩ㹻ʶ
4ͨжϳʶǷʶ,ȷǷ-ϵ
5ӵ2пʼ,αȽʶı,ֱֵ1ͬıΪֹ,ҵ߲ǹͬȣ
6ʶĴ洢ṹȿɱ,λΪλж̬ռ,˳ֵ˴洢ռ,ܹЧش洢ʶͶ̱ʶ.
2.4 Żʶ
ĽʶԽϺõ˶ĸ,õĿչ.,ͨʡȫ뵥Ԫʡ洢ռ,,Ա뵥ԪеȫԪûнЧĴ,,ûгô洢ռ.ԸĽʶԵĲ,Żʶ,ЧشȫԪ,ʵ˳ô洢ռĿ.

ͼ3ŻʶԵı
ŻʶԵҪ˼루ͼ3ʾǣԪȻɻλıбʾ,ɱ뵥Ԫͱ뵥Ԫɣ뵥Ԫȡֵͱʾʽλʶͬ뵥ԪɼԪ,ԪĻλĳԤȶ,һԪܹʾֵΧҲԤȶ.뵥ԪֵһԪıʾޣmǱ뵥Ԫĳ,2m-1,ֵ1,뵥Ԫֵȥʾޣ2m-1޸ĺı뵥Ԫֳֵ˼Ԫıʾ,ٽֵ1,뵥Ԫֵȥʾޣ2m-1.,ֱҪΪֹ.¼һеļԪȫ뵥Ԫĸ,λڼԪǰ,ͼ3ʾ.
ԪֵܺͼΪֵ,ԪĳҲԤȶ.ֵһԪıʾޣrԪĳ,2r-1ʱ,򽫸ԪΪȫ־ȫ㣩,һµԪ.ֳֵԪĹͬʾޣ22r-1,ٷһµԪ.,ֱҪΪֹ.ʶĵ1ڱʾĲΣʶԪظ.
ΪȷʶеĳԪصֵ,,ԪصǰrλrԪĳȣ,Ԫȫ־,rλ,ֱҵһδȫ־ԪΪֹ,ѶԪֵӾ͵õֵNumȻ,mλmǼԪĳȣ,õԪֵNC,nλnǱ뵥Ԫĳȣ,õ뵥ԪֵNUô,ԪصֵΪ2n-1(2m-1(Num1)NC1)NU.пԱʾĲͬԪֵĿΪk2r-12m-12n-1kԪĸ.ŻʶҲܽϺõʶĸ.
3 
Ϊ˺ۻλʶԡĽʶԺŻʶԵ,ѡͳʶΪԱȲԶ,ͨģ˴ܲ.ڷԽʱ,Ƿ,λʶԡĽʶԺŻʶԵܴ¹ɣ
(1) ߵĿռ俪ʵݼ,νṹϼʱ,ֵݼƲԣ
(2) ߵʱ俪ʵ,ȽС.
ڴ,ҪܶԱȲԶ󡢻ԼλʶԵĶԱȲԽ.
3.1 ԱȲԶ󼰻
ѡһֻĴͳΪԱȲԶ,ֻĴͳPRIMAϵͳ4ʵ.Ļ˼ǣƿʾ,ƿʶָƿָ롢ָ1ƿָ롢ָǰһֵƿָ롢ָһֵƿָϢÿıʶͨһηģĸӦڶ.
Cʵ˴ͳԺͻλʶ,л586΢166Mhz,32MBڴ棩.ڲԵνṹȡΪ30.ڻλʶ,뵥ԪĳȾȡ8λ.ȡ100 000нƽֵΪԽ.
3.2 Խ
ݰٴ洢ռ;ڻøʶʱ俪;ж-ϵʱ俪,ҳ߲ķǹͬȵʱ俪.Խ£
. 洢ռ
Ϊ˱ڱȽ,ٶÿУ28-1.ڴͳ,ڱʶά֮ϵĴ洢ռСǹ̶,Ĳ޹,ÿ20ֽ.ڻλʶ,ıʶ2ֽ,ÿһ,ʶһУ1ֽڣ.ͼ4ʾ,С19ʱ,λʶԵʶռõĴ洢ռڴͳԵƿռõĴ洢ռ䣻δ19ʱ,λʶԵʶռõĴ洢ռڴͳԵƿռõĴ洢ռ.

ͼ4洢ռ
. øʶʱ俪
ڴͳ,Ϊ˵õĳʶΪtidĸʶ,,ҵtidӦƿ飻Ȼ,ͨϵָҵƿ,õʶ.ڻλʶ,,1,õLȻζģL1,͵õ˸ʶ.ֲԶ,øʶʱ俪ͼ5ʾ޹.

ͼ5øʶʱ俪
. ж-ϵʱ俪
ڴͳ,Եϵķж֮-ϵ,ʱ俪֮Ĳβй.ڻλʶ,ʶĵ2пʼ,ζȡÿֽڲбȽ,Ӷж֮-ϵ.ʱ俪֮Ĳβ޹,̱ʶй.Ϊ˱ڱȽ,ȡĲξΪ21,ͨı丸Ĳ۲ʱ俪ı仯ͼ6ʾ.ŸĲ,ڴͳ,·,ʱ俪٣ڻλʶ,Ƚϵֽ,ʱ俪.

ͼ6ж-ϵʱ俪
. ҳ߲ķǹͬȵʱ俪
ڴͳУT1T2ĲηֱΪL1L2,L1>L2,,ͨƿеָ,ҵT1λڲL2ϵA1Ȼ,T2A1ͬʱָԵ,¼ÿ,ֱҵ1ͬ,ô,ϴ߲ķǹͬ,ʱ俪ǹ֮ͬĲβй.ڻλʶ,ʶĵ2пʼ,ζȡÿֽڲбȽ,ֱҵ1ֽͬ,Ӷҳ߲ķǹͬ,ʱ俪ǹͬȵĲй.Ϊ˱ڱȽ,ȡĲξΪ21,ͨı߲ķǹͬȵĲ۲ʱ俪ı仯ͼ7ʾ.߲ķǹͬȵĲ,ڴͳ,·,ʱ俪٣ڻλʶ,Ƚϵֽ,ʱ俪.

ͼ7ҳ߲ķǹͬȵʱ俪
4 С 
Ƕģ͵ִЧ,оʶ,оʶԵĻ,һϵʵЧʶԣλʶԡĽʶԺŻʶ.ǽνṹйϢЧؼ¼ʶ,봫ͳԵĶԱȲԽ,Ǽ˴洢ռʹʱЧ,ܹõʶĸ,ǶЧ.λʶ,ĽʶԺŻʶܹЧô洢ռ,ǵʱ俪,ϡʱ任ȡռ䡱Ĺ.
λʶԾʵƵĿͻ/ݿϵͳKDOODB,ΪKDOODBϵͳЧ춨˼ʵĻ.
,Ů,1971,ʿ,ҪоΪݿ,㣬зֲ,.¾,1971,ʿ,ҪоΪݿ,зֲ,ʵ.,1926,,ʿʦ,ҪоΪݿ,ʵ,ܻϵṹ,зֲ.
ͨѶϵ:,ɳ410073,ɳѧԺϵֲصʵ
ߵλɳѧԺֲصʵҡɳ410073
ο
1Harder T, Rothermel K. Concurrency control issues in nested transactions. Journal of Very Large Databases, 1993,2(1):3342
2Catriel Beeri, Bernstein P A, Goodman N. A model for concurrency in nested transaction systems. Journal of the Association for Computing Machinery, 1989,36(2):230269
3,¾,.ݿϵͳе.ѧ,1996,23(6):5962
(Wang Yi-jie, Wang Yong-jun, Hu Shou-ren. Transaction management in object-oriented database management systems. Computer Science, 1996,23(6):5962)
4Harder T, Meyer-Wegener K, Mitschang B et al. PRIMAa DBMS prototype supporting engineering applications. In: Agrawal R, Bell D eds. Proceedings of the 13th International Conference on Very Large Data Bases. San Mateo, CA: Morgan Kaufman Publishers, Inc., 1987. 4759
1998-05-05յԭ 
1998-08-05յ޸ĸ
