Deciding Robustness for Lower SQL Isolation Levels

Bas Ketsman, Christoph Koch, Frank Neven, Brecht Vandevoort

Onderzoeksoutput: Conference paper

4 Citaten (Scopus)
85 Downloads (Pure)

Samenvatting

While serializability always guarantees application correctness, lower isolation levels can be chosen to improve transaction throughput at the risk of introducing certain anomalies. A set of transactions is robust against a given isolation level if every possible interleaving of the transactions under the specified isolation level is serializable. Robustness therefore always guarantees application correctness with the performance benefit of the lower isolation level. While the robustness problem has received considerable attention in the literature, only sufficient conditions have been obtained. The most notable exception is the seminal work by Fekete where he obtained a characterization for deciding robustness against SNAPSHOT ISOLATION. In this paper, we address the robustness problem for the lower SQL isolation levels READ UNCOMMITTED and READ COMMITTED which are defined in terms of the forbidden dirty write and dirty read patterns. The first main contribution of this paper is that we characterize robustness against both isolation levels in terms of the absence of counter example schedules of a specific form (split and multi-split schedules) and by the absence of cycles in interference graphs that satisfy various properties. A critical difference with Fekete's work, is that the properties of cycles obtained in this paper have to take the relative ordering of operations within transactions into account as READ UNCOMMITTED and READ COMMITTED do not satisfy the atomic visibility requirement. A particular consequence is that the latter renders the robustness problem against READ COMMITTED coNP-complete. The second main contribution of this paper is the coNP-hardness proof. For READ UNCOMMITTED, we obtain LOGSPACE-completeness.

Originele taal-2English
TitelProceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems
UitgeverijACM
Pagina's315-330
Aantal pagina's16
ISBN van elektronische versie9781450371087
DOI's
StatusPublished - 14 jun 2020
Evenement39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems - Online - due to COVID, Portland, United States
Duur: 14 jun 202019 jun 2020
https://sigmod2020.org/

Publicatie series

NaamProceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems

Conference

Conference39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems
Verkorte titelPODS'20
LandUnited States
StadPortland
Periode14/06/2019/06/20
Internet adres

Vingerafdruk

Duik in de onderzoeksthema's van 'Deciding Robustness for Lower SQL Isolation Levels'. Samen vormen ze een unieke vingerafdruk.

Citeer dit