A cautious scheduler for multistep transactions

Given a classC of serializable schedules, a cautiousC-scheduler is an on-line transaction scheduler that outputs schedules in classC 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 inC. 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 inC, then the current request is delayed. An efficient cautiousCPSR-scheduler has been proposed by Casanova and Bernstein.This paper discusses cautiousWRW-scheduling, whereWRW is the largest polynomially recognizable subclass of serializable schedules currently known. Since cautiousWRW-scheduling is, in general, NP-complete as shown in this paper, we introduce, a subclass (namedWRW^#) ofWRW and discuss an efficient cautiousWRW^#-scheduler. We also show that the fixed point set of the cautiousWRW^#-scheduler properly containsCPSR. Therefore, ourWRW^#-scheduler allows more concurrency than anyCPSR- scheduler.This work was supported in part by the Natural Sciences and Engineering Research Council of Canada under Grant No. A5240 and in part by the Ministry of Education, Science and Culture of Japan under Scientific Research Grant-in-Aid.