A concurrency control theory for nested transactions (Preliminary Report)

ABSTRACT

Concurrency control is the activity of synchronizing transactions that access shared data. A concurrency control algorithm is regarded as correct if it ensures that any interleaved execution of transactions is equivalent to a serial one. Such executions are called serializable. Serializability theory provides a method for modelling and analyzing the correctness of concurrency control algorithms [BSW, Pa]. The concept of nested transaction has recently received much attention [GR], [Mo]. In a nested transaction model, each transaction can invoke sub- transactions, which can invoke sub-subtransactions, and so on. The natural modelling concept is the tree log. The leaves of a tree log are atomic operations executed by the underlying system. Internal nodes are operations (as seen by their parents) implemented as transactions (as seen by their children). Nodes are related by a partial order <, where x<y means x executes before y [La].

REFERENCES

• 1: Attar, R., P.A. Bernstein, and N. Goodman, "Site initialization, Recovery, and Back-up in a Distributed Database Systems," Proc. 6th Berkeley Workshop, Feb. 1982, pp. 185-202.
• 2: R. Bayer , H. Heller , A. Reiser, Parallelism and recovery in database systems, ACM Transactions on Database Systems (TODS), v.5 n.2, p.139-156, June 1980 [doi>10.1145/320141.320146]
• 3: Philip A. Bernstein , Nathan Goodman, Concurrency Control in Distributed Database Systems, ACM Computing Surveys (CSUR), v.13 n.2, p.185-221, June 1981 [doi>10.1145/356842.356846]
• 4: Philip A. Bernstein , Nathan Goodman, A Sophisticate's Introduction to Distributed Concurrency Control (Invited Paper), Proceedings of the 8th International Conference on Very Large Data Bases, p.62-76, September 08-10, 1982
• 5: Bernstein, P.A., and N. Goodman, "Multi-version Concurrency Control-Theory and Algorithms," Proc. of the ACM SIGACT-SIGOPS Conf. on Principles of Distributed Computation, August 1982, Ottawa.
• 6: Bernstein, P.A., N. Goodman, and M.Y. Lai, "Laying Phantoms to Rest (by Understanding the Interactions Between Schedulers and Translators in a Database System)," Proc. 1981 IEEE COMPSAC Conf., Oct. 1981.
• 7: Bernstein, P.A., D.W. Shipman, and W.S. Wong, "Formal Aspects of Serializability in Database Concurrency Control," IEEE Trans. on Software Engineering, SE-5, 3 (May 1979), 203-215.
• 8: Arvola Chan , Stephen Fox , Wen-Te K. Lin , Anil Nori , Daniel R. Ries, The implementation of an integrated concurrency control and recovery scheme, Proceedings of the 1982 ACM SIGMOD international conference on Management of data, June 02-04, 1982, Orlando, Florida [doi>10.1145/582353.582386]
• 9: Dubourdieu, D.J., "Implementation of Distributed Transactions," Proc. 1982 Berkeley Workshop on Distributed Data Management and Computer Networks, pp. 81-94.
• 10: K. P. Eswaran , J. N. Gray , R. A. Lorie , I. L. Traiger, The notions of consistency and predicate locks in a database system, Communications of the ACM, v.19 n.11, p.624-633, Nov. 1976 [doi>10.1145/360363.360369]
• 11: Fischer, J.J., Griffeth, N.D., and N.A. Lynch, "Global States of a Distributed System," Proc. 1st IEEE Annual Symp. on Reliability in Distributed Software and Database Systems, 1981, pp. 31-38.
• 12: Gray, J., "The Transaction Concept: Virtues and Limitations," Proc. 7th International Conf. on Very Large Data Bases, Cannes, Sept. 1981, pp. 144-154.
• 13: Kwong, Y.S., and Wood, D., "A New Method for Concurrency in B-trees," IEEE Trans. Softw. Eng. SE-8, 3 (May 1982), pp. 211-222.
• 14: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 15: Philip L. Lehman , s. Bing Yao, Efficient locking for concurrent operations on B-trees, ACM Transactions on Database Systems (TODS), v.6 n.4, p.650-670, Dec. 1981 [doi>10.1145/319628.319663]
• 16: Liskov, B., and W. Weihl, "Specification and Implementation of Resilient, Atomic Data Types," Manuscript, MIT Laboratory of Computer Sciences, 1982.
• 17: Nancy A. Lynch, Concurrency control for resilient nested transactions, Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systems, March 21-23, 1983, Atlanta, Georgia [doi>10.1145/588058.588080]
• 18: Manna, Z., and A. Pnueli, book in preparation, 1983.
• 19: Moss, T.E.B., "Nested Transactions: An Approach to Reliable Distributed Computing," Ph.D. Thesis, MIT Laboratory for Computer Science, 1981.
• 20: Christos H. Papadimitriou, The serializability of concurrent database updates, Journal of the ACM (JACM), v.26 n.4, p.631-653, Oct. 1979 [doi>10.1145/322154.322158]
• 21: Christos H. Papadimitriou , Paris C. Kanellakis, On concurrency control by multiple versions, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California [doi>10.1145/588111.588125]
• 22: Daniel J. Rosenkrantz , Richard E. Stearns , Philip M. Lewis, II, System level concurrency control for distributed database systems, ACM Transactions on Database Systems (TODS), v.3 n.2, p.178-198, June 1978 [doi>10.1145/320251.320260]
• 23: D. P. Reed, NAMING AND SYNCHRONIZATION IN A DECENTRALIZED COMPUTER SYSTEM, Massachusetts Institute of Technology, Cambridge, MA, 1978
• 24: Abraham Silberschatz , Zvi Kedem, Consistency in Hierarchical Database Systems, Journal of the ACM (JACM), v.27 n.1, p.72-80, Jan. 1980 [doi>10.1145/322169.322176]
• 25: Schwartz, P., and Spector, A., "Synchronizing Shared Abstract Types," Tech. Rep. CMU-CS-82-128, CMU Dept. of Computer Science, Sept. 1982.
• 26: Stearns, R.E., P.M. Lewis II, and D.J. Rosenkrantz, "Concurrency Controls for Data-base Systems," Proc. 17th Symp. on Foundations of Computer Science, IEEE, N.Y., 1976, pp. 19-32.
• 27: Richard E. Stearns , Daniel J. Rosenkrantz, Distributed database concurrency controls using before-values, Proceedings of the 1981 ACM SIGMOD international conference on Management of data, April 29-May 01, 1981, Ann Arbor, Michigan [doi>10.1145/582318.582330]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Transaction processing

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design

General Terms:
Design, Theory