Robustness against Read Committed for Transaction Templates with Functional Constraints

DOI10.46298/LMCS-19(4:39)2023MaRDI QIDQ6137875zbMATH OpenOpenAlexFDO

Authors Brecht Vandevoort, Bas Ketsman, Christoph Koch, Frank Neven

Publication date 16 January 2024

Published in Logical Methods in Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2201.05021

zbMATH Keywords

robustnesscomplexityconcurrency control

Mathematics Subject Classification ID

Logic in computer science (03B70) Computer science (68-XX)

Abstract: The popular isolation level Multiversion Read Committed (RC) trades some of the strong guarantees of serializability for increased transaction throughput. Sometimes, transaction workloads can be safely executed under RC obtaining serializability at the lower cost of RC. Such workloads are said to be robust against RC. Previous work has yielded a tractable procedure for deciding robustness against RC for workloads generated by transaction programs modeled as transaction templates. An important insight of that work is that, by more accurately modeling transaction programs, we are able to recognize larger sets of workloads as robust. In this work, we increase the modeling power of transaction templates by extending them with functional constraints, which are useful for capturing data dependencies like foreign keys. We show that the incorporation of functional constraints can identify more workloads as robust that otherwise would not be. Even though we establish that the robustness problem becomes undecidable in its most general form, we show that various restrictions on functional constraints lead to decidable and even tractable fragments that can be used to model and test for robustness against RC for realistic scenarios.

Recommendations

• Checking robustness between weak transactional consistency models
• Checking robustness against snapshot isolation
• Robustness Against Transactional Causal Consistency.
• scientific article; zbMATH DE number 7327945
• Robustness against consistency models with atomic visibility

Cites work

• scientific article; zbMATH DE number 3986679 (Why is no real title available?)
• A framework for transactional consistency models with atomic visibility
• A variant of a recursively unsolvable problem
• Algebraic laws for weak consistency
• Analysing snapshot isolation
• Robustness Against Transactional Causal Consistency.
• Robustness against consistency models with atomic visibility
• The Implication Problem for Functional and Inclusion Dependencies is Undecidable

This page was built for publication: Robustness against Read Committed for Transaction Templates with Functional Constraints

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