Disjoint-Interval Topological Sort: A Useful Concept in Serializability Theory (Extended Abstract).

Toshihide Ibaraki, Tiko Kameda, Toshimi Minoura: Disjoint-Interval Topological Sort: A Useful Concept in Serializability Theory (Extended Abstract). VLDB 1983: 89-91
  author    = {Toshihide Ibaraki and
               Tiko Kameda and
               Toshimi Minoura},
  editor    = {Mario Schkolnick and
               Costantino Thanos},
  title     = {Disjoint-Interval Topological Sort: A Useful Concept in Serializability
               Theory (Extended Abstract)},
  booktitle = {9th International Conference on Very Large Data Bases, October
               31 - November 2, 1983, Florence, Italy, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1983},
  isbn      = {0-934613-15-X},
  pages     = {89-91},
  ee        = {db/conf/vldb/IbarakiKM83.html},
  crossref  = {DBLP:conf/vldb/83},
  bibsource = {DBLP,}


The theory of serializability for concurrency control of databases has been extensively studied [ESWA-76, STEA-76, BERN-79, PAPA-79, SETH-81].

In this paper, we introduce a unifying concept in the theory, called disjoint-interval topological sort (DITS, for short), and discuss its applications, including a number of new results.

We prove that the existence of a DITS for the transaction IO graph (Section 3) associated with a schedule is a necessary and sufficient condition for serializability. The notion of DITS captures the essence of serializability and most known results on the characterization of serializable schedules follow directly from this main theorem. The most important contributions of the DITS are its appeal to intuition and its wide applicability. It is not only useful as an analysis toll, as we demontstrate in this paper, but it also provides a useful aid to a scheduler [KATO-83]. The concept of DITS can be easily extended to the multi-version case [STEA-76, REED-79, MURO-81, BERN-82, PAPA-82, IBAR-83].

We demonstrate a class of schedules, called WR+RW (see Section 5), which is the largest class of serializable schedules currently known that is polynomially recognizable. We also state some NP-completeness results.

Copyright © 1983 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Online Paper

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

Mario Schkolnick, Costantino Thanos (Eds.): 9th International Conference on Very Large Data Bases, October 31 - November 2, 1983, Florence, Italy, Proceedings. Morgan Kaufmann 1983, ISBN 0-934613-15-X
Contents BibTeX


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
Arthur J. Bernstein, Nathan Goodman: Concurrency Control Algorithms for Multiversion Database Systems. PODC 1982: 209-215 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
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. PODS 1982: 76-82 BibTeX
David P. Reed: Implementing Atomic Actions on Decentralized Data. SOSP 1979: 163 BibTeX
Ravi Sethi: A model of concurrent database transactions (summary). FOCS 1981: 175-184 BibTeX
Richard Edwin Stearns, Philip M. Lewis II, Daniel J. Rosenkrantz: Concurrency Control for Database Systems. FOCS 1976: 19-32 BibTeX

Referenced by

  1. Toshihide Ibaraki, Tiko Kameda, Toshimi Minoura: Serializability with Constraints. ACM Trans. Database Syst. 12(3): 429-452(1987)
  2. Naoki Katoh, Toshihide Ibaraki, Tiko Kameda: Cautious Transaction Schedulers with Admission Control. ACM Trans. Database Syst. 10(2): 205-229(1985)
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:45:18 2009