ACM SIGMOD Anthology VLDB dblp.uni-trier.de

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
@inproceedings{DBLP:conf/vldb/IbarakiKM83,
  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, http://dblp.uni-trier.de}
}

Abstract

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

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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BERN-82]
Arthur J. Bernstein, Nathan Goodman: Concurrency Control Algorithms for Multiversion Database Systems. PODC 1982: 209-215 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[ESWA-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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[IBAR-82]
...
[IBAR-83]
...
[KATO-83]
...
[MURO-81]
Shojiro Muro, Tiko Kameda, Toshimi Minoura: Multi-version Concurrency Control Scheme for a Database System. J. Comput. Syst. Sci. 29(2): 207-224(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[PAPA-79]
Christos H. Papadimitriou: The serializability of concurrent database updates. J. ACM 26(4): 631-653(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[PAPA-82]
Christos H. Papadimitriou, Paris C. Kanellakis: On Concurrency Control by Multiple Versions. PODS 1982: 76-82 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[REED-79]
David P. Reed: Implementing Atomic Actions on Decentralized Data. SOSP 1979: 163 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SETH-81]
Ravi Sethi: A model of concurrent database transactions (summary). FOCS 1981: 175-184 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[STEA-76]
Richard Edwin Stearns, Philip M. Lewis II, Daniel J. Rosenkrantz: Concurrency Control for Database Systems. FOCS 1976: 19-32 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Tue Mar 16 02:21:57 2010 by Michael Ley (ley@uni-trier.de)