A cautious scheduler for multistep transactions (Q1101210)

Given a class C of serializable schedules, a cautious C-scheduler is an on-line transaction scheduler that outputs schedules in class C and never resorts to rollbacks. Such a scheduler grants the current request if and only if the partial schedule it has granted so far, followed by the current request, can be extended to a schedule in C. A suitable extension is searched among the set of all possible sequences of the pending steps, which are predeclared by the transactions whose first requests have already arrived. If the partial schedule cannot be extended to a schedule in C, then the current request is delayed. An efficient cautious CPSR- scheduler has been proposed by \textit{M. A. Casanova} and \textit{Ph. A. Bernstein} [Acta Inf. 14, 195-220 (1980; Zbl 0419.68080)]. This paper discusses cautious WRW-scheduling, where WRW is the largest polynomially recognizable subclass of serializable schedules currently known. Since cautious WRW-scheduling is, in general, NP-complete as shown in this paper, we introduce a subclass (named \(WRW^{\#})\) of WRW and discuss an efficient cautious \(WRW^{\#}\)-scheduler. We also show that the fixed point set of the cautions \(WRW^{\#}\)-scheduler properly contains CPSR. Therefore, our \(WRW^{\#}\)-scheduler allows more concurrency than any CPSR-scheduler.