Simple Rational Guidance for Chopping Up Transactions.

@inproceedings{DBLP:conf/sigmod/ShashaSV92,
  author    = {Dennis Shasha and
               Eric Simon and
               Patrick Valduriez},
  editor    = {Michael Stonebraker},
  title     = {Simple Rational Guidance for Chopping Up Transactions},
  booktitle = {Proceedings of the 1992 ACM SIGMOD International Conference on
               Management of Data, San Diego, California, June 2-5, 1992},
  publisher = {ACM Press},
  year      = {1992},
  pages     = {298-307},
  ee        = {http://doi.acm.org/10.1145/130283.130328, db/conf/sigmod/ShashaSV92.html},
  crossref  = {DBLP:conf/sigmod/92},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Chopping transactions into pieces is good for performance but may lead to non-serializable 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 only the degree 2 and degree 3 consistency options offered by the vast majority of conventional database systems; and
• knows the set of transactions that may run during a certain interval (users are likely to have such knowledge for online or real-time transactional applications).

Given this information, our algorithm finds the finest partitioning of a set of transactions TranSet with the follotving property: if the partitioned transactions execute serializable, then TranSet executes serializable. This permits users to obtain more concurrency while preserving correctness. Besides obtaining more inter-transaction concurrency, chopping transactions in this way can enhance intra-transaction parallelism.

The algorithm is inexpensive, running in O(n × (e + m)) time 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 practical systems.

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.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...

• 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/smod7592 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/aDVD1 or /dvd

Printed Edition

Online Edition: ACM Digital Library

Journal Version

References

[1]

Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
Contents BibTeX

[2]

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

[3]

...

[4]

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

[10]

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

[11]

Mihalis Yannakakis: A Theory of Safe Locking Policies in Database Systems. J. ACM 29(3): 718-740(1982) BibTeX

[12]

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

[13]

...

[14]

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

Referenced by

1. Paul Ammann, Sushil Jajodia, Indrakshi Ray: Applying Formal Methods to Semantic-Based Decomposition of Transactions. ACM Trans. Database Syst. 22(2): 215-254(1997)
2. Paul Ammann, Sushil Jajodia, Indrakshi Ray: Using Formal Methods to Reason about Semantics-Based Decompositions of Transactions. VLDB 1995: 218-227
3. Gustavo Alonso, Divyakant Agrawal, Amr El Abbadi: Reducing Recovery Constraints on Locking based Protocols. PODS 1994: 129-138
4. Divyakant Agrawal, John L. Bruno, Amr El Abbadi, Vashudha Krishnaswamy: Relative Serializbility: An Approach for Relaxing the Atomicity of Transactions. PODS 1994: 139-149
5. Alexander Thomasian: Two-Phase Locking Performance and Its Thrashing Behavior. ACM Trans. Database Syst. 18(4): 579-625(1993)