Document Open Access Logo

Robustness Against Read Committed for Transaction Templates with Functional Constraints

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

PDF
Thumbnail PDF

File

LIPIcs.ICDT.2022.16.pdf
  • Filesize: 0.83 MB
  • 17 pages

Document Identifiers

Author Details

Brecht Vandevoort
  • UHasselt, Data Science Institute, ACSL, Diepenbeek, Belgium
Bas Ketsman
  • Vrije Universiteit Brussel, Belgium
Christoph Koch
  • École Polytechnique Fédérale de Lausanne, Switzerland
Frank Neven
  • UHasselt, Data Science Institute, ACSL, Diepenbeek, Belgium

Funding

This work is funded by FWO-grant G019921N.

Cite As Get BibTex

Brecht Vandevoort, Bas Ketsman, Christoph Koch, and Frank Neven. Robustness Against Read Committed for Transaction Templates with Functional Constraints. In 25th International Conference on Database Theory (ICDT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 220, pp. 16:1-16:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ICDT.2022.16

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.

Subject Classification

ACM Subject Classification
  • Information systems → Database transaction processing
Keywords
  • concurrency control
  • robustness
  • complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

Supplementary Materials

References

  1. Atul Adya, Barbara Liskov, and Patrick E. O'Neil. Generalized isolation level definitions. In ICDE, pages 67-78, 2000. Google Scholar
  2. Mohammad Alomari, Michael Cahill, Alan Fekete, and Uwe Rohm. The cost of serializability on platforms that use snapshot isolation. In ICDE, pages 576-585, 2008. Google Scholar
  3. Mohammad Alomari and Alan Fekete. Serializable use of read committed isolation level. In AICCSA, pages 1-8, 2015. Google Scholar
  4. Sidi Mohamed Beillahi, Ahmed Bouajjani, and Constantin Enea. Checking robustness against snapshot isolation. In CAV, pages 286-304, 2019. Google Scholar
  5. Sidi Mohamed Beillahi, Ahmed Bouajjani, and Constantin Enea. Robustness against transactional causal consistency. In CONCUR, pages 1-18, 2019. Google Scholar
  6. Hal Berenson, Philip A. Bernstein, Jim Gray, Jim Melton, Elizabeth J. O'Neil, and Patrick E. O'Neil. A critique of ANSI SQL isolation levels. In SIGMOD, pages 1-10, 1995. Google Scholar
  7. Giovanni Bernardi and Alexey Gotsman. Robustness against consistency models with atomic visibility. In CONCUR, pages 7:1-7:15, 2016. Google Scholar
  8. Andrea Cerone, Giovanni Bernardi, and Alexey Gotsman. A framework for transactional consistency models with atomic visibility. In CONCUR, pages 58-71, 2015. Google Scholar
  9. Andrea Cerone and Alexey Gotsman. Analysing snapshot isolation. J.ACM, 65(2):1-41, 2018. Google Scholar
  10. Andrea Cerone, Alexey Gotsman, and Hongseok Yang. Algebraic Laws for Weak Consistency. In CONCUR, pages 26:1-26:18, 2017. Google Scholar
  11. Ashok K. Chandra and Moshe Y. Vardi. The implication problem for functional and inclusion dependencies is undecidable. SIAM J. Comput., 14(3):671-677, 1985. Google Scholar
  12. Alan Fekete. Allocating isolation levels to transactions. In PODS, pages 206-215, 2005. Google Scholar
  13. Alan Fekete, Dimitrios Liarokapis, Elizabeth J. O'Neil, Patrick E. O'Neil, and Dennis E. Shasha. Making snapshot isolation serializable. ACM Trans. Database Syst., 30(2):492-528, 2005. Google Scholar
  14. Bas Ketsman, Christoph Koch, Frank Neven, and Brecht Vandevoort. Deciding robustness for lower SQL isolation levels. In PODS, pages 315-330, 2020. Google Scholar
  15. Christos H. Papadimitriou. The Theory of Database Concurrency Control. Computer Science Press, 1986. Google Scholar
  16. Emil L. Post. A variant of a recursively unsolvable problem. Bull. Amer. Math. Soc., pages 264-268, 1946. Google Scholar
  17. Brecht Vandevoort, Bas Ketsman, Christoph Koch, and Frank Neven. Robustness against read committed for transaction templates. PVLDB, 14(11):2141-2153, 2021. Google Scholar
  18. Brecht Vandevoort, Bas Ketsman, Christoph Koch, and Frank Neven. Robustness against read committed for transaction templates with functional constraints (full version), 2022. URL: https://arxiv.org/abs/2201.05021.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact