A cautious scheduler for multistep transactions

DOI10.1007/BF01840347MaRDI QIDQ1101210zbMATH OpenOpenAlexFDO

Authors Naoki Katoh, Tiko Kameda, Toshihide Ibaraki

Publication date 1987

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01840347

zbMATH Keywords

cautious schedulersconcurrency controldatabase systemsNP-completeschedulingserializabilitytransaction scheduler

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Information storage and retrieval of data (68P20)

Review text

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.

Recommendations

• Cautious transaction schedulers with admission control
• Data and Applications Security XIX
• Scheduling transactions with strigent real-time constraints
• Stable scheduling in transactional memory

Cites work

• A theorem in database concurrency control
• Cautious transaction schedulers with admission control
• Formal Aspects of Serializability in Database Concurrency Control
• General purpose schedulers for database systems
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• The concurrency control problem for database systems
• The serializability of concurrent database updates
• Useless Actions Make a Difference

Cited in

(2)

• A multiversion cautious scheduler with dynamic serialization constraints for database concurrency control
• Cautious transaction schedulers with admission control

This page was built for publication: A cautious scheduler for multistep transactions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1101210)