Obtaining Progressive Protocols for a Simple Multiversion Database Model

MO>! database systems ensure the consistency of the data by means of a concurrency control scheme that USE a polynomial time on-line scheduler. Papadimirrlou and Kanellakis have shown that for the most general multiversion database model no such effective scheduler exists. In this paper we focus our attention 0 ~ an efficient multiversion database model and derive necessary and sufficient conditions for ensuring serializability and serializability without the use of transaction rollback for this model. It is shown that both t,hese classes yield additional concurrency through t.he use of mu!tiple versions. This characterization is used to derive the first general multiversion protocol which does not use transaction rollback as a means for ensuring serializability.