Serializability with Constraints.

@article{DBLP:journals/tods/IbarakiKM87,
  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        = {http://doi.acm.org/10.1145/27629.214284, db/journals/tods/IbarakiKM87.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

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

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/An3-1 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD2 or /dvd

References

[1]

Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley 1974, ISBN 0-201-00029-6
BibTeX

[2]

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

[3]

Philip A. Bernstein, Nathan Goodman: Multiversion Concurrency Control - Theory and Algorithms. ACM Trans. Database Syst. 8(4): 465-483(1983) BibTeX

[4]

...

[5]

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

[6]

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
BibTeX

[7]

Thanasis Hadzilacos, Christos H. Papadimitriou: Algorithmic Aspects of Multiversion Concurrency Control. PODS 1985: 96-104 BibTeX

[8]

...

[9]

...

[10]

Toshihide Ibaraki, Tiko Kameda, Toshimi Minoura: Disjoint-Interval Topological Sort: A Useful Concept in Serializability Theory (Extended Abstract). VLDB 1983: 89-91 BibTeX

[11]

...

[12]

Toshihide Ibaraki, Tiko Kameda, Naoki Katoh: Cautious Transaction Schedulers for Database Concurrency Control. IEEE Trans. Software Eng. 14(7): 997-1009(1988) BibTeX

[13]

Naoki Katoh, Toshihide Ibaraki, Tiko Kameda: Cautious Transaction Schedulers with Admission Control. ACM Trans. Database Syst. 10(2): 205-229(1985) BibTeX

[14]

Naoki Katoh, Tiko Kameda, Toshihide Ibaraki: A Cautious Scheduler for Multistep Transactions. Algorithmica 2: 1-26(1987) BibTeX

[15]

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

[16]

Christos H. Papadimitriou: The serializability of concurrent database updates. J. ACM 26(4): 631-653(1979) BibTeX

[17]

Christos H. Papadimitriou, Paris C. Kanellakis: On Concurrency Control by Multiple Versions. ACM Trans. Database Syst. 9(1): 89-99(1984) BibTeX

[18]

Ravi Sethi: A model of concurrent database transactions (summary). FOCS 1981: 175-184 BibTeX

[19]

Ravi Sethi: Useless Actions Make a Difference: Strict Serializability of Database Updates. J. ACM 29(2): 394-403(1982) BibTeX

[20]

Richard Edwin Stearns, Philip M. Lewis II, Daniel J. Rosenkrantz: Concurrency Control for Database Systems. FOCS 1976: 19-32 BibTeX

[21]

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