Transaction Chopping: Algorithms and Performance Studies.

@article{DBLP:journals/tods/ShashaLSV95,
  author    = {Dennis Shasha and
               Fran\c{c}ois Llirbat and
               Eric Simon and
               Patrick Valduriez},
  title     = {Transaction Chopping: Algorithms and Performance Studies},
  journal   = {ACM Trans. Database Syst.},
  volume    = {20},
  number    = {3},
  year      = {1995},
  pages     = {325-363},
  ee        = {http://doi.acm.org/10.1145/211414.211427, db/journals/tods/ShashaLSV95.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Chopping transactions into pieces is good for performance but may lead to nonserializable executions. Many researchers have reacted to this fact by either inventing new concurrency-control mechanisms, weakening serializability, or both. We adopt a different approach. We assume a user who

• has access only to user-level tools such as (1) choosing isolation degrees 1-4, (2) the ability to execute a portion of a transaction using multiversion read consistency, and (3) the ability to reorder the instructions in transaction programs; and
• knows the set of transactions that may run during a certain interval (users are likely to have such knowledge for on-line or real-time transactional applications).

Given this information, our algorithm finds the finest chopping of a set of transactions TranSet with the following property: If the pieces of the chopping execute serializably, then TranSet executes serializably. This permits users to obtain more concurrency while preserving correctness. Besides obtaining more intertransaction concurrency, chopping transactions in this way can enhance intratransaction parallelism.

The algorithm is inexpensive, running in O(nx(e+m)) time, once conflicts are identified, using a naive implementation, where n is the number of concurrent transactions in the interval, e is the number of edges in the conflict graph among the transactions, and m is the maximum number of accesses of any transaction. This makes it feasible to add as a tuning knob to real systems.

Copyright © 1995 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-2 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

Online Edition: ACM Digital Library

References

[Adler et al. 1992]

...

[Agrawal et al. 1992]

Divyakant Agrawal, Amr El Abbadi, Richard Jeffers: Using Delayed Commitment in Locking Protocols for Real-Time Databases. SIGMOD Conference 1992: 104-113 BibTeX

[Agrawal et al. 1994]

Divyakant Agrawal, John L. Bruno, Amr El Abbadi, Vashudha Krishnaswamy: Relative Serializbility: An Approach for Relaxing the Atomicity of Transactions. PODS 1994: 139-149 BibTeX

[Agrawal 1994]

...

[Agrawal et al. 1987]

Rakesh Agrawal, Michael J. Carey, Miron Livny: Concurrency Control Performance Modeling: Alternatives and Implications. ACM Trans. Database Syst. 12(4): 609-654(1987) BibTeX

[Aho et al. 1986]

Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman: Compilers: Princiles, Techniques, and Tools. Addison-Wesley 1986, ISBN 0-201-10088-6
BibTeX

[Bayer 1986]

Rudolf Bayer: Consistency of Transactions and Random Batch. ACM Trans. Database Syst. 11(4): 397-404(1986) BibTeX

[Bernstein et al. 1980]

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

[Bernstein et al. 1991]

...

[Carey 1983]

Michael J. Carey: Modeling and Evaluation of Database Concurrency Control Algorithms. Ph.D. thesis, College of Engineering, University of California, Berkeley 1983
BibTeX

[Carey et al. 1990]

Michael J. Carey, Sanjay Krishnamurthi, Miron Livny: Load Control for Locking: The 'Half-and-Half' Approach. PODS 1990: 72-84 BibTeX

[Casanova 1981]

...

[Dadam et al. 1983]

...

[Farrag and Özsu 1987]

Abdel Aziz Farrag, M. Tamer Özsu: Towards a General Concurrency Control Algorithm for Database Systems. IEEE Trans. Software Eng. 13(10): 1073-1079(1987) BibTeX

[Farrag and Özsu 1989]

Abdel Aziz Farrag, M. Tamer Özsu: Using Semantic Knowledge of Transactions to Increase Concurrency. ACM Trans. Database Syst. 14(4): 503-525(1989) BibTeX

[Garcia-Molina 1983]

Hector Garcia-Molina: Using Semantic Knowledge for Transaction Processing in Distributed Database. ACM Trans. Database Syst. 8(2): 186-213(1983) BibTeX

[Gray 1991]

Jim Gray (Ed.): The Benchmark Handbook for Database and Transaction Systems (1st Edition). Morgan Kaufmann 1991
Contents BibTeX

[Gray and Reuter 1992]

Jim Gray, Andreas Reuter: Transaction Processing: Concepts and Techniques. Morgan Kaufmann 1993, ISBN 1-55860-190-2
Contents BibTeX

[Haritsa et al. 1990]

Jayant R. Haritsa, Michael J. Carey, Miron Livny: On Being Optimistic about Real-Time Constraints. PODS 1990: 331-343 BibTeX

[Helland et al. 1987]

Pat Helland, Harald Sammer, Jim Lyon, Richard Carr, Phil Garrett, Andreas Reuter: Group Commit Timers and High Volume Transaction Systems. HPTS 1987: 301-329 BibTeX

[Hseuh and Pu 1993]

...

[Hsu and Chan 1986]

Meichun Hsu, Arvola Chan: Partitioned Two-Phase Locking. ACM Trans. Database Syst. 11(4): 431-446(1986) BibTeX

[Lausen et al. 1986]

Georg Lausen, Eljas Soisalon-Soininen, Peter Widmayer: Pre-analysis Locking. Information and Control 70(2/3): 193-215(1986) BibTeX

[Llirbat 1994]

...

[Lynch 1983]

Nancy A. Lynch: Multilevel Atomicity - A New Correctness Criterion for Database Concurrency Control. ACM Trans. Database Syst. 8(4): 484-502(1983) BibTeX

[O'Neil 1986]

Patrick E. O'Neil: The Escrow Transactional Method. ACM Trans. Database Syst. 11(4): 405-430(1986) BibTeX

[Ramamritham and Chrysanthis 1995]

...

[Ryu and Thomasian 1990]

In Kyung Ryu, Alexander Thomasian: Analysis of Database Performance with Dynamic Locking. J. ACM 37(3): 491-523(1990) BibTeX

[Salzberg and Tombroff 1994]

...

[Shasha 1988]

Dennis Shasha, Marc Snir: Efficient and Correct Execution of Parallel Programs that Share Memory. ACM Trans. Program. Lang. Syst. 10(2): 282-312(1988) BibTeX

[Shasha 1992]

Dennis Shasha: Database Tuning - A Principled Approach. Prentice-Hall 1992, ISBN 0-13-205246-6
Contents BibTeX

[Tay 1987]

...

[Thomasian 1991]

Alexander Thomasian: Performance Limits of Two-Phase Locking. ICDE 1991: 426-435 BibTeX

[Thomasian and Ryu 1991]

Alexander Thomasian, In Kyung Ryu: Performance Analysis of Two-Phase Locking. IEEE Trans. Software Eng. 17(5): 386-402(1991) BibTeX

[Weiser 1984]

Mark Weiser: Program Slicing. IEEE Trans. Software Eng. 10(4): 352-357(1984) BibTeX

[Wolfson 1987]

Ouri Wolfson: The Virtues of Locking by Symbolic Names. J. Algorithms 8(4): 536-556(1987) BibTeX

[Wong and Edelberg 1977]

Kai C. Wong, Murray Edelberg: Interval Hierarchies and Their Application to Predicate Files. ACM Trans. Database Syst. 2(3): 223-232(1977) BibTeX

[Yannakakis 1982]

Mihalis Yannakakis: A Theory of Safe Locking Policies in Database Systems. J. ACM 29(3): 718-740(1982) 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. François Llirbat, Eric Simon, Dimitri Tombroff: Using Versions in Update Transactions: Application to Integrity Checking. VLDB 1997: 96-105
4. Eric Simon, Angelika Kotz Dittrich: Promises and Realities of Active Database Systems. VLDB 1995: 642-653