ACM SIGMOD Anthology TODS dblp.uni-trier.de

Using Semantic Knowledge of Transactions to Increase Concurrency.

Abdel Aziz Farrag, M. Tamer Özsu: Using Semantic Knowledge of Transactions to Increase Concurrency. ACM Trans. Database Syst. 14(4): 503-525(1989)
@article{DBLP:journals/tods/FarragO89,
  author    = {Abdel Aziz Farrag and
               M. Tamer {\"O}zsu},
  title     = {Using Semantic Knowledge of Transactions to Increase Concurrency},
  journal   = {ACM Trans. Database Syst.},
  volume    = {14},
  number    = {4},
  year      = {1989},
  pages     = {503-525},
  ee        = {http://doi.acm.org/10.1145/76902.76905, db/journals/tods/FarragO89.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

When the only information available about transactions is syntactic information, serializability is the main correctness criterion for concurrency control. Serializability requires that the execution of each transaction must appear to every other transaction as a single atomic step (i.e., the execution of the transaction cannot be interrupted by other transactions). Many researchers, however, have realized that this requirement is unnecessarily strong for many applications and can significantly increase transaction response time. To overcome this problem, a new approach for controlling concurrency that exploits the semantic information available about transactions to allow controlled nonserializable interleavings has recently been proposed. This approach is useful when the cost of producing only serializable interleavings is unacceptably high. The main drawback of the approach is the extra overhead incurred by utilizing the semantic information. We examine this new approach in this paper and discuss its strengths and weaknesses. We introduce a new formalization for the concurrency control problem when semantic information is available about the transactions. This semantic information takes the form of transaction types, transaction steps, and transaction breakpoints. We define a new class of "safe" schedules called relatively consistent (RC) schedules. This class contains serializable as well as nonserializable schedules. We prove that the execution of an RC schedule cannot violate consistency and propose a new concurrency control mechanism that produces only RC schedules. Our mechanism assumes fewer restrictions on the interleavings among transactions than previously introduced semantic-based mechanisms.

Copyright © 1989 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 1, TODS 1976-1990" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

References

[1]
Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley 1974, ISBN 0-201-00029-6
BibTeX
[2]
...
[3]
Rudolf Bayer, Hans Heller, Angelika Reiser: Parallelism and Recovery in Database Systems. ACM Trans. Database Syst. 5(2): 139-156(1980) BibTeX
[4]
Philip A. Bernstein, Nathan Goodman: Concurrency Control in Distributed Database Systems. ACM Comput. Surv. 13(2): 185-221(1981) BibTeX
[5]
Ricardo Cordon, Hector Garcia-Molina: The Performance of a Concurrency Control Mechanism that Exploits Semantic Knowledge. ICDCS 1985: 350-358 BibTeX
[6]
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
[7]
...
[8]
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
[9]
Michael J. Fischer, Nancy D. Griffeth, Nancy A. Lynch: Global States of a Distributed System. IEEE Trans. Software Eng. 8(3): 198-202(1982) BibTeX
[10]
Hector Garcia-Molina: Using Semantic Knowledge for Transaction Processing in Distributed Database. ACM Trans. Database Syst. 8(2): 186-213(1983) BibTeX
[11]
Jim Gray: Notes on Data Base Operating Systems. Advanced Course: Operating Systems 1978: 393-481 BibTeX
[12]
Richard C. Holt: Some Deadlock Properties of Computer Systems. ACM Comput. Surv. 4(3): 179-196(1972) BibTeX
[13]
H. T. Kung, Christos H. Papadimitriou: An Optimality Theory of Concurrency Control for Databases. SIGMOD Conference 1979: 116-126 BibTeX
[14]
H. T. Kung, John T. Robinson: On Optimistic Methods for Concurrency Control. ACM Trans. Database Syst. 6(2): 213-226(1981) BibTeX
[15]
...
[16]
Nancy A. Lynch: Multilevel Atomicity - A New Correctness Criterion for Database Concurrency Control. ACM Trans. Database Syst. 8(4): 484-502(1983) BibTeX
[17]
...
[18]
Daniel J. Rosenkrantz, Richard Edwin Stearns, Philip M. Lewis II: System Level Concurrency Control for Distributed Database Systems. ACM Trans. Database Syst. 3(2): 178-198(1978) BibTeX
[19]
David J. Rypka, Anthony P. Lucido: Deadlock Detection and Avoidance for Shared Logical Resources. IEEE Trans. Software Eng. 5(5): 465-471(1979) BibTeX

Referenced by

  1. Sharad Mehrotra, Rajeev Rastogi, Henry F. Korth, Abraham Silberschatz: Ensuring Consistency in Multidatabases by Preserving Two-Level Serializability. ACM Trans. Database Syst. 23(2): 199-230(1998)
  2. Alexander Thomasian: Concurrency Control: Methods, Performance, and Analysis. ACM Comput. Surv. 30(1): 70-119(1998)
  3. 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
  4. Tetsuya Furukawa, Haiyan Xu, Yihua Shi: Supporting Collaborative Work by Process-Based Transaction Model. ER Workshops 1998: 421-433
  5. Paul Ammann, Sushil Jajodia, Indrakshi Ray: Applying Formal Methods to Semantic-Based Decomposition of Transactions. ACM Trans. Database Syst. 22(2): 215-254(1997)
  6. Lisa Cingiser DiPippo, Victor Fay Wolfe: Object-Based Semantic Real-Time Concurrency Control with Bounded Imprecision. IEEE Trans. Knowl. Data Eng. 9(1): 135-147(1997)
  7. Krithi Ramamritham, Panos K. Chrysanthis: A Taxonomy of Correctness Criteria in Database Applications. VLDB J. 5(1): 85-97(1996)
  8. Dimitrios Georgakopoulos, Mark F. Hornick, Frank Manola: Customizing Transaction Models and Mechanisms in a Programmable Environment Supporting Reliable Workflow Automation. IEEE Trans. Knowl. Data Eng. 8(4): 630-649(1996)
  9. Dennis Shasha, François Llirbat, Eric Simon, Patrick Valduriez: Transaction Chopping: Algorithms and Performance Studies. ACM Trans. Database Syst. 20(3): 325-363(1995)
  10. Paul Ammann, Sushil Jajodia, Indrakshi Ray: Using Formal Methods to Reason about Semantics-Based Decompositions of Transactions. VLDB 1995: 218-227
  11. Dimitrios Georgakopoulos, Marek Rusinkiewicz, Witold Litwin: Chronological Scheduling of Transactions with Temporal Dependencies. VLDB J. 3(1): 1-28(1994)
  12. Kenneth Salem, Hector Garcia-Molina, Jeannie Shands: Altruistic Locking. ACM Trans. Database Syst. 19(1): 117-165(1994)
  13. Narayanan Krishnakumar, Arthur J. Bernstein: Bounded Ignorance: A Technique for Increasing Concurrency in a Replicated System. ACM Trans. Database Syst. 19(4): 586-625(1994)
  14. Henry F. Korth, Gregory D. Speegle: Formal Aspects of Concurrency Control in Long-Duration Transaction Systems Using the NT/PV Model. ACM Trans. Database Syst. 19(3): 492-535(1994)
  15. Gustavo Alonso, Divyakant Agrawal, Amr El Abbadi: Reducing Recovery Constraints on Locking based Protocols. PODS 1994: 129-138
  16. Divyakant Agrawal, John L. Bruno, Amr El Abbadi, Vashudha Krishnaswamy: Relative Serializbility: An Approach for Relaxing the Atomicity of Transactions. PODS 1994: 139-149
  17. Dimitrios Georgakopoulos, Mark F. Hornick, Piotr Krychniak, Frank Manola: Specification and Management of Extended Transactions in a Programmable Transaction Environment. ICDE 1994: 462-473
  18. Marek Rusinkiewicz, Amit P. Sheth: Transactional Workflow Management in Distributed Systems (Invited Paper). ADBIS 1994: 18-33
  19. Divyakant Agrawal, Amr El Abbadi, Ambuj K. Singh: Consistency and Orderability: Semantics-Based Correctness Criteria for Databases. ACM Trans. Database Syst. 18(3): 460-486(1993)
  20. Rajeev Rastogi, Sharad Mehrotra, Yuri Breitbart, Henry F. Korth, Abraham Silberschatz: On Correctness of Non-serializable Executions. PODS 1993: 97-108
  21. Yuri Breitbart, Hector Garcia-Molina, Abraham Silberschatz: Overview of Multidatabase Transaction Management. VLDB J. 1(2): 181-239(1992)
  22. Dennis Shasha, Eric Simon, Patrick Valduriez: Simple Rational Guidance for Chopping Up Transactions. SIGMOD Conference 1992: 298-307
  23. Man Hon Wong, Divyakant Agrawal: Tolerating Bounded Inconsistency for Increasing Concurrency in Database Systems. PODS 1992: 236-245
  24. Henry F. Korth, Eliezer Levy, Abraham Silberschatz: A Formal Approach to Recovery by Compensating Transactions. VLDB 1990: 95-106
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:07 2008