A cautious scheduler for multistep transactions (Q1101210): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Formal Aspects of Serializability in Database Concurrency Control / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: General purpose schedulers for database systems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The concurrency control problem for database systems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4198056 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Cautious transaction schedulers with admission control / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The serializability of concurrent database updates / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A theorem in database concurrency control / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Useless Actions Make a Difference / rank | |||
Normal rank |
Latest revision as of 16:53, 18 June 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