Abstract
The main results of this paper show that serialization is both necessary and sufficient for consistency in concurrent database systems. This is true for both the final database and the views of the database seen by individual transactions. The model of a transaction includes both read and write operations which may be performed in any order (except an entity must be read before being written).
The main results are presented in terms of an information flow model describing the source of each value read and the use of each value written. Since the model does not involve any concept of the “time” a value was read or written, it models any concurrency system producing information flow among transactions.
There is a section discussing the effect of changing the model to include write operations without preceding reads, and a section discussing the restriction to straight-line programs.
The research of this author was supported in part by the National Science Foundation under grant MCS 78-03157.
The research of this author was supported in part by the National Science Foundation under grant MCS 79-03770.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
R. Bayer, E. Elhardt, H. Heller, and A. Reiser. Distributed concurrency control in database systems. In Proc. Sixth International Conference on Very Large Data Bases, pages 275–284, Montreal, Oct. 1980.
R. Bayer, H. Heller, and A. Reiser. Parallelism and recovery in database systems. ACM Trans. Database Systems, 5:139–156, 1980.
M. A. Casanova. The Concurrency Control Problem for Database Systems. Lecture Notes in Computer Science, volume 116. Springer, Berlin, 1981.
M. A. Casanova and P. A. Bernstein. General purpose schedules for database systems. Acta Inform., 14:195–220, 1980.
K. P. Eswaran, J. N. Gray, R. A. Lorie, and I. L. Traiger. The notions of consistency and predicate locks in a database system. Comm. ACM, 19(11):624–633, 1976.
G. Gardarin. Contributions to the theory of concurrency in databases. In J. Winkowski, editor, Mathematical Foundations of Computer Science. Lecture Notes in Computer Science, volume 64, pages 201–212. Springer, Berlin, 1978.
G. Gardarin and P. Lebeux. Scheduling algorithms for avoiding inconsistency in large databases. In Proc. Third International Conference on Very Large Data Bases, pages 501–506, Tokyo, 1977.
G. Gardarin and M. Melkanoff. Proving consistency of database transactions. In Proc. Fifth International Conference on Very Large Data Bases, pages 291–298, Rio de Janeiro, Oct. 1979.
J. N. Gray, R. A. Lorie, G. R. Putzolu, and I. L. Traiger. Granularity of locks and degrees of consistency in a shared data base. In G. M. Nijssen, editor, Modelling in Data Base Management Systems, pages 365–394. North-Holland, Amsterdam, 1976.
H. T. Kung and C. H. Papadimitriou. An optimality theory of concurrency control for databases. In Proc. SIGMOD International Conference on Management of Data, pages 116–126, Boston, MA, May 1979.
L. Lamport. Towards a theory of correctness for multi-user data base systems. Technical Report CA-7610-0712, Mass. Comput. Assoc. Inc., Oct. 1976.
Z. Manna. Mathematical Theory of Computation. McGraw–Hill, New York, 1974.
D. P. Reed. Naming and synchronization in a decentralized computer system. Technical Report MIT/LCS/TR-205, Dept. of Electrical Engineering and Computer Science, Massachusetts Inst. of Technology, Cambridge, MA, Sept. 1978. (Ph.D. thesis).
R. E. Stearns and D. J. Rosenkrantz. Distributed database concurrency controls using before values. In Proc. SIGMOD International Conference on Management of Data, pages 74–83, Ann Arbor, MI, Apr. 1981.
R. E. Stearns, P. M. Lewis II, and D. J. Rosenkrantz. Concurrency controls for database systems. In Proc. 17th Annual Symp. on Foundations of Comptr. Sci., pages 19–32, Houston, TX, 1976.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer Science + Business Media B.V.
About this chapter
Cite this chapter
Rosenkrantz, D.J., Stearns, R.E., Lewis, P.M. (2009). Consistency and serializability in concurrent database systems. In: Ravi, S.S., Shukla, S.K. (eds) Fundamental Problems in Computing. Springer, Dordrecht. https://doi.org/10.1007/978-1-4020-9688-4_5
Download citation
DOI: https://doi.org/10.1007/978-1-4020-9688-4_5
Publisher Name: Springer, Dordrecht
Print ISBN: 978-1-4020-9687-7
Online ISBN: 978-1-4020-9688-4
eBook Packages: Computer ScienceComputer Science (R0)