Consistency and Serializability in Concurrent Database Systems
Daniel J. Rosenkrantz, Richard Edwin Stearns, Philip Lewis · SIAM Journal on Computing · 1984
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.