{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:48:15Z","timestamp":1750308495125,"version":"3.41.0"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2025,5,14]],"date-time":"2025-05-14T00:00:00Z","timestamp":1747180800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"FWO","award":["G019921N"],"award-info":[{"award-number":["G019921N"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2025,6,30]]},"abstract":"<jats:p>A serializable concurrency control mechanism ensures consistency for OLTP systems at the expense of a reduced transaction throughput. A DBMS, therefore usually offers the possibility to allocate lower isolation levels for some transactions when it is safe to do so. However, such trading of consistency for efficiency does not come with any safety guarantees. In this article, we study the mixed robustness problem which asks whether, for a given set of transactions and a given allocation of isolation levels, every possible interleaved execution of those transactions that is allowed under the provided allocation is always serializable. That is, whether the given allocation is indeed safe. While robustness has already been studied in the literature for the homogeneous setting where all transactions are allocated the same isolation level, the heterogeneous setting that we consider in this article, despite its practical relevance, has largely been ignored. We focus on multiversion concurrency control and consider the isolation levels that are available in PostgreSQL and Oracle: read committed (RC), snapshot isolation (SI), and serializable snapshot isolation (SSI). We show that the mixed robustness problem can be decided in polynomial time. In addition, we provide a polynomial time algorithm for computing the optimal robust allocation for a given set of transactions, prioritizing lower over higher isolation levels. The present results therefore establish the groundwork to automate isolation level allocation within existing databases supporting multiversion concurrency control.<\/jats:p>","DOI":"10.1145\/3716374","type":"journal-article","created":{"date-parts":[[2025,4,8]],"date-time":"2025-04-08T11:33:07Z","timestamp":1744111987000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Allocating Isolation Levels to Transactions in a Multiversion Setting"],"prefix":"10.1145","volume":"50","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7212-4625","authenticated-orcid":false,"given":"Brecht","family":"Vandevoort","sequence":"first","affiliation":[{"name":"Data Science Institute, ACSL, UHasselt, Diepenbeek, Belgium"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4032-0709","authenticated-orcid":false,"given":"Bas","family":"Ketsman","sequence":"additional","affiliation":[{"name":"Vrije Universiteit Brussel, Brussel, Belgium"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7143-1903","authenticated-orcid":false,"given":"Frank","family":"Neven","sequence":"additional","affiliation":[{"name":"Data Science Institute, ACSL, UHasselt, Diepenbeek, Belgium"}]}],"member":"320","published-online":{"date-parts":[[2025,5,14]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.5555\/930194"},{"key":"e_1_3_3_3_2","first-page":"67","volume-title":"Proceedings of the 16th International Conference on Data Engineering","author":"Adya Atul","year":"2000","unstructured":"Atul Adya, Barbara Liskov, and Patrick E. O\u2019Neil. 2000. Generalized isolation level definitions. In Proceedings of the 16th International Conference on Data Engineering. 67\u201378."},{"key":"e_1_3_3_4_2","first-page":"1","volume-title":"Proceedings of the 2013 ACS International Conference on Computer Systems and Applications","author":"Alomari Mohammad","year":"2013","unstructured":"Mohammad Alomari. 2013. Serializable executions with Snapshot Isolation and two-phase locking: Revisited. In Proceedings of the 2013 ACS International Conference on Computer Systems and Applications. 1\u20138."},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497466"},{"key":"e_1_3_3_6_2","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1007\/978-3-540-78568-2_21","volume-title":"Database Systems for Advanced Applications: 13th International Conference, DASFAA 2008, New Delhi, India, March 19-21, 2008. Proceedings 13","author":"Alomari Mohammad","year":"2008","unstructured":"Mohammad Alomari, Michael J. Cahill, Alan D. Fekete, and Uwe R\u00f6hm. 2008. Serializable executions with snapshot isolation: Modifying application code or mixing isolation levels?. In Database Systems for Advanced Applications: 13th International Conference, DASFAA 2008, New Delhi, India, March 19-21, 2008. Proceedings 13. 267\u2013281."},{"key":"e_1_3_3_7_2","first-page":"1","volume-title":"Proceedings of the 2015 IEEE\/ACS 12th International Conference of Computer Systems and Applications","author":"Alomari Mohammad","year":"2015","unstructured":"Mohammad Alomari and Alan Fekete. 2015. Serializable use of read committed isolation level. In Proceedings of the 2015 IEEE\/ACS 12th International Conference of Computer Systems and Applications. 1\u20138."},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.22"},{"key":"e_1_3_3_9_2","doi-asserted-by":"crossref","unstructured":"Peter Alvaro and Kyle Kingsbury. 2020. Elle: Inferring isolation anomalies from experimental observations. Proceedings of the VLDB Endowment 14 3 (2020) 268\u2013280.","DOI":"10.14778\/3430915.3430918"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.14778\/2732232.2732237"},{"key":"e_1_3_3_11_2","doi-asserted-by":"crossref","first-page":"286","DOI":"10.1007\/978-3-030-25543-5_17","volume-title":"Computer Aided Verification: 31st International Conference, CAV 2019, New York City, NY, USA, July 15-18, 2019, Proceedings, Part II 31","author":"Beillahi Sidi Mohamed","year":"2019","unstructured":"Sidi Mohamed Beillahi, Ahmed Bouajjani, and Constantin Enea. 2019. Checking robustness against snapshot isolation. In Computer Aided Verification: 31st International Conference, CAV 2019, New York City, NY, USA, July 15-18, 2019, Proceedings, Part II 31. 286\u2013304."},{"key":"e_1_3_3_12_2","unstructured":"Sidi Mohamed Beillahi Ahmed Bouajjani and Constantin Enea. 2019. Robustness against transactional causal consistency. In Proceedings of the 30th International Conference on Concurrency Theory. 1\u201318."},{"key":"e_1_3_3_13_2","first-page":"1","volume-title":"ACM SIGMOD Record 24, 2 (1995),","author":"Berenson Hal","year":"1995","unstructured":"Hal Berenson, Philip A. Bernstein, Jim Gray, Jim Melton, Elizabeth J. O\u2019Neil, and Patrick E. O\u2019Neil. 1995. A critique of ANSI SQL isolation levels. In ACM SIGMOD Record 24, 2 (1995),1\u201310."},{"key":"e_1_3_3_14_2","first-page":"7:1\u20137:15","volume-title":"Proceedings of the 27th International Conference on Concurrency Theory","author":"Bernardi Giovanni","year":"2016","unstructured":"Giovanni Bernardi and Alexey Gotsman. 2016. Robustness against consistency models with atomic visibility. In Proceedings of the 27th International Conference on Concurrency Theory. 7:1\u20137:15."},{"key":"e_1_3_3_15_2","first-page":"729","volume-title":"Proceedings of the SIGMOD","author":"Cahill Michael J.","year":"2008","unstructured":"Michael J. Cahill, Uwe R\u00f6hm, and Alan D. Fekete. 2008. Serializable isolation for snapshot databases. In Proceedings of the SIGMOD. 729\u2013738."},{"issue":"4","key":"e_1_3_3_16_2","first-page":"20:1\u201320:42","article-title":"Serializable isolation for snapshot databases","volume":"34","author":"Cahill Michael J.","year":"2009","unstructured":"Michael J. Cahill, Uwe R\u00f6hm, and Alan D. Fekete. 2009. Serializable isolation for snapshot databases. ACM Transactions on Database Systems 34, 4 (2009), 20:1\u201320:42.","journal-title":"ACM Transactions on Database Systems"},{"key":"e_1_3_3_17_2","first-page":"58","volume-title":"Proceedings of the 26th International Conference on Concurrency Theory","author":"Cerone Andrea","year":"2015","unstructured":"Andrea Cerone, Giovanni Bernardi, and Alexey Gotsman. 2015. A framework for transactional consistency models with atomic visibility. In Proceedings of the 26th International Conference on Concurrency Theory. 58\u201371."},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/3152396"},{"key":"e_1_3_3_19_2","first-page":"26:1\u201326:18","volume-title":"Proceedings of the 28th International Conference on Concurrency Theory","author":"Cerone Andrea","year":"2017","unstructured":"Andrea Cerone, Alexey Gotsman, and Hongseok Yang. 2017. Algebraic laws for weak consistency. In Proceedings of the 28th International Conference on Concurrency Theory. 26:1\u201326:18."},{"key":"e_1_3_3_20_2","first-page":"206","volume-title":"Proceedings of the 24th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems","author":"Fekete Alan","year":"2005","unstructured":"Alan Fekete. 2005. Allocating isolation levels to transactions. In Proceedings of the 24th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. 206\u2013215."},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/1071610.1071615"},{"issue":"11","key":"e_1_3_3_22_2","first-page":"2773","article-title":"IsoDiff: Debugging anomalies caused by weak isolation","volume":"13","author":"Gan Yifan","year":"2020","unstructured":"Yifan Gan, Xueyuan Ren, Drew Ripberger, Spyros Blanas, and Yang Wang. 2020. IsoDiff: Debugging anomalies caused by weak isolation. PVLDB 13, 11 (2020), 2773\u20132786.","journal-title":"PVLDB"},{"key":"e_1_3_3_23_2","first-page":"315","volume-title":"Proceedings of the PODS","author":"Ketsman Bas","year":"2020","unstructured":"Bas Ketsman, Christoph Koch, Frank Neven, and Brecht Vandevoort. 2020. Deciding robustness for lower SQL isolation levels. In Proceedings of the PODS. 315\u2013330."},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.14778\/2367502.2367523"},{"key":"e_1_3_3_25_2","unstructured":"TPC benchmark C standard specification revision 5.11 Transaction Processing Performance Council February 2010."},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476268"},{"key":"e_1_3_3_27_2","first-page":"16:1\u201316:17","volume-title":"Proceedings of the ICDT","author":"Vandevoort Brecht","year":"2022","unstructured":"Brecht Vandevoort, Bas Ketsman, Christoph Koch, and Frank Neven. 2022. Robustness against read committed for transaction templates with functional constraints. In Proceedings of the ICDT. 16:1\u201316:17."},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/3584372.3588672"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3716374","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3716374","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T18:43:43Z","timestamp":1750272223000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3716374"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,14]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6,30]]}},"alternative-id":["10.1145\/3716374"],"URL":"https:\/\/doi.org\/10.1145\/3716374","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2025,5,14]]},"assertion":[{"value":"2024-04-15","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-02-02","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-05-14","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}