ACM SIGMOD Anthology TODS dblp.uni-trier.de

Semantics-Based Concurrency Control: Beyond Commutativity.

B. R. Badrinath, Krithi Ramamritham: Semantics-Based Concurrency Control: Beyond Commutativity. ACM Trans. Database Syst. 17(1): 163-199(1992)
@article{DBLP:journals/tods/BadrinathR92,
  author    = {B. R. Badrinath and
               Krithi Ramamritham},
  title     = {Semantics-Based Concurrency Control: Beyond Commutativity},
  journal   = {ACM Trans. Database Syst.},
  volume    = {17},
  number    = {1},
  year      = {1992},
  pages     = {163-199},
  ee        = {http://doi.acm.org/10.1145/128765.128771, db/journals/tods/BadrinathR92.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

The concurrency of transactions executing on atomic data types can be enhanced through the use of semantic information about operations defined on these types. Hitherto, commutativity of operations has been exploited to provide enchanced concurrency while avoiding cascading aborts. We have identified a property known as recoverability which can be used to decrease the delay involved in processing noncommuting operations while still avoiding cascading aborts. When an invoked operation is recoverable with respect to an uncommitted operation, the invoked operation can be executed by forcing a commit dependency between the invoked operation and the uncommitted operation; the transaction invoking the operation will not have to wait for the uncommitted operation to abort or commit. Further, this commit dependency only affects the order in which the operations should commit, if both commit; if either operation aborts, the other can still commit thus avoiding cascading aborts. To ensure the serializability of transactions, we force the recoverability relationship between transactions to be acyclic. Simulation studies, based on the model presented by Agrawal et al. [1], indicate that using recoverability, the turnaround time of transactions can be reduced. Further, our studies show enchancement in concurrency even when resource constraints are taken into consideration. The magnitude of enchancement is dependent on the resource contention; the lower the resource contention, the higher the improvement.

Copyright © 1992 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

CDROM Version: Load the CDROM "Volume 3 Issue 2, TODS 1991-1995, TKDE 1989-1992" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

Online Edition: ACM Digital Library

[Abstract, Index Terms and Review]
[Full Text in PDF Format, 2100 KB]

References

[1]
Rakesh Agrawal, Michael J. Carey, Miron Livny: Concurrency Control Performance Modeling: Alternatives and Implications. ACM Trans. Database Syst. 12(4): 609-654(1987) BibTeX
[2]
...
[3]
B. R. Badrinath, Krithi Ramamritham: Semantics-Based Concurrency Control: Beyond Commutativity. ICDE 1987: 304-311 BibTeX
[4]
B. R. Badrinath, Krithi Ramamritham: Performance Evaluation of Semantics-based Multilevel Concurrency Control Protocols. SIGMOD Conference 1990: 163-172 BibTeX
[5]
Catriel Beeri, Philip A. Bernstein, Nathan Goodman: A Concurrency Control Theory for Nested Transactions. PODC 1983: 45-62 BibTeX
[6]
Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
Contents BibTeX
[7]
Kenneth P. Birman, Thomas A. Joseph, Thomas Räuchle, Amr El Abbadi: Implementing Fault-Tolerant Distributed Objects. IEEE Trans. Software Eng. 11(6): 502-508(1985) BibTeX
[8]
Gabriel Bracha, Sam Toueg: A Distributed Algorithm for Generalized Deadlock Detection. PODC 1984: 285-301 BibTeX
[9]
Gael N. Buckley, Abraham Silberschatz: Beyond Two-Phase Locking. J. ACM 32(2): 314-326(1985) BibTeX
[10]
...
[11]
Ricardo Cordon, Hector Garcia-Molina: The Performance of a Concurrency Control Mechanism that Exploits Semantic Knowledge. ICDCS 1985: 350-358 BibTeX
[12]
David J. DeWitt, Randy H. Katz, Frank Olken, Leonard D. Shapiro, Michael Stonebraker, David A. Wood: Implementation Techniques for Main Memory Database Systems. SIGMOD Conference 1984: 1-8 BibTeX
[13]
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
[14]
Hector Garcia-Molina: Using Semantic Knowledge for Transaction Processing in Distributed Database. ACM Trans. Database Syst. 8(2): 186-213(1983) BibTeX
[15]
...
[16]
Maurice Herlihy: Apologizing Versus Asking Permission: Optimistic Concurrency Control for Abstract Data Types. ACM Trans. Database Syst. 15(1): 96-124(1990) BibTeX
[17]
Maurice Herlihy, William E. Weihl: Hybrid Concurrency Control for Abstract Data Types. PODS 1988: 201-210 BibTeX
[18]
Henry F. Korth: Locking Primitives in a Database System. J. ACM 30(1): 55-79(1983) BibTeX
[19]
H. T. Kung, John T. Robinson: On Optimistic Methods for Concurrency Control. ACM Trans. Database Syst. 6(2): 213-226(1981) BibTeX
[20]
...
[21]
J. Eliot B. Moss, Nancy D. Griffeth, Marc H. Graham: Abstraction in Recovery Management. SIGMOD Conference 1986: 72-83 BibTeX
[22]
Brian M. Oki, Barbara Liskov, Robert Scheifler: Reliable Object Storage to Support Atomic Actions. SOSP 1985: 147-159 BibTeX
[23]
Christos H. Papadimitriou: The serializability of concurrent database updates. J. ACM 26(4): 631-653(1979) BibTeX
[24]
Peter M. Schwarz, Alfred Z. Spector: Synchronizing Shared Abstract Types. ACM Trans. Comput. Syst. 2(3): 223-250(1984) BibTeX
[25]
Mukul K. Sinha, N. Natarajan: A Priority Based Distributed Deadlock Detection Algorithm. IEEE Trans. Software Eng. 11(1): 67-80(1985) BibTeX
[26]
Michael Stonebraker, Randy H. Katz, David A. Patterson, John K. Ousterhout: The Design of XPRS. VLDB 1988: 318-330 BibTeX
[27]
Y. C. Tay, Rajan Suri, Nathan Goodman: A Mean Value Performance Model for Locking in Databases: The No-Waiting Case. J. ACM 32(3): 618-651(1985) BibTeX
[28]
Y. C. Tay, Nathan Goodman, Rajan Suri: Locking Performance in Centralized Databases. ACM Trans. Database Syst. 10(4): 415-462(1985) BibTeX
[29]
...
[30]
William E. Weihl: Commutativity-Based Concurrency Control for Abstract Data Types. IEEE Trans. Computers 37(12): 1488-1505(1988) BibTeX
[31]
William E. Weihl, Barbara Liskov: Implementation of Resilient, Atomic Data Types. ACM Trans. Program. Lang. Syst. 7(2): 244-269(1985) BibTeX

Referenced by

  1. Alexander Thomasian: Concurrency Control: Methods, Performance, and Analysis. ACM Comput. Surv. 30(1): 70-119(1998)
  2. Arthur J. Bernstein, David Scott Gerstl, Wai-Hong Leung, Philip M. Lewis: Design and Performance of an Assertional Concurrency Control System. ICDE 1998: 436-445
  3. Paul Ammann, Sushil Jajodia, Indrakshi Ray: Applying Formal Methods to Semantic-Based Decomposition of Transactions. ACM Trans. Database Syst. 22(2): 215-254(1997)
  4. H. V. Jagadish, Inderpal Singh Mumick, Michael Rabinovich: Scalable Versioning in Distributed Databases with Commuting Updates. ICDE 1997: 520-531
  5. Javam Machado, Christine Collet: A Parallel Execution Model for Database Transactions. DASFAA 1997: 511-520
  6. Henry F. Korth: The Double Life of the Transaction Abstraction: Fundamental Principle and Evolving System Concept. VLDB 1995: 2-6
  7. Paul Ammann, Sushil Jajodia, Indrakshi Ray: Using Formal Methods to Reason about Semantics-Based Decompositions of Transactions. VLDB 1995: 218-227
  8. Radek Vingralek, Haiyan Ye, Yuri Breitbart, Hans-Jörg Schek: Unified Transaction Model for Semantically Rich Operations. ICDT 1995: 148-161
  9. Kenneth Salem, Hector Garcia-Molina, Jeannie Shands: Altruistic Locking. ACM Trans. Database Syst. 19(1): 117-165(1994)
  10. Panos K. Chrysanthis, Krithi Ramamritham: Synthesis of Extended Transaction Models Using ACTA. ACM Trans. Database Syst. 19(3): 450-491(1994)
  11. Divyakant Agrawal, Amr El Abbadi, A. E. Lang: The Performance of Protocols Based on Locks with Ordered Sharing. IEEE Trans. Knowl. Data Eng. 6(5): 805-818(1994)
  12. Alexandros Biliris, Shaul Dar, Narain H. Gehani, H. V. Jagadish, Krithi Ramamritham: ASSET: A System for Supporting Extended Transactions. SIGMOD Conference 1994: 44-54
  13. Divyakant Agrawal, John L. Bruno, Amr El Abbadi, Vashudha Krishnaswamy: Relative Serializbility: An Approach for Relaxing the Atomicity of Transactions. PODS 1994: 139-149
  14. Alexander Thomasian: Two-Phase Locking Performance and Its Thrashing Behavior. ACM Trans. Database Syst. 18(4): 579-625(1993)
  15. H. V. Jagadish, Abraham Silberschatz, S. Sudarshan: Recovering from Main-Memory Lapses. VLDB 1993: 391-404
  16. Man Hon Wong, Divyakant Agrawal: Context-Based Synchronisation: An Approach beyond Semantics for Concurrency Control. PODS 1993: 276-287
  17. Rajeev Rastogi, Henry F. Korth, Abraham Silberschatz: Strict Histories in Object-Based Database Systems. PODS 1993: 288-299
  18. H. V. Jagadish, Oded Shmueli: Proclamation-Based Model for Cooperating Transactions. VLDB 1992: 265-276
  19. Man Hon Wong, Divyakant Agrawal: Tolerating Bounded Inconsistency for Increasing Concurrency in Database Systems. PODS 1992: 236-245
  20. Man Hon Wong, Divyakant Agrawal: Context-Specific Synchronization for Atomic Data Types. ICDT 1992: 201-215
  21. Panos K. Chrysanthis, S. Raghuram, Krithi Ramamritham: Extracting Concurrency from Objects: A Methodology. SIGMOD Conference 1991: 108-117
  22. B. R. Badrinath, Krithi Ramamritham: Performance Evaluation of Semantics-based Multilevel Concurrency Control Protocols. SIGMOD Conference 1990: 163-172
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Tue Jun 24 18:39:12 2008