{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:03:44Z","timestamp":1750309424640,"version":"3.41.0"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2024,5,14]],"date-time":"2024-05-14T00:00:00Z","timestamp":1715644800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGMOD Rec."],"published-print":{"date-parts":[[2024,5,14]]},"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 paper, 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 paper, despite its practical relevance, has largely been ignored. We focus on multiversion concurrency control and consider the isolation levels that are available in Postgres 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\/3665252.3665257","type":"journal-article","created":{"date-parts":[[2024,5,14]],"date-time":"2024-05-14T22:04:33Z","timestamp":1715724273000},"page":"16-23","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":"53","author":[{"given":"Brecht","family":"Vandevoort","sequence":"first","affiliation":[{"name":"UHasselt, Data Science Institute, ACSL"}]},{"given":"Bas","family":"Ketsman","sequence":"additional","affiliation":[{"name":"Vrije Universiteit Brussel"}]},{"given":"Frank","family":"Neven","sequence":"additional","affiliation":[{"name":"UHasselt, Data Science Institute, ACSL"}]}],"member":"320","published-online":{"date-parts":[[2024,5,14]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"MIT","author":"Adya A.","year":"1999","unstructured":"A. Adya. Weak Consistency: A Generalized Theory and Optimistic Implementations for Distributed Transactions. Ph.D., MIT, Cambridge, MA, USA, Mar. 1999."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/846219.847380"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/AICCSA.2013.6616497"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497466"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-78568-2_21"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/AICCSA.2015.7507103"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.22"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/3430915.3430918"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732232.2732237"},{"key":"e_1_2_1_10_1","first-page":"286","volume-title":"CAV","author":"Beillahi S. M.","year":"2019","unstructured":"S. M. Beillahi, A. Bouajjani, and C. Enea. Checking robustness against snapshot isolation. In CAV, pages 286--304, 2019."},{"key":"e_1_2_1_11_1","first-page":"1","volume-title":"CONCUR","author":"Beillahi S. M.","year":"2019","unstructured":"S. M. Beillahi, A. Bouajjani, and C. Enea. Robustness against transactional causal consistency. In CONCUR, pages 1--18, 2019."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/223784.223785"},{"key":"e_1_2_1_13_1","first-page":"1","volume-title":"CONCUR","author":"Bernardi G.","year":"2016","unstructured":"G. Bernardi and A. Gotsman. Robustness against consistency models with atomic visibility. In CONCUR, pages 7:1--7:15, 2016."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376690"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1620585.1620587"},{"key":"e_1_2_1_16_1","first-page":"58","volume-title":"CONCUR","author":"Cerone A.","year":"2015","unstructured":"A. Cerone, G. Bernardi, and A. Gotsman. A framework for transactional consistency models with atomic visibility. In CONCUR, pages 58--71, 2015."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3152396"},{"key":"e_1_2_1_18_1","first-page":"1","volume-title":"CONCUR","author":"Cerone A.","year":"2017","unstructured":"A. Cerone, A. Gotsman, and H. Yang. Algebraic Laws for Weak Consistency. In CONCUR, pages 26:1--26:18, 2017."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065193"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1071610.1071615"},{"issue":"11","key":"e_1_2_1_21_1","first-page":"2773","article-title":"Isodiff: Debugging anomalies caused by weak isolation","volume":"13","author":"Gan Y.","year":"2020","unstructured":"Y. Gan, X. Ren, D. Ripberger, S. Blanas, and Y. Wang. Isodiff: Debugging anomalies caused by weak isolation. PVLDB, 13(11):2773--2786, 2020.","journal-title":"PVLDB"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3387655"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/2367502.2367523"},{"key":"e_1_2_1_24_1","unstructured":"TPC-C. On-line transaction processing benchmark. http:\/\/www.tpc.org\/tpcc\/."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476268"},{"key":"e_1_2_1_26_1","first-page":"1","volume-title":"ICDT","author":"Vandevoort B.","year":"2022","unstructured":"B. Vandevoort, B. Ketsman, C. Koch, and F. Neven. Robustness against read committed for transaction templates with functional constraints. In ICDT, pages 16:1--16:17, 2022."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3584372.3588672"}],"container-title":["ACM SIGMOD Record"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3665252.3665257","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3665252.3665257","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:58:33Z","timestamp":1750294713000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3665252.3665257"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,14]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,5,14]]}},"alternative-id":["10.1145\/3665252.3665257"],"URL":"https:\/\/doi.org\/10.1145\/3665252.3665257","relation":{},"ISSN":["0163-5808"],"issn-type":[{"type":"print","value":"0163-5808"}],"subject":[],"published":{"date-parts":[[2024,5,14]]},"assertion":[{"value":"2024-05-14","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}