Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
T. Hadzilacos and C. H. Papadimitriou, Algorithmic Aspects of Multiversion Concurrency Control,Proc. ACM Symp. Principles of Database Systems, pp. 96–104 (1985).
S. Muro, T. Kameda, and T. Minoura, Multiversion Concurrency Control Scheme for a Database System,J. Comput. System Sci. 29:207–224 (1984).
C. H. Papadimitriou and P. C. Kanellakis, On Concurrency Control by Multiple Versions,ACM Trans. Database Systems,9:89–99 (1984).
C. H. Papadimitriou and M. Yannakakis, The Complexity of Reliable Concurrency Control,Proc. ACM Symp. Principles of Database Systems, pp. 230–234 (1985).
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).
K. Vidyasankar, Generalized Theory of Serializability, Department of Computer Science, Memorial University, St. John's, Newfoundland, Canada, Tech. Report No. 8510 (May 1985).
M. Yannakakis, Serializability by Locking,J. ACM,31: 227–244 (1984).
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).
C. H. Papadimitriou, The Serializability of Concurrent Database Updates,J. ACM,26:631–653 (1979).
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).
P. A. Bernstein and N. Goodman, Multiversion Concurrency Control-Theory and Algorithms,ACM Trans. Database Systems,8:465–483 (1983).
J. A. Brzozowski, On Models of Transactions, Department of Applied Mathematics and Physics, Kyoto University, Kyoto, Japan, Tech. Report No. 84001 (April 1984).
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).
J. A. Brzozowski and S. Muro, On Serializability, Department of Applied Mathematics and Physics, Kyoto University, Kyoto, Japan, Tech. Report No. 84012 (July 1984).
Author information
Authors and Affiliations
Additional information
This research was supported in part by a Japan Society for the Promotion of Science Research Fellowship, in part by a Scientific Research Grant-in-Aid from the Ministry of Education, Science and Culture of Japan, and in part by the Natural Science and Engineering Research Council of Canada under Grant No. A1617. Most of this work was done when the first author was a Visiting Professor in the Department of Applied Mathematics and Physics, Kyoto University, Kyoto, Japan.
Rights and permissions
About this article
Cite this article
Brzozowski, J.A., Muro, S. On serializability. International Journal of Computer and Information Sciences 14, 387–403 (1985). https://doi.org/10.1007/BF00991181
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF00991181