Cautious transaction schedulers with admission control
Naoki Katoh, Toshihide Ibaraki, Tiko Kameda · ACM Transactions on Database Systems · 1985
We propose a new class of schedulers, called cautious schedulers , that grant an input request if it will not necessitate any rollback in the future. In particular, we investigate cautious WRW-schedulers that output schedules in class WRW only. Class WRW consists of all schedules that are serializable, while preserving the write-read and read-write conflict, and is the largest polynomially recognizable subclass of serializable schedules currently known. It is shown, in this paper however, that cautious WRW- scheduling is, in general, NP-complete. Therefore, we introduce a special type ( type 1R ) of transaction, which consists of no more than one read step (an indivisible set of read operations) followed by multiple write steps. It is shown that cautious WRW-scheduling can be performed efficiently if all transactions are of type 1R and if admission control can be exercised. Admission control rejects a transaction unless its first request is immediately grantable.