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