摘要
近十年,计算技术和无线通讯技术的发展与结合使得一种全新的计算模式——移动计算成为现实。研究支持移动计算环境的分布式数据库技术,也就是移动数据库技术,已成为目前分布式数据库研究的一个重要方向。移动数据库的研究主要包括复制与缓存技术、位置管理、查询及其优化技术、数据广播、安全机制、移动事务处理以及人机界面技术,其中移动事务处理技术是移动数据库关键技术之一,而并发控制又是移动事务处理技术的重要方面。
在已有的传统的并发控制中,如两阶段锁协议、乐观并发控制以及时戳排序法在设置锁及冲突检测上需要大量开销,不适合移动环境。本文以二级复制为基础,对传统的移动数据库的系统结构进行了改进,提出了一种提前提交并发控制的系统结构。该系统结构分为两部分:固定网络部分和移动网络部分。固定网络部分,即移动数据库系统中的服务器部分,对应着二级复制技术中的第一级复制“服务器级复制”。为了提高该级复制的效率,对固定网络中的服务器运用了P2P技术和DRG策略。移动网络部分,即系统中的移动结点部分,该部分中的移动客户端通过无线网络跟最近的服务器通信,来保证客户端所访问的数据与服务器中的数据的一致性,它对应着二级复制中的第二级复制。
其中,第二级复制采用的是提前提交的并发控制策略。该策略只允许部分的移动客户端在断接时进行本地更新,而其他的移动客户端必须等到重新连接时在服务器端进行更新。而哪些移动客户端的更新是可以在本地进行的,则是根据该客户端的更新量是否在某个范围内来决定,即该策略通过选取MC上的数据单元允许变化范围的最大值(用λ表示),将移动事务的更新分为提前提交事务和请求事务。提前提交事务可以在链路断接时在MC本地完成更新,当链路重新连接时,在服务器上只作为基础事务更新。而请求事务则不能在本地更新,必须等到链路重新连接时,在服务器上更新。
通过对DRG策略和提前提交策略的模拟仿真实验表明,这些策略的应用可以明显减少更新事务的等待时间,节省大量的网络资源,降低系统在重连接时进行冲突检测和同步处理的网络代价。
In last ten years, the improvements and integration of computing technology and wireless communication made a new computing mode, mobile computing, become reality. The research on database management in mobile environment, which is known as mobile computing, has become a new hot topic in database reseach society. Research mainly focuses on replication and caching, location management, query optimizing, data broadcast, security, mobile transaction processing and human-machine interface technologies. Among these topics, research of mobile transaction processing is one of the key technologies, while the study of concurrency control is the most important part of mobile transaction processing.
Among the traditional schemes of concurrency control, for instance 2PL, the optimistic concurrency control scheme, the time-compositor concurrency control scheme, are all cost much in the way of setting lock and examining the conflicts. So these methods don't adapt to the mobile environment. In this paper, we study a new model of mobile database which is based of the two-tier replication method and the classical model of the mobile database. This new model includes two parts: the fixed network and the mobile network. The servers of the mobile database system compose the fixed network. This corresponds the first replication of the two-tier replication, the replication of the servers. To improve the efficiency of the first replication, we use the technology of P2P and the DRG Also, the mobile network is consitituded of the mobile clients. The mobile clients communicate with the nearest server through the wireless network. This is the second replication of the two-tier replication method.
The second replication uses the pre-committed concurrency control scheme. This scheme allows some of the mobile clients to pre-commit at the local place when the link is disconnected, but the other of MCs must wait until the link is re-connected. To confirm which MCs can pre-commit, we should choose the value of the amount of change that can occur on the replica at each MC (we keep it asλ). If the transactions change the data value by at mostλin a MC, they are called pre-committed transactions and can be free to commit. Otherwise, if the transactions change the data value more thanλ, they are called request transactions and must commit at the server.
Experiment results of the DRG and the pre-committed scheme indicate that the methods can reduces transactions' commit time and also help to reduce the number of rejections, which could arise due to the BT not being able to commit.
引文
1.D.Agrawal and A.EI Abbadi:Using Reconfiguration For Efficient Management of Replicated Data.In:Knowledge and Data Engineering,2001.786-801
2.D.Agrawal and A.EI Abbadi:The Tree Quorum technique:An Efficient Approach for Managing Replicated Data.In:Very Large Data Bases,2002.243-254
3.P.A.Bemstein,V.Hadzilaeos,and N.Goodman:Concurrency Control and Recovery in Database System.In:Addison-Wesley,1996.279-301
4.B.Bhargava:Concurrency Control in Database System.In:IEEE Trans.Knowledge and Data Engineering,2001.3-16.
5.Budiarto,S.Noshio,and M.Tsukamoto:Data Management Issues in Mobile and Peer -to-Peer Environment.In:Journal Data and Knowledge Engineering,2002.183-204
6.S.Y.Cheung,M.H.Ammar,and M.Ahmad:The Gird Technique:A High Performance Schema for Maintaining Replicated Data.In:IEEE Trans.Knowledge and Data Engineering,2000.582-592.
7.J.Holliday,R.Steinke,D.Agrawal and A.EI Abbadi:Disconnection modes for mobile database.In:Journal of Wireless Network,2002.391-402.
8.S.Jajodia and D.Mutehles:Dynamic Voting Algorithms for Maintaining the Consistency of a Replicated Database[M].In:ACM Trans.Database System,1999.230-280.
9.J.Holliday,R.Steinke,D.Agrawal and A.EI Abbadi:Epidemic Algorithms for Replicated Databases.In:Knowledge and Data Engineering,2003.1218-1238.
10.M.Maekawa:A √ n Algorithms for Mutual Exclusion in Decentralized System.In:ACM Trans.Computer System,1999.145-159.
11.刘云生.现代数据库技术[M].国防工业出版社,2001.3.
12.J.F.Pairs and D.E.Long:Efficient Dynamic Voting Algorithms.In:Fourth IEEE Int'l Conf.1990.268-275.
13.林承军、李石君。移动数据库中数据广播与数据更新并发控制的数据一致性维护[J].计算机工程与应用,2004,4(1):182-183
14.曾斌、徐帆江、李之棠.数据库广播的并发控制算法研究[J].计算机工程与应用,2002,9(4):166-167
15.卢彦、党德鹏.广播环境中的Q可串行化实时并发控制[J].计算机科 学,2006,33(6):2-3
16.丁治明、孟小峰、王珊.复制的移动数据库系统事务级同步处理策略[J].软件学报,2002,13(2):258-265
17.O.Wolfsort,S.Jajodia,and Y.Huang:An Adaptive Data Replicated Algorithm.In:ACM Transactions on Database System.2002.255-314.
18.Daniel Barbara:Mobile Computing and Database-A survey.In:IEEE TKDE.1999.268-275.1
9.M.H.Dunham,A.Helal:Mobile Computing and Databases:Anything New?:In:SIGMOD Ree.,24(4),Dee.2000.264-275
20.Evaggelia Pitroura and Bharat Bhargava:Revising transaction concepts for Mobile Computing.In:Workshop on Mobile Computing System and Application.2000.223-225
21.S.Aeharya,M.Franklin,S.Zdonik:Dessemination-based Data Delivery Using Broadcast Disks.In:IEEE Personal Communications.2001.225-293
22.Evaggelia Pitroura and Bharat Bhargava:Maintaining Consistency of Data in Mobile Distributed Environment.In:Proceedings of 15th ICDCS,Vancouver,Canada.1999.378-398
23.Chrysanthis,P.K.:Transaction processing in Mobile Computing Environment.In:IEEE workshop on Advances in Parallel and Distributed Sys.2000.245-265
24.J.Gray,P.Helland,P.E.O'Neil,D.Shasha:The Dangers of Replication and a Solution.In:SIGMOD Conf.2001.336-366
25.Daniel Barbara:Certification Reports:Supporting Transactions in Wireless Systems [M].In:ICDCS.1997.265-274
26.Jin Jing,Omran Bukhres,Ahmed Elmagarmid:Distributed Lock management for Mobile transaction.In:the proceedings of ICDCS.2000.298-310
27.S.Madria,Bharat Bhargava:A transaction model for Mobile computing.In:Proc.of Int.Database Eng.And Appn.Syrup.2003.315-330
28.Jiang HF,Lu HJ,Wang W,Yu JX.Path materialization revisited:An efficient storage model for XML data.In:Zhou XF,ed.Proe.of the 13th Australasian Database Conf.on Database Technologies 2002(ADC).Melbourne:Australian Computer Society,2002.85-94.
29.王文方,王刚,刘景.对等网络维护数据副本一致性的乐观复制技术研究[J].计算机工程,2006.32(20):615-620
30.D.Walbom and P.K.Chrysanthis.Pro-motion:Management of mobile transactions. In:Proceedings of the 11th ACM Symposium on Applied Computing.2002.615-630.
31.M.Faiz and A.Zaslavsky:Database Replica Management Strategies in Multi-database Systems with Mobile Hosts.In:Proceedings of the 6~(th)International Hong Kong Computer Society Database Workshop.2000.622-633
32.P.Reiher,J.Heidemann,D.Rather,G.Skinner,and G.Popek:Resolving File Conflicts in the Focus File System.In:Proceedings of the Summer USENIX Conference.1999.183-195
33.Ziyad Tariq Abdul-Mehdi,Ali Bin Mamat,Hamidah lbrahim and Mustafa.M.Dirs:Check-Out Planned Disconnection Mode with New Transaction Management in Mobile Database.In:proceeding of M2USIC 2005 MMU International Symposium on Information and Communication Technologies.2005.167-176
34.Milo T,Suciu D.Index structures for path expressions.In:Beeri C,Buneman P,eds.Proc.of the 1999 Int'l Conf.on Database Theory(ICDT).LNCS 1540,Jerusalem:Springer-Veflag,1999.277-295.
35.Zhang C,Naughton J,DeWitt D.On supporting containment queries in relational database management systems.In:Aref WG,ed.Proceedings of the 2001 ACM SIGMOD Int'l Conf.on Management of Data(SIGMOD).Santa Barbara:ACM Press,2001.425-436.
36.S.Madria and B.Bhargava:Distributed and Parallel Database.In:proceeding of the ACM SIGMOD Conference,Madison,Wisconsin,2001,127-160
37.E.Pitoura and P.Chrysanthis:Distributed Computing System.In:Proc.of the ACM SIGMOD Int'l Conf.on Management of Data(SIGMOD).Baltimore:ACM Press,2005.432-439
38.J.Shanmugasundaram,A.Nithrakashyap and R.Sivasankaran:Management of Data.In:Proceedings of the 2002 ACM symposium on Applied computing,March Madrid,Spain,2002:11-14.
39.何新贵,唐常杰等.特种数据库技术[M].科学出版社,2000.32(20):635-640
40.汤庸等.时态知识和时态数据的统一模型研究[M].软件学报,2003:74-78.
41.M.Franklin,M.Carey and M.Livny:Database System.In:Proc.Of the 11~(th)International Conference on Database and Expert Systems Applications(DEXA2000),LNCS,September 2000.615-630.
42.F.Wang,X.Zhou and C.Zaaiolo.Build Efficient Transaction-Time Temporal DataBase Systems on Relational Databases,Pro.of the 30~(th)VLDB Conference,2004.678-701
43.T.lmielinski,B.R.Badrinath:Mobile Wireless Computing Challenges in Data Management.In:ACM 37(10).1999.623-701
44.F.Grandi and F.Mandreoli and P.Tiberio and M.Bergonzini:A Temporal Data Model and Management System for Normative Texts.In:WIDM.2003.29-36
45.王文琴,费贤举,鞠时光.基于数据复制技术实现移动数据同步[M].计算机应用.2006,26(7):263-279.4
6.E.Pitoura,B.Bhargava:Maintaining Consistency of Datain Mobile Distributed Environment.In:Proceedings of the15th International Conference on Distributed Computing Systems.2001.401-413
47.H.W.Leung:Concurrency Control for Data Broadcasts in Mobile Computing Systems.In:Department of Computer Science,City University of Hong Kong.2001.201-212
48.Chien SY,Vagena Z,Zhang D,Tsotras VJ,Zaniolo C.Efficient Structural Joins on Indexed XML Documents.In:Bressan S,Chaudhri AB,Lee ML,Yu JX,Lacroix Z,eds.Proc.of the 28th Int'l Conf.on Very Large Data Bases(VLDB).LNCS 2590,Hong Kong:Morgan Kaufmann,2002.263-274.
49.Silberstein A,He H,Yi K,Yang J.BOXes:Efficient maintenance of order-based labeling for dynamic XML data.In:Stephanie Kawada,ed.Proc.of the 21st Int'l Conf.on Data Engineering(ICDE).Tokyo:IEEE Computer Society,2005.285-296.
50.Cohen E,Kaplan H,Milo T.Labeling dynamic XML trees.In:Popa L,ed.Proc.of the 21st ACM SIGACT-SIGMOD-SIGART Symp.on Principles of Database Systems(PODS).Madison:ACM Press,2002.271-281.
51.Han ZM,Fu NY.Efficiently coding and querying XML document.In:Bhalla S,ed.Proc.of the 4th Int'l Workshop on Databases in Networked Information Systems (DNIS).LNCS 3433,Springer-Verlag,2005.54-69.
52.Kaushik R,Bohannon P,Naughton JF,Korth HF.Covering indexes for branching path queries.In:Franklin MJ,Moon B,Ailamaki A,eds.Proc.of the 2002 ACM SIGMOD Int'l Conf.on Management of Data(SIGMOD).Madison:ACM Press,2002.133-144.
53.赵畅.基于移动数据库的事务处理模型的研究[J].计算机工程.2006(21):141-145.