×
Brzozowski, J. A.; Muro, S.

On serializability. (English) Zbl 0602.68092

Int. J. Comput. Inform. Sci. 14, No. 6, 387-403 (1985).
Concurrent execution of database transactions is desirable from the point of view of speed, but may introduce inconsistencies. A commonly used criterion of correctness of a concurrent execution of transactions is serializability, i.e., the equivalence of the execution to some serial schedule or schedules. In the literature several transaction models have been used and several different notions of serializability have been introduced. In this paper, we investigate the various serializability families in the general transaction model, in the two-step model, and in the restricted two-step model. We also examine these families in the multiversion database model.

Cited in 1 Document

MSC:

68P20 Information storage and retrieval of data

Keywords:

concurrency; families of schedules; database transactions; concurrent execution
Cite Review PDF
Full Text: DOI

References:

[1] T. Hadzilacos and C. H. Papadimitriou, Algorithmic Aspects of Multiversion Concurrency Control,Proc. ACM Symp. Principles of Database Systems, pp. 96?104 (1985). · Zbl 0625.68082
[2] S. Muro, T. Kameda, and T. Minoura, Multiversion Concurrency Control Scheme for a Database System,J. Comput. System Sci. 29:207?224 (1984). · Zbl 0547.68093 · doi:10.1016/0022-0000(84)90031-X
[3] C. H. Papadimitriou and P. C. Kanellakis, On Concurrency Control by Multiple Versions,ACM Trans. Database Systems,9:89?99 (1984). · Zbl 0547.68092 · doi:10.1145/348.318588
[4] C. H. Papadimitriou and M. Yannakakis, The Complexity of Reliable Concurrency Control,Proc. ACM Symp. Principles of Database Systems, pp. 230?234 (1985). · Zbl 0654.68034
[5] A. Tuzhilin and P. Spirakis, A Semantic Approach to Correctness of Concurrent Transaction Executions,Proc. ACM Symp. Principles of Database Systems, pp. 85?95 (1985).
[6] K. Vidyasankar, Generalized Theory of Serializability, Department of Computer Science, Memorial University, St. John’s, Newfoundland, Canada, Tech. Report No. 8510 (May 1985).
[7] M. Yannakakis, Serializability by Locking,J. ACM,31: 227?244 (1984). · Zbl 0631.68078 · doi:10.1145/62.322425
[8] K. P. Eswaran, J. N. Gray, R. A. Lorie, and I. L. Traiger, The Notion of Consistency and Predicate Locks in a Database System,Comm. ACM 19:624?633 (1976). · Zbl 0341.68023 · doi:10.1145/360363.360369
[9] C. H. Papadimitriou, The Serializability of Concurrent Database Updates,J. ACM,26:631?653 (1979). · Zbl 0419.68036 · doi:10.1145/322154.322158
[10] R. E. Stearns, P. M. Lewis II, and D. J. Rosenkrantz, Concurrency Control for Database Systems,Proc. 17th Symp. Foundations of Computer Science, pp. 19?32 (1976).
[11] P. A. Bernstein and N. Goodman, Multiversion Concurrency Control-Theory and Algorithms,ACM Trans. Database Systems,8:465?483 (1983). · Zbl 0531.68060 · doi:10.1145/319996.319998
[12] J. A. Brzozowski, On Models of Transactions, Department of Applied Mathematics and Physics, Kyoto University, Kyoto, Japan, Tech. Report No. 84001 (April 1984).
[13] T. Ibaraki and T. Kameda, Multiversion vs. Single-Version Serializability, Laboratory for Computer and Communication Research, Simon Fraser University, Burnaby, B. C., Canada, Tech. Report No. 83-1 (1983).
[14] J. A. Brzozowski and S. Muro, On Serializability, Department of Applied Mathematics and Physics, Kyoto University, Kyoto, Japan, Tech. Report No. 84012 (July 1984).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.