A concurrency control mechanism based on extendible hashing for main memory database systems

ABSTRACT

A non-preemptive deadlock-free concurrency control mechanism based on extendible hashing has been presented for main memory database system. The algorithm makes use of the verification process of the optimistic concurrency control algorithm and two-phase locking policy to manage concurrent operations on sharable data. We also present a comparison of our algorithm with other two-phase locking mechanisms and show that our algorithm is more robust, easier to implement and provides a higher degree of concurrency than other algorithms on extendible hash file.

REFERENCES

• DEWI84: David J DeWitt , Randy H Katz , Frank Olken , Leonard D Shapiro , Michael R Stonebraker , David Wood, Implementation techniques for main memory database systems, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• ELLI82: Ellis, C.S, "Extendible Hashing for Concurrent Operations and Distributed Data", ACM SIGMOD 1982.
• ESWA76: 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]
• FAGI79: Ronald Fagin , Jurg Nievergelt , Nicholas Pippenger , H. Raymond Strong, Extendible hashing—a fast access method for dynamic files, ACM Transactions on Database Systems (TODS), v.4 n.3, p.315-344, Sept. 1979 [doi>10.1145/320083.320092]
• HSU85: Meichun Hsu , Wei-Pang Yang, Concurrent Operations in Extendible Hashing, Proceedings of the 12th International Conference on Very Large Data Bases, p.241-247, August 25-28, 1986
• KUMA88: Kumar, V., "A Superior Deadlock-Avoidence Two-Phase Locking Algorithm and its Performance" Information Sciences, 1989.
• KUNG81: H. T. Kung , John T. Robinson, On optimistic methods for concurrency control, ACM Transactions on Database Systems (TODS), v.6 n.2, p.213-226, June 1981 [doi>10.1145/319566.319567]
• LEHM86: Tobin Jon Lehman, Design and performance evaluation of a main memory relational database system (t tree), 1986
• LEHM81: 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]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
          Subjects: Deadlock avoidance

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Deadlocks

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Number-theoretic computations (e.g., factoring, primality testing)

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Distributed databases; Concurrency

General Terms:
Algorithms, Design, Performance, Verification