Towards a Unified Theory of Concurrency Control and Recovery.

@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.

• 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
• UNIX/LINUX/Mac: use mount point /pods8298/... 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
• UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

Printed Edition

Online Edition: ACM Digital Library

References

[BBG89]

Catriel Beeri, Philip A. Bernstein, Nathan Goodman: A model for concurrency in nested transactions systems. J. ACM 36(2): 230-269(1989) BibTeX

[BGRS91]

Yuri Breitbart, Dimitrios Georgakopoulos, Marek Rusinkiewicz, Abraham Silberschatz: On Rigorous Transaction Scheduling. IEEE Trans. Software Eng. 17(9): 954-960(1991) BibTeX

[BSW88]

Catriel Beeri, Hans-Jörg Schek, Gerhard Weikum: Multi-Level Transaction Management, Theoretical Art or Practical Need ? EDBT 1988: 134-154 BibTeX

[Dij76]

Edsger W. Dijkstra: A Discipline of Programming. Prentice-Hall 1976
BibTeX

[GM83]

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

[GR93]

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

[Had88]

Vassos Hadzilacos: A theory of reliability in database systems. J. ACM 35(1): 121-145(1988) BibTeX

[HH88]

Thanasis Hadzilacos, Vassos Hadzilacos: Transaction Synchronisation in Object Bases. PODS 1988: 193-200 BibTeX

[HW88]

Maurice Herlihy, William E. Weihl: Hybrid Concurrency Control for Abstract Data Types. PODS 1988: 201-210 BibTeX

[SWY92]

...

[Kor83]

Henry F. Korth: Locking Primitives in a Database System. J. ACM 30(1): 55-79(1983) BibTeX

[KRST92]

...

[LKS91]

Eliezer Levy, Henry F. Korth, Abraham Silberschatz: A Theory of Relaxed Atomicity (Extended Abstract). PODC 1991: 95-109 BibTeX

[LMWF93]

...

[MGG86]

J. Eliot B. Moss, Nancy D. Griffeth, Marc H. Graham: Abstraction in Recovery Management. SIGMOD Conference 1986: 72-83 BibTeX

[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) BibTeX

[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 BibTeX

[O'N86]

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

[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 BibTeX

[RKS93]

Rajeev Rastogi, Henry F. Korth, Abraham Silberschatz: Strict Histories in Object-Based Database Systems. PODS 1993: 288-299 BibTeX

[SS84]

Peter M. Schwarz, Alfred Z. Spector: Synchronizing Shared Abstract Types. ACM Trans. Comput. Syst. 2(3): 223-250(1984) BibTeX

[SWY92]

...

[Vei90]

...

[Wei88]

...

[Wei89]

William E. Weihl: The Impact of Recovery on Concurrency Control. PODS 1989: 259-269 BibTeX

[Wei91]

Gerhard Weikum: Principles and Realization Strategies of Multilevel Transaction Management. ACM Trans. Database Syst. 16(1): 132-180(1991) BibTeX

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)