Cautious transaction schedulers for database concurrency control

摘要

Cautious schedulers, which never resort to rollbacks for the purpose of concurrency control, are investigated. In particular, cautious schedulers for classes WW consisting of schedules serializable under the write-write constraints, and WRW, a superclass of W, are considered. The cautious WW-scheduler has a number of nice properties, one of which is the existence of a polynomial-time scheduling algorithm. Since cautious WRW-scheduling is, in general, NP-complete, some restrictions are introduced which allow polynomial-time scheduling. All of these cautious schedulers are based on the assumption that transaction predeclare their read and write sets on arrival. Anomalies which occur when transaction modify their read sets or write sets during execution are discussed and countermeasures are proposed.