ISSN:
1432-0541
Keywords:
Database systems
;
Concurrency control
;
Serialized ability
;
Transaction scheduler
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract 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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01840347
Permalink
