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

A Semantic Approach to Correctness of Concurrent Transaction Executions.

Alexander Tuzhilin, Paul G. Spirakis: A Semantic Approach to Correctness of Concurrent Transaction Executions. PODS 1985: 85-95
@inproceedings{DBLP:conf/pods/TuzhilinS85,
  author    = {Alexander Tuzhilin and
               Paul G. Spirakis},
  title     = {A Semantic Approach to Correctness of Concurrent Transaction
               Executions},
  booktitle = {Proceedings of the Fourth ACM SIGACT-SIGMOD Symposium on Principles
               of Database Systems, March 25-27, 1985, Portland, Oregon},
  publisher = {ACM},
  year      = {1985},
  isbn      = {0-89791-153-9},
  pages     = {85-95},
  ee        = {http://doi.acm.org/10.1145/325405.325416, db/conf/pods/TuzhilinS85.html},
  crossref  = {DBLP:conf/pods/85},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

One of the main issues in concurrency control is the question of what constitutes a legal or correct behavior of a group of transactions updating the database simultaneously. It seems that the undesirable effects of concurrent transaction executions can be put into three classes: violation of integrity constraints, inconsistent outputs to users and racing. An intuitive way to define correctness of transaction schedules is then to require that the scheduler avoid all three types of anomalies. In this paper, we formalize this notion of correctness. To do this, we develop a new, desirable, semantic property of transaction schedules, which we call independence. Then, we give a partial answer to the followinq question: Is there any intermediate class of schedules, between the classes of the serializable and correct schedules, that has an easy membership test? We first prove a negative result. For integrity constraints in the form of linear inequalities and for linear semantics of transaction actions, we show that the serializable schedules are the only class of schedules preserving those integrity constraints. However, if the semantics of transaction actions are more restricted, then there exists a class of nonserializable schedules (we call them weakly serializable of order 2) which is a proper subset of the class of correct schedules and has an easy membership test.

Copyright © 1985 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 ... BibTeX

Printed Edition

Proceedings of the Fourth ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, March 25-27, 1985, Portland, Oregon. ACM 1985, ISBN 0-89791-153-9
Contents BibTeX

Online Edition: ACM Digital Library

References

[Bern 79]
Philip A. Bernstein, David W. Shipman, Wing S. Wong: Formal Aspects of Serializability in Database Concurrency Control. IEEE Trans. Software Eng. 5(3): 203-216(1979) BibTeX
[Bern 80]
Philip A. Bernstein, David W. Shipman, James B. Rothnie Jr.: Concurrency Control in a System for Distributed Databases (SDD-1). ACM Trans. Database Syst. 5(1): 18-51(1980) BibTeX
[Bern 81]
Philip A. Bernstein, Nathan Goodman: Concurrency Control in Distributed Database Systems. ACM Comput. Surv. 13(2): 185-221(1981) BibTeX
[Casa 80]
Marco A. Casanova, Philip A. Bernstein: General Purpose Schedulers for Database Systems. Acta Inf. 14: 195-220(1980) BibTeX
[Esw 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
[Fisc 82]
Michael J. Fischer, A. Michael: Sacrificing Serializability to Attain High Availability of Data. PODS 1982: 70-75 BibTeX
[Garc 83]
Hector Garcia-Molina: Using Semantic Knowledge for Transaction Processing in Distributed Database. ACM Trans. Database Syst. 8(2): 186-213(1983) BibTeX
[Kung 79]
H. T. Kung, Christos H. Papadimitriou: An Optimality Theory of Concurrency Control for Databases. SIGMOD Conference 1979: 116-126 BibTeX
[Papa 79]
Christos H. Papadimitriou: The serializability of concurrent database updates. J. ACM 26(4): 631-653(1979) BibTeX
[Schl 78]
Gunter Schlageter: Process Synchronization in Database Systems. ACM Trans. Database Syst. 3(3): 248-271(1978) BibTeX
[Shas 84]
...
[Silb 80]
Abraham Silberschatz, Zvi M. Kedem: Consistency in Hierarchical Database Systems. J. ACM 27(1): 72-80(1980) BibTeX
[Ull 82]
Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
BibTeX

Referenced by

  1. Victor Vianu, Gottfried Vossen: Goal-Oriented Concurrency Control. MFDBS 1989: 398-414
  2. Dennis Shasha, Nathan Goodman: Concurrent Search Structure Algorithms. ACM Trans. Database Syst. 13(1): 53-90(1988)
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:33:46 2009