License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICDT.2022.16
URN: urn:nbn:de:0030-drops-158905
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15890/
Go to the corresponding LIPIcs Volume Portal

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

Robustness Against Read Committed for Transaction Templates with Functional Constraints

pdf-format:
LIPIcs-ICDT-2022-16.pdf (0.8 MB)

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.

BibTeX - Entry

@InProceedings{vandevoort_et_al:LIPIcs.ICDT.2022.16,
  author =	{Vandevoort, Brecht and Ketsman, Bas and Koch, Christoph and Neven, Frank},
  title =	{{Robustness Against Read Committed for Transaction Templates with Functional Constraints}},
  booktitle =	{25th International Conference on Database Theory (ICDT 2022)},
  pages =	{16:1--16:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-223-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{220},
  editor =	{Olteanu, Dan and Vortmeier, Nils},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/15890},
  URN =		{urn:nbn:de:0030-drops-158905},
  doi =		{10.4230/LIPIcs.ICDT.2022.16},
  annote =	{Keywords: concurrency control, robustness, complexity}
}

Keywords: concurrency control, robustness, complexity
Collection: 25th International Conference on Database Theory (ICDT 2022)
Issue Date: 2022
Date of publication: 19.03.2022
Supplementary Material: Audiovisual (Video of the Presentation): https://doi.org/10.5446/57484

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI