Concurrency control of nested transactions accessing B-trees

ABSTRACT

This paper presents a concurrency control algorithm for nested transactions accessing B-trees. It combines the idea of B-link tree with that of resilient 2-phase locking [Mos85b]. The I/O automaton model is used in the specification and proofs of correctness of the system. We define “strongly-serially correct” schedules and use this property as our correctness criterion.

REFERENCES

• Ell87: Carla Schlatter Ellis, Concurrency in linear hashing, ACM Transactions on Database Systems (TODS), v.12 n.2, p.195-217, June 1987 [doi>10.1145/22952.22954]
• FLM87: A. Fekete , N. Lynch , M. Merrit , W. Weihl, Nested transactions and read-write locking, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.97-111, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28669]
• FLM88: A. Fekete, N. Lynch, M. Merritt and W. Weihl, Commutativity-Based Locking for Nested Transactions, Book draft, Aug. 1988.
• GoL87: Kenneth J. Goldman , Nancy A. Lynch, Quorum consensus in nested transaction systems, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.27-41, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41843]
• GoS85: Nathan Goodman , Dennis Shasha, Semantically-based concurrancy control for search structures, Proceedings of the fourth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.8-19, March 25-27, 1985, Portland, Oregon, United States [doi>10.1145/325405.325407]
• Had88: Vassos Hadzilacos, A theory of reliability in database systems, Journal of the ACM (JACM), v.35 n.1, p.121-145, Jan. 1988 [doi>10.1145/42267.42272]
• HaH88: Thanasis Hadzilacos , Vassos Hadzilacos, Transaction synchronisation in object bases, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.193-200, March 1988, Austin, Texas, United States [doi>10.1145/308386.308438]
• IKM87: Toshihide Ibaraki , Tiko Kameda , Toshimi Minoura, Serializability with constraints, ACM Transactions on Database Systems (TODS), v.12 n.3, p.429-452, Sept. 1987 [doi>10.1145/27629.214284]
• KuL80: H. T. Kung , Philip L. Lehman, Concurrent manipulation of binary search trees, ACM Transactions on Database Systems (TODS), v.5 n.3, p.354-382, Sept. 1980 [doi>10.1145/320613.320619]
• LeY81: 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]
• LyM86: N. A. Lynch , M. Merritt, INTRODUCTION TO THE THEORY OF NESTED TRANSACTIONS, Massachusetts Institute of Technology, Cambridge, MA, 1986
• Mos85a: E. B. Moss, NESTED TRANSACTIONS: AN APPROACH TO RELIABLE DISTRIBUTED COMPUTING, Massachusetts Institute of Technology, Cambridge, MA, 1981
• Mos85b: J. E.B. Moss, Nested transactions: an approach to reliable distributed computing, Massachusetts Institute of Technology, Cambridge, MA, 1985
• Sag85: Yehoshua Sagiv, Concurrent operations on B-trees with overtaking, Proceedings of the fourth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.28-37, March 25-27, 1985, Portland, Oregon, United States [doi>10.1145/325405.325409]
• ShG88: Dennis Shasha , Nathan Goodman, Concurrent search structure algorithms, ACM Transactions on Database Systems (TODS), v.13 n.1, p.53-90, March 1988 [doi>10.1145/42201.42204]
• Vid87: K. Vidyasankar, Serializability of Nested Transactions, Technical Report #8702, Dept. of Computer Science, Memorial University of Newfoundland, May 1987.
• VLS87: K. Vidyasankar, W. Litwin and Y. Sagiv, Concurrency and Trie Hashing , Technical Report #8704, Dept. Comp. So., Memorial U. of New Foundland, 1987.
• Wed74: H. Wedekind, On the Selection of Access Paths in a Database System, in Data Base Management, J. W. Klimbie and K. L. Koffeman (ed.), North Holland, Amsterdan, 1974, 385-397.

INDEX TERMS

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

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees
  E.2 DATA STORAGE REPRESENTATIONS
      Subjects: Hash-table representations

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Automata (e.g., finite, push-down, resource-bounded)
  F.3 LOGICS AND MEANINGS OF PROGRAMS

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

General Terms:
Algorithms, Languages, Theory