Serializability with Constraints.

Toshihide Ibaraki, Tiko Kameda, Toshimi Minoura: Serializability with Constraints. ACM Trans. Database Syst. 12(3): 429-452(1987)
  author    = {Toshihide Ibaraki and
               Tiko Kameda and
               Toshimi Minoura},
  title     = {Serializability with Constraints},
  journal   = {ACM Trans. Database Syst.},
  volume    = {12},
  number    = {3},
  year      = {1987},
  pages     = {429-452},
  ee        = {, db/journals/tods/IbarakiKM87.html},
  bibsource = {DBLP,}


This paper deals with the serializability theory for single-version and multiversion database systems. We first introduce the concept of disjoint-interval topological sort (DITS, for short) of an arc-labeled directed acyclic graph. It is shown that a history is serializable if and only if its transaction IO graph has a DITS. We then define several subclasses of serializable histories, based on the constraints imposed by write-write, write-read, read-write, or read-read conflicts, and investigate inclusion relationships among them. In terms of DITS, we give a sufficient condition for a class of serializable histories to be polynomially recognizable, which is then used to show that a new class of histories, named WRW, can be recognized in polynomial time. We also present NP-completeness results for the problem of testing membership in some other classes.

In the second half of this paper, we extend these results to multiversion database systems. The inclusion relationships among multiversion classes defined by constraints, such as write-write and write-read, are investigated. One such class coincides with class DMVSR, introduced by Papadimitriou and Kanellakis, and gives a simple characterization of this class. It is shown that for most constraints, multiversion classes properly contain the corresponding single-version classes. Complexity results for the membership testing are also discussed.

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

Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 1, TODS 1976-1990" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX


Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley 1974, ISBN 0-201-00029-6
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
Philip A. Bernstein, Nathan Goodman: Multiversion Concurrency Control - Theory and Algorithms. ACM Trans. Database Syst. 8(4): 465-483(1983) BibTeX
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
M. R. Garey, David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 1979, ISBN 0-7167-1044-7
Thanasis Hadzilacos, Christos H. Papadimitriou: Algorithmic Aspects of Multiversion Concurrency Control. PODS 1985: 96-104 BibTeX
Toshihide Ibaraki, Tiko Kameda, Toshimi Minoura: Disjoint-Interval Topological Sort: A Useful Concept in Serializability Theory (Extended Abstract). VLDB 1983: 89-91 BibTeX
Toshihide Ibaraki, Tiko Kameda, Naoki Katoh: Cautious Transaction Schedulers for Database Concurrency Control. IEEE Trans. Software Eng. 14(7): 997-1009(1988) BibTeX
Naoki Katoh, Toshihide Ibaraki, Tiko Kameda: Cautious Transaction Schedulers with Admission Control. ACM Trans. Database Syst. 10(2): 205-229(1985) BibTeX
Naoki Katoh, Tiko Kameda, Toshihide Ibaraki: A Cautious Scheduler for Multistep Transactions. Algorithmica 2: 1-26(1987) BibTeX
Shojiro Muro, Tiko Kameda, Toshimi Minoura: Multi-version Concurrency Control Scheme for a Database System. J. Comput. Syst. Sci. 29(2): 207-224(1984) BibTeX
Christos H. Papadimitriou: The serializability of concurrent database updates. J. ACM 26(4): 631-653(1979) BibTeX
Christos H. Papadimitriou, Paris C. Kanellakis: On Concurrency Control by Multiple Versions. ACM Trans. Database Syst. 9(1): 89-99(1984) BibTeX
Ravi Sethi: A model of concurrent database transactions (summary). FOCS 1981: 175-184 BibTeX
Ravi Sethi: Useless Actions Make a Difference: Strict Serializability of Database Updates. J. ACM 29(2): 394-403(1982) BibTeX
Richard Edwin Stearns, Philip M. Lewis II, Daniel J. Rosenkrantz: Concurrency Control for Database Systems. FOCS 1976: 19-32 BibTeX
Mihalis Yannakakis: Issues of Correctness in Database Concurrency Control by Locking. STOC 1981: 363-367 BibTeX

Referenced by

  1. Tadeusz Morzy: The Correctness of Concurrency Control for Multiversion Database Systems with Limited Number of Versions. ICDE 1993: 595-604
  2. Ada Wai-Chee Fu, Tiko Kameda: Concurrency Control of Nested Transactions Accessing B-Trees. PODS 1989: 270-285
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Tue Jun 24 18:39:02 2008