Algorithmic aspects of multiversion concurrency control (Q579971)

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.