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

Towards a Unified Theory of Concurrency Control and Recovery.

Hans-Jörg Schek, Gerhard Weikum, Haiyan Ye: Towards a Unified Theory of Concurrency Control and Recovery. PODS 1993: 300-311
@inproceedings{DBLP:conf/pods/SchekWY93,
  author    = {Hans-J{\"o}rg Schek and
               Gerhard Weikum and
               Haiyan Ye},
  title     = {Towards a Unified Theory of Concurrency Control and Recovery},
  booktitle = {Proceedings of the Twelfth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, May 25-28, 1993, Washington,
               DC},
  publisher = {ACM Press},
  year      = {1993},
  isbn      = {0-89791-593-3},
  pages     = {300-311},
  ee        = {http://doi.acm.org/10.1145/153850.153935, db/conf/pods/SchekWY93.html},
  crossref  = {DBLP:conf/pods/93},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

The classical theory of transaction management is based on two different and independent criteria for the correct execution of transactions. The first criterion, serializability, ensures correct execution of parallel transactions under the assumption that no failures occur. The second criterion, strictness, ensures correct recovery from failures.

In this paper we develop a unified model that allows reasoning about the correctness of concurrency control and recovery within the same framework. We introduce the correctness criteria of (prefix-) reducibility and (prefix-) expanded serializability and investigate their relationships to the classical criteria. An important advantage of our model is that it captures schedules with semantically rich ADT actions in addition to classical read/write schedules.

Copyright © 1993 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.


Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ...

Printed Edition

Proceedings of the Twelfth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 25-28, 1993, Washington, DC. ACM Press 1993, ISBN 0-89791-593-3
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 1150 KB]

References

[BBG89]
Catriel Beeri, Philip A. Bernstein, Nathan Goodman: A model for concurrency in nested transactions systems. J. ACM 36(2): 230-269(1989) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BGRS91]
Yuri Breitbart, Dimitrios Georgakopoulos, Marek Rusinkiewicz, Abraham Silberschatz: On Rigorous Transaction Scheduling. IEEE Trans. Software Eng. 17(9): 954-960(1991) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BSW88]
Catriel Beeri, Hans-Jörg Schek, Gerhard Weikum: Multi-Level Transaction Management, Theoretical Art or Practical Need ? EDBT 1988: 134-154 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Dij76]
Edsger W. Dijkstra: A Discipline of Programming. Prentice-Hall 1976
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GM83]
Hector Garcia-Molina: Using Semantic Knowledge for Transaction Processing in Distributed Database. ACM Trans. Database Syst. 8(2): 186-213(1983) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GR93]
Jim Gray, Andreas Reuter: Transaction Processing: Concepts and Techniques. Morgan Kaufmann 1993, ISBN 1-55860-190-2
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Had88]
Vassos Hadzilacos: A theory of reliability in database systems. J. ACM 35(1): 121-145(1988) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HH88]
Thanasis Hadzilacos, Vassos Hadzilacos: Transaction Synchronisation in Object Bases. PODS 1988: 193-200 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HW88]
Maurice Herlihy, William E. Weihl: Hybrid Concurrency Control for Abstract Data Types. PODS 1988: 201-210 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SWY92]
...
[Kor83]
Henry F. Korth: Locking Primitives in a Database System. J. ACM 30(1): 55-79(1983) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KRST92]
...
[LKS91]
Eliezer Levy, Henry F. Korth, Abraham Silberschatz: A Theory of Relaxed Atomicity (Extended Abstract). PODC 1991: 95-109 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LMWF93]
...
[MGG86]
J. Eliot B. Moss, Nancy D. Griffeth, Marc H. Graham: Abstraction in Recovery Management. SIGMOD Conference 1986: 72-83 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[MHL+92]
C. Mohan, Donald J. Haderle, Bruce G. Lindsay, Hamid Pirahesh, Peter M. Schwarz: ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging. ACM Trans. Database Syst. 17(1): 94-162(1992) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[MRW+93]
Peter Muth, Thomas C. Rakow, Gerhard Weikum, Peter Brössler, Christof Hasse: Semantic Concurrency Control in Object-Oriented Database Systems. ICDE 1993: 233-242 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[O'N86]
Patrick E. O'Neil: The Escrow Transactional Method. ACM Trans. Database Syst. 11(4): 405-430(1986) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Pap86]
...
[BHG87]
Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[RKS93]
Rajeev Rastogi, Henry F. Korth, Abraham Silberschatz: Strict Histories in Object-Based Database Systems. PODS 1993: 288-299 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SS84]
Peter M. Schwarz, Alfred Z. Spector: Synchronizing Shared Abstract Types. ACM Trans. Comput. Syst. 2(3): 223-250(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SWY92]
...
[Vei90]
...
[Wei88]
...
[Wei89]
William E. Weihl: The Impact of Recovery on Concurrency Control. PODS 1989: 259-269 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Wei91]
Gerhard Weikum: Principles and Realization Strategies of Multilevel Transaction Management. ACM Trans. Database Syst. 16(1): 132-180(1991) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Referenced by

  1. Seppo Sippu, Eljas Soisalon-Soininen: A Theory of Transactions on Recoverable Search Trees. ICDT 2001: 83-98
  2. Jens Lechtenbörger, Gottfried Vossen: On Herbrand Semantics and Conflict Serializability of Read-Write Transactions. PODS 2000: 187-194
  3. Heiko Schuldt, Gustavo Alonso, Hans-Jörg Schek: Concurrency Control and Recovery in Transactional Process Management. PODS 1999: 316-326
  4. Gustavo Alonso, Stephen Blott, Armin Fessler, Hans-Jörg Schek: Correctness and Parallelism of Composite Systems. PODS 1997: 197-208
  5. Man Hon Wong: Recovery for Transaction Failures in Object-Based Databases. PODS 1996: 139-149
  6. Vadim V. Doubrovski: Key Integrity for Cooperative Database Environments with Stationary and Mobile Hosts. ADBIS 1996: 134-140
  7. Vinay K. Chaudhri, Vassos Hadzilacos: Safe Locking Policies for Dynamic Databases. PODS 1995: 233-244
  8. Radek Vingralek, Haiyan Ye, Yuri Breitbart, Hans-Jörg Schek: Unified Transaction Model for Semantically Rich Operations. ICDT 1995: 148-161
  9. Gustavo Alonso, Divyakant Agrawal, Amr El Abbadi: Reducing Recovery Constraints on Locking based Protocols. PODS 1994: 129-138
  10. Andrew Deacon, Hans-Jörg Schek, Gerhard Weikum: Semantics-Based Multilevel Transaction Management in Federated Systems. ICDE 1994: 452-461
  11. Gustavo Alonso, Radek Vingralek, Divyakant Agrawal, Yuri Breitbart, Amr El Abbadi, Hans-Jörg Schek, Gerhard Weikum: A Unified Approach to Concurrency Control and Transaction Recovery (Extended Abstract). EDBT 1994: 123-130
  12. Gerhard Weikum, Andrew Deacon, Werner Schaad, Hans-Jörg Schek: Open Nested Transactions in Federated Database Systems. IEEE Data Eng. Bull. 16(2): 4-7(1993)

Copyright © Mon Nov 2 21:04:23 2009 by Michael Ley (ley@uni-trier.de)