A cautious scheduler for multistep transactions (Q1101210): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 03:11, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A cautious scheduler for multistep transactions |
scientific article |
Statements
A cautious scheduler for multistep transactions (English)
0 references
1987
0 references
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.
0 references
database systems
0 references
concurrency control
0 references
serializability
0 references
cautious schedulers
0 references
transaction scheduler
0 references
scheduling
0 references
NP-complete
0 references