ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Formal Model of Correctness Without Serializability.

Henry F. Korth, Gregory D. Speegle: Formal Model of Correctness Without Serializability. SIGMOD Conference 1988: 379-386
@inproceedings{DBLP:conf/sigmod/KorthS88,
  author    = {Henry F. Korth and
               Gregory D. Speegle},
  editor    = {Haran Boral and
               Per-{\AA}ke Larson},
  title     = {Formal Model of Correctness Without Serializability},
  booktitle = {Proceedings of the 1988 ACM SIGMOD International Conference on
               Management of Data, Chicago, Illinois, June 1-3, 1988},
  publisher = {ACM Press},
  year      = {1988},
  pages     = {379-386},
  ee        = {http://doi.acm.org/10.1145/50202.50248, db/conf/sigmod/KorthS88.html},
  crossref  = {DBLP:conf/sigmod/88},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

In the classical approach to transaction processing, a concurrent execution is considered to be correct if it is equivalent to a non-concurrent schedule. This notion of correctness is called serializability. Serializability has proven to be a highly useful concept for transaction systems for data-processing style applications. Recent interest in applying database concepts to applications in computer-aided design, office information systems, etc. has resulted in transactions of relatively long duration. For such transactions, there are serious consequences to requiring serializability as the notion of correctness. Specifically, such systems either impose long-duration waits or require the abortion of long transactions. In this paper, we define a transaction model that allows for several alternative notions of correctness without the requirement of serializability. After introducing the model, we investigate classes of schedules for transactions. We show that these classes are richer than analogous classes under the classical model. Finally, we show the potential practicality of our model by describing protocols that permit a transaction manager to allow correct non-serializable executions.

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

Online Version (ACM WWW Account required): Full Text in PDF Format

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

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

Haran Boral, Per-Åke Larson (Eds.): Proceedings of the 1988 ACM SIGMOD International Conference on Management of Data, Chicago, Illinois, June 1-3, 1988. ACM Press 1988 BibTeX , SIGMOD Record 17(2), June 1988
Contents

Online Edition: ACM Digital Library

References

[Bancilhon et al. 85]
François Bancilhon, Won Kim, Henry F. Korth: A Model of CAD Transactions. VLDB 1985: 25-33 BibTeX
[Beeri et al. 89]
Catriel Beeri, Philip A. Bernstein, Nathan Goodman: A model for concurrency in nested transactions systems. J. ACM 36(2): 230-269(1989) BibTeX
[Bernstein et al. 87]
Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
Contents BibTeX
[Eswaran et al. 76]
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
[Fekete et al. 87]
Alan Fekete, Nancy A. Lynch, Michael Merritt, William E. Weihl: Nested Transactions and Read/Write Locking. PODS 1987: 97-111 BibTeX
[Kim et al. 84]
Won Kim, Raymond A. Lorie, Dan McNabb, Wil Plouffe: A Transaction Mechanism for Engineering Design Databases. VLDB 1984: 355-362 BibTeX
[Korth 83]
Henry F. Korth: Locking Primitives in a Database System. J. ACM 30(1): 55-79(1983) BibTeX
[Korth et al. 88]
...
[Liskov et al. 87]
Barbara Liskov, Dorothy Curtis, Paul Johnson, Robert Scheifler: Implementation of Argus. SOSP 1987: 111-122 BibTeX
[Lorie and Plouffe 83]
...
[Lynch 86]
Nancy A. Lynch: Concurrency Control for Resilient Nested Transactions. Advances in Computing Research 3: 335-373(1986) BibTeX
[Moss 85]
...
[Moss et al. 86]
J. Eliot B. Moss, Nancy D. Griffeth, Marc H. Graham: Abstraction in Recovery Management. SIGMOD Conference 1986: 72-83 BibTeX
[Papadimitriou 79]
Christos H. Papadimitriou: The serializability of concurrent database updates. J. ACM 26(4): 631-653(1979) BibTeX
[Papadimitriou 86]
...
[Papadimitriou and Kanellakis 82]
Christos H. Papadimitriou, Paris C. Kanellakis: On Concurrency Control by Multiple Versions. PODS 1982: 76-82 BibTeX
[Weikum and Schek 84]
Gerhard Weikum, Hans-Jörg Schek: Architectural Issues of Transaction Management in Multi-Layered Systems. VLDB 1984: 454-465 BibTeX
[Yannakakis 82]
Mihalis Yannakakis: A Theory of Safe Locking Policies in Database Systems. J. ACM 29(3): 718-740(1982) 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. Kun-Lung Wu, Philip S. Yu, Calton Pu: Divergence Control Algorithms for Epsilon Serializability. IEEE Trans. Knowl. Data Eng. 9(2): 262-274(1997)
  3. Sanjay Kumar Madria, Bharat K. Bhargava: System Defined Prewrites for Increasing Concurrency in Databases. ADBIS 1997: 18-22
  4. Krithi Ramamritham, Panos K. Chrysanthis: A Taxonomy of Correctness Criteria in Database Applications. VLDB J. 5(1): 85-97(1996)
  5. Krithi Ramamritham, Calton Pu: A Formal Characterization of Epsilon Serializability. IEEE Trans. Knowl. Data Eng. 7(6): 997-1007(1995)
  6. Paul Ammann, Sushil Jajodia, Indrakshi Ray: Using Formal Methods to Reason about Semantics-Based Decompositions of Transactions. VLDB 1995: 218-227
  7. Dimitrios Georgakopoulos, Marek Rusinkiewicz, Witold Litwin: Chronological Scheduling of Transactions with Temporal Dependencies. VLDB J. 3(1): 1-28(1994)
  8. Daniel Barbará, Hector Garcia-Molina: The Demarcation Protocol: A Technique for Maintaining Constraints in Distributed Database Systems. VLDB J. 3(3): 325-353(1994)
  9. 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)
  10. 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)
  11. Panos K. Chrysanthis, Krithi Ramamritham: Synthesis of Extended Transaction Models Using ACTA. ACM Trans. Database Syst. 19(3): 450-491(1994)
  12. 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)
  13. Andrea H. Skarra: SLEVE: Semantic Locking for EVEnt synchronisation. ICDE 1993: 495-502
  14. Marian H. Nodine, Stanley B. Zdonik: Cooperative Transaction Hierarchies: Transaction Support for Design Applications. VLDB J. 1(1): 41-80(1992)
  15. Yuri Breitbart, Hector Garcia-Molina, Abraham Silberschatz: Overview of Multidatabase Transaction Management. VLDB J. 1(2): 181-239(1992)
  16. H. V. Jagadish, Oded Shmueli: Proclamation-Based Model for Cooperating Transactions. VLDB 1992: 265-276
  17. Kun-Lung Wu, Philip S. Yu, Calton Pu: Divergence Control for Epsilon-Serializability. ICDE 1992: 506-515
  18. Daniel Barbará, Hector Garcia-Molina: The Demarcation Protocol: A Technique for Maintaining Linear Arithmetic Constraints in Distributed Database Systems. EDBT 1992: 373-388
  19. Naser S. Barghouti, Gail E. Kaiser: Concurrency Control in Advanced Database Applications. ACM Comput. Surv. 23(3): 269-317(1991)
  20. Panos K. Chrysanthis, Krithi Ramamritham: A Formalism for Extended Transaction Model. VLDB 1991: 103-112
  21. Narayanan Krishnakumar, Arthur J. Bernstein: Bounded Ignorance in Replicated Systems. PODS 1991: 63-74
  22. Henry F. Korth, Nandit Soparkar, Abraham Silberschatz: Triggered Real-Time Databases with Consistency Constraints. VLDB 1990: 71-82
  23. Henry F. Korth, Eliezer Levy, Abraham Silberschatz: A Formal Approach to Recovery by Compensating Transactions. VLDB 1990: 95-106
  24. Henry F. Korth, Gregory D. Speegle: Long-Duration Transactions in Software Design Projects. ICDE 1990: 568-574
  25. Weimin Du, Ahmed K. Elmagarmid: Quasi Serializability: a Correctness Criterion for Global Concurrency Control in InterBase. VLDB 1989: 347-355
  26. Victor Vianu, Gottfried Vossen: Goal-Oriented Concurrency Control. MFDBS 1989: 398-414
  27. Andrea Bondavalli, Nicoletta De Francesco, Diego Latella, Gigliola Vaglini: Shared Abstract Data Types: An Algebraic Methodology for Their Specification. MFDBS 1989: 53-67
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:39:55 2009