Partitioned Two-Phase Locking.

@article{DBLP:journals/tods/HsuC86,
  author    = {Meichun Hsu and
               Arvola Chan},
  title     = {Partitioned Two-Phase Locking},
  journal   = {ACM Trans. Database Syst.},
  volume    = {11},
  number    = {4},
  year      = {1986},
  pages     = {431-446},
  ee        = {http://doi.acm.org/10.1145/7239.7477, db/journals/tods/HsuC86.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

In a large integrated database, there often exists an "information hierarchy," where both raw data and derived data are stored and used together. Therefore, among update transactions, there will often be some that perform only read accesses from a certain (i.e., the "raw" data) portion of the database and write into another (i.e., the "derived" data) portion. A conventional concurrency control algorithm would have treated such transactions as regular update transactions and subjected them to the usual protocols for synchronizing update transactions. In this paper such transactions are examined more closely. The purpose is to devise concurrency control methods that allow the computation of derived information to proceed without interfering with the updating of raw data.

The first part of the paper presents a proof method for correctness of concurrency control algorithms in a hierarchically decomposed database. The proof method provides a framework for understanding the intricacies in dealing with hierarchically decomposed databases. The second part of the paper is an application of the proof method to show the correctness of a two-phase-locking-based algorithm, called partitioned two-phase locking, for hierarchically decomposed databases. This algorithm is a natural extension to the Version Pool method proposed previously in the literature.

Copyright © 1986 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Joint ACM SIGMOD / IEEE Computer Society Anthology

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/An3-1 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD2 or /dvd

References

[1]

Rudolf Bayer, Hans Heller, Angelika Reiser: Parallelism and Recovery in Database Systems. ACM Trans. Database Syst. 5(2): 139-156(1980) BibTeX

[2]

Philip A. Bernstein, Nathan Goodman: Concurrency Control in Distributed Database Systems. ACM Comput. Surv. 13(2): 185-221(1981) BibTeX

[3]

Philip A. Bernstein, Nathan Goodman: Multiversion Concurrency Control - Theory and Algorithms. ACM Trans. Database Syst. 8(4): 465-483(1983) BibTeX

[4]

Philip A. Bernstein, David W. Shipman, James B. Rothnie Jr.: Concurrency Control in a System for Distributed Databases (SDD-1). ACM Trans. Database Syst. 5(1): 18-51(1980) BibTeX

[5]

Michael J. Carey, Waleed A. Muhanna: The Performance of Multiversion Concurrency Control Algorithms. ACM Trans. Comput. Syst. 4(4): 338-378(1986) BibTeX

[6]

Arvola Chan, Robert Gray: Implementing Distributed Read-Only Transactions. IEEE Trans. Software Eng. 11(2): 205-212(1985) BibTeX

[7]

Arvola Chan, Umeshwar Dayal, Meichun Hsu: Providing Database Management Capabilities for Mission Critical Applications. HPTS 1985: 0- BibTeX

[8]

Arvola Chan, Stephen Fox, Wen-Te K. Lin, Anil Nori, Daniel R. Ries: The Implementation of an Integrated Concurrency Control and Recovery Scheme. SIGMOD Conference 1982: 184-191 BibTeX

[9]

Kapali P. Eswaran, Jim Gray, Raymond A. Lorie, Irving L. Traiger: The Notions of Consistency and Predicate Locks in a Database System. Commun. ACM 19(11): 624-633(1976) BibTeX

[10]

Hector Garcia-Molina, Gio Wiederhold: Read-Only Transactions in a Distributed Database. ACM Trans. Database Syst. 7(2): 209-234(1982) BibTeX

[11]

Jim Gray: Notes on Data Base Operating Systems. Advanced Course: Operating Systems 1978: 393-481 BibTeX

[12]

...

[13]

...

[14]

Meichun Hsu, Stuart E. Madnick: Hierarchical Database Decomposition - A Technique for Database Concurrency Control. PODS 1983: 182-191 BibTeX

[15]

Zvi M. Kedem, Abraham Silberschatz: Non-Two-Phase Locking Protocols with Shared and Exclusive Locks. VLDB 1980: 309-317 BibTeX

[16]

Zvi M. Kedem, Abraham Silberschatz: Locking Protocols: From Exclusive to Shared Locks. J. ACM 30(4): 787-804(1983) BibTeX

[17]

H. T. Kung, Christos H. Papadimitriou: An Optimality Theory of Concurrency Control for Databases. SIGMOD Conference 1979: 116-126 BibTeX

[18]

Leslie Lamport: Time, Clocks, and the Ordering of Events in a Distributed System. Commun. ACM 21(7): 558-565(1978) BibTeX

[19]

Christos H. Papadimitriou, Paris C. Kanellakis: On Concurrency Control by Multiple Versions. ACM Trans. Database Syst. 9(1): 89-99(1984) BibTeX

[20]

Abraham Silberschatz, Zvi M. Kedem: Consistency in Hierarchical Database Systems. J. ACM 27(1): 72-80(1980) BibTeX

[21]

Abraham Silberschatz, Zvi M. Kedem: A Family of Locking Protocols for Database Systems that Are Modeled by Directed Graphs. IEEE Trans. Software Eng. 8(6): 558-562(1982) BibTeX

[22]

Richard Edwin Stearns, Daniel J. Rosenkrantz: Distributed Database Concurrency Controls Using Before-Values. SIGMOD Conference 1981: 74-83 BibTeX

Referenced by

1. Dennis Shasha, François Llirbat, Eric Simon, Patrick Valduriez: Transaction Chopping: Algorithms and Performance Studies. ACM Trans. Database Syst. 20(3): 325-363(1995)
2. Paul Ammann, Vijayalakshmi Atluri, Sushil Jajodia: The Partitioned Synchronization Rule for Planar Extendible Partial Orders. IEEE Trans. Knowl. Data Eng. 7(5): 797-808(1995)
3. Dennis Shasha, Eric Simon, Patrick Valduriez: Simple Rational Guidance for Chopping Up Transactions. SIGMOD Conference 1992: 298-307
4. William Perrizo, Min Luo, Donald A. Varvel: Ordering Accesses to Improving Transaction Processing Performance. ICDE 1988: 58-63