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)

[BGRS91]

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

[BSW88]

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

[Dij76]

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

[GM83]

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

[GR93]

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

[Had88]

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

[HH88]

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

[HW88]

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

[SWY92]

...

[Kor83]

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

[KRST92]

...

[LKS91]

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

[LMWF93]

...

[MGG86]

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

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

[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

[O'N86]

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

[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

[RKS93]

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

[SS84]

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

[SWY92]

...

[Vei90]

...

[Wei88]

...

[Wei89]

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

[Wei91]

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