Let MC stand for a class of logs (i.e., sequences of read/write steps) that are serializable when multiple versions of the data items are maintained in the database. In this paper the authors propose a new type of multiversion cautions scheduler for database concurrency control, which dynamically imposes serialization constraints, consisting of all rw(read-write)-constraints and a subset of other serialization constriants that is dynamically determined. The authors shall show that (i) the key step of the present scheduler is carried out by checking the acyclicity of a certain directed graph, and hence can be done in polynomial time, (ii) this scheduler achieves a higher degree of concurrency than any existing cautious schedulers such as MCS(MWW) and MCS(MWRW), if concurrency is measured in terms of their fixed point sets, and (iii) it exhibits neither cancellation or augmentation anomaly. It is also shown that the scheduler immediately grants all write requests.
