Multiversion cautious schedulers for database concurrency control

摘要

Let MC stand for a class of logs (i.e. sequences of read/write steps of transactions) that are serializable when multiple versions of the data items are maintained. The multiversion cautious scheduler, MCS(MC) which is introduced, outputs a sequence belonging to MC by reordering, if necessary, the incoming sequence of requests from transactions and it never resorts to rollbacks. In the model, transactions on arrival predeclare their read sets and write sets. It is shown that MCS(MWW) and MCS(MWRW) can be executed in polynomial time, where MWW and MWRW are multiversion classes of logs serializable under the write-write and write-read-write constraints respectively. For any multiversion class MC of interest, MCS(MC) does not exhibit cancellation anomaly, i.e. it functions correctly even if some of the predeclared steps are canceled. Furthermore, MCS(MWW) functions correctly, even if transactions issue more read operations than they predeclared. Thus, MCS(MWW) allows each transaction to predeclare only its write set.