{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T22:10:03Z","timestamp":1755900603822,"version":"3.44.0"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2024,5,10]],"date-time":"2024-05-10T00:00:00Z","timestamp":1715299200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100006374","name":"Fonds Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["G019921N"],"award-info":[{"award-number":["G019921N"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,5,10]]},"abstract":"<jats:p>A DBMS allows trading consistency for efficiency through the allocation of isolation levels that are strictly weaker than serializability. The robustness problem 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 safe. In the literature, safe is interpreted as conflict-serializable (to which we refer here as conflict-robustness). In this paper, we study the view-robustness problem, interpreting safe as view-serializable. View-serializability is a more permissive notion that allows for a greater number of schedules to be serializable and aligns more closely with the intuitive understanding of what it means for a database to be consistent. However, view-serializability is more complex to analyze (e.g., conflict-serializability can be decided in polynomial time whereas deciding view-serializability is NP-complete). While conflict-robustness implies view-robustness, the converse does not hold in general. In this paper, we provide a sufficient condition for isolation levels guaranteeing that conflict- and view-robustness coincide and show that this condition is satisfied by the isolation levels occurring in Postgres and Oracle: read committed (RC), snapshot isolation (SI) and serializable snapshot isolation (SSI). It hence follows that for these systems, widening from conflict- to view-serializability does not allow for more sets of transactions to become robust. Interestingly, the complexity of deciding serializability within these isolation levels is still quite different. Indeed, deciding conflict-serializability for schedules allowed under RC and SI remains in polynomial time, while we show that deciding view-serializability within these isolation levels remains NP-complete.<\/jats:p>","DOI":"10.1145\/3651592","type":"journal-article","created":{"date-parts":[[2024,5,14]],"date-time":"2024-05-14T08:32:13Z","timestamp":1715675533000},"page":"1-16","source":"Crossref","is-referenced-by-count":0,"title":["When View- and Conflict-Robustness Coincide for Multiversion Concurrency Control"],"prefix":"10.1145","volume":"2","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, Brussels, 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":[[2024,5,14]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/888672"},{"key":"e_1_2_1_2_1","volume-title":"O'Neil","author":"Adya Atul","year":"2000","unstructured":"Atul Adya, Barbara Liskov, and Patrick E. O'Neil. 2000. Generalized Isolation Level Definitions. In ICDE. 67--78."},{"key":"e_1_2_1_3_1","volume-title":"O'Neil","author":"Berenson Hal","year":"1995","unstructured":"Hal Berenson, Philip A. Bernstein, Jim Gray, Jim Melton, Elizabeth J. O'Neil, and Patrick E. O'Neil. 1995. A Critique of ANSI SQL Isolation Levels. In SIGMOD. 1--10."},{"key":"e_1_2_1_4_1","first-page":"1","article-title":"Robustness against Consistency Models with Atomic Visibility","volume":"7","author":"Bernardi Giovanni","year":"2016","unstructured":"Giovanni Bernardi and Alexey Gotsman. 2016. Robustness against Consistency Models with Atomic Visibility. In CONCUR. 7:1--7:15.","journal-title":"CONCUR."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/319996.319998"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3360591"},{"key":"e_1_2_1_7_1","volume-title":"Uwe R\u00f6 hm, and Alan D. Fekete","author":"Cahill Michael J.","year":"2008","unstructured":"Michael J. Cahill, Uwe R\u00f6 hm, and Alan D. Fekete. 2008. Serializable isolation for snapshot databases. In SIGMOD. 729--738."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1620585.1620587"},{"key":"e_1_2_1_9_1","unstructured":"Andrea Cerone Giovanni Bernardi and Alexey Gotsman. 2015. A Framework for Transactional Consistency Models with Atomic Visibility. In CONCUR. 58--71."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3152396"},{"key":"e_1_2_1_11_1","first-page":"1","article-title":"Algebraic Laws for Weak Consistency","volume":"26","author":"Cerone Andrea","year":"2017","unstructured":"Andrea Cerone, Alexey Gotsman, and Hongseok Yang. 2017. Algebraic Laws for Weak Consistency. In CONCUR. 26:1--26:18.","journal-title":"CONCUR."},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Alan Fekete. 2005. Allocating isolation levels to transactions. In PODS. 206--215.","DOI":"10.1145\/1065167.1065193"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1071610.1071615"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Bas Ketsman Christoph Koch Frank Neven and Brecht Vandevoort. 2020. Deciding Robustness for Lower SQL Isolation Levels. In PODS. 315--330.","DOI":"10.1145\/3375395.3387655"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/322154.322158"},{"volume-title":"The Theory of Database Concurrency Control","author":"Papadimitriou Christos H.","key":"e_1_2_1_16_1","unstructured":"Christos H. Papadimitriou. 1986. The Theory of Database Concurrency Control. Computer Science Press."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/348.318588"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/2367502.2367523"},{"key":"e_1_2_1_19_1","unstructured":"TPC-C. [n. d.]. On-Line Transaction Processing Benchmark. ( [n. d.]). http:\/\/www.tpc.org\/tpcc\/."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476268"},{"key":"e_1_2_1_21_1","first-page":"1","article-title":"Robustness Against Read Committed for Transaction Templates with Functional Constraints","volume":"16","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 ICDT. 16:1--16:17.","journal-title":"ICDT."},{"key":"e_1_2_1_22_1","unstructured":"Brecht Vandevoort Bas Ketsman Christoph Koch and Frank Neven. 2023 b. Detecting Robustness against MVRC for Transaction Programs with Predicate Reads. In EDBT. 565--577."},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Brecht Vandevoort Bas Ketsman and Frank Neven. 2023 a. Allocating Isolation Levels to Transactions in a Multiversion Setting. In PODS. 69--78.","DOI":"10.1145\/3584372.3588672"},{"key":"e_1_2_1_24_1","unstructured":"Brecht Vandevoort Bas Ketsman and Frank Neven. 2024. When View- and Conflict-Robustness Coincide for Multiversion Concurrency Control (full version). (2024). https:\/\/arxiv.org\/abs\/2403.17665."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/62.322425"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651592","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3651592","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T21:40:17Z","timestamp":1755898817000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651592"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,10]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,5,10]]}},"alternative-id":["10.1145\/3651592"],"URL":"https:\/\/doi.org\/10.1145\/3651592","relation":{},"ISSN":["2836-6573"],"issn-type":[{"type":"electronic","value":"2836-6573"}],"subject":[],"published":{"date-parts":[[2024,5,10]]}}}