Algorithmic aspects of multiversion concurrency control

DOI10.1016/0022-0000(86)90022-XMaRDI QIDQ579971zbMATH OpenFDO

Authors Thanasis Hadzilacos, Christos Papadimitriou

Publication date 1986

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0022-0000(86)90022-X

zbMATH Keywords

conflict serializabilitydatabase concurrency controlmultiversion serializabilityscheduling

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

Multiversion schedulers are now a widely accepted method for enhancing the performance of the concurrency control component of a database. In this paper we introduce a new notion of multiversion serializability (MVSR) based on conflicts (MVCSR), and discuss its relation with the well known single version conflict serializability (CSR). On-line schedulable (OLS) subsets of (MVSR) were defined by the second author and \textit{P. C. Kanellakis} [ACM Trans. Database Syst. 9, 89-99 (1984; Zbl 0547.68092)]. We prove there that it is NP-complete to decide whether a set of schedules is OLS. We next introduce the concept of maximal OLS sets, and show that no efficient scheduler can be designed that recognizes maximal subsets of the MVSR or MVCSR schedules.

Recommendations

• Multiversion concurrency control—theory and algorithms
• On Concurrency Control by Multiple Versions
• scientific article; zbMATH DE number 3915662
• Multi-version concurrency control scheme for a database system
• The Complexity of Reliable Concurrency Control

Cites work

• Algorithmic aspects of multiversion concurrency control
• scientific article; zbMATH DE number 3986679 (Why is no real title available?)
• Multiversion concurrency control—theory and algorithms
• On Concurrency Control by Multiple Versions
• Parallelism and recovery in database systems
• The serializability of concurrent database updates

Cited in

(10)

• Hybrid concurrency control for abstract data types
• On-line multiversion database concurrency control
• Key factors for improving performance of concurrency control algorithms
• Concurrency control by transactions carrying states and preordering multiversioned entities
• On Concurrency Control by Multiple Versions
• Cautious transaction schedulers with admission control
• On serializability
• scientific article; zbMATH DE number 2090608 (Why is no real title available?)
• Algorithmic aspects of multiversion concurrency control
• A conservative multiversion locking-graph scheduler algorithm

This page was built for publication: Algorithmic aspects of multiversion concurrency control

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