{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,3]],"date-time":"2026-04-03T02:53:34Z","timestamp":1775184814256,"version":"3.50.1"},"reference-count":81,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2023,12,8]],"date-time":"2023-12-08T00:00:00Z","timestamp":1701993600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100006374","name":"National Science Foundation","doi-asserted-by":"publisher","award":["IIS-1762268,IIS-1956096"],"award-info":[{"award-number":["IIS-1762268,IIS-1956096"]}],"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":[[2023,12,8]]},"abstract":"<jats:p>What is a minimal set of tuples to delete from a database in order to eliminate all query answers? This problem is called \"the resilience of a query\" and is one of the key algorithmic problems underlying various forms of reverse data management, such as view maintenance, deletion propagation and causal responsibility. A long-open question is determining the conjunctive queries (CQs) for which resilience can be solved in PTIME.<\/jats:p>\n          <jats:p>We shed new light on this problem by proposing a unified Integer Linear Programming (ILP) formulation. It is unified in that it can solve both previously studied restrictions (e.g., self-join-free CQs under set semantics that allow a PTIME solution) and new cases (all CQs under set or bag semantics). It is also unified in that all queries and all database instances are treated with the same approach, yet the algorithm is guaranteed to terminate in PTIME for all known PTIME cases. In particular, we prove that for all known easy cases, the optimal solution to our ILP is identical to a simpler Linear Programming (LP) relaxation, which implies that standard ILP solvers return the optimal solution to the original ILP in PTIME.<\/jats:p>\n          <jats:p>Our approach allows us to explore new variants and obtain new complexity results. 1) It works under bag semantics, for which we give the first dichotomy results in the problem space. 2) We extend our approach to the related problem of causal responsibility and give a more fine-grained analysis of its complexity. 3) We recover easy instances for generally hard queries, including instances with read-once provenance and instances that become easy because of Functional Dependencies in the data. 4) We solve an open conjecture about a unified hardness criterion from PODS 2020 and prove the hardness of several queries of previously unknown complexity. 5) Experiments confirm that our findings accurately predict the asymptotic running times, and that our universal ILP is at times even quicker than a previously proposed dedicated flow algorithm.<\/jats:p>","DOI":"10.1145\/3626715","type":"journal-article","created":{"date-parts":[[2023,12,12]],"date-time":"2023-12-12T14:01:21Z","timestamp":1702389681000},"page":"1-27","source":"Crossref","is-referenced-by-count":9,"title":["A Unified Approach for Resilience and Causal Responsibility with Integer Linear Programming (ILP) and LP Relaxations"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0221-6836","authenticated-orcid":false,"given":"Neha","family":"Makhija","sequence":"first","affiliation":[{"name":"Northeastern University, Boston, MA, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9614-0504","authenticated-orcid":false,"given":"Wolfgang","family":"Gatterbauer","sequence":"additional","affiliation":[{"name":"Northeastern University, Boston, MA, USA"}]}],"member":"320","published-online":{"date-parts":[[2023,12,12]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/s0927-0507(05)x1200--2"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2018.0857"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3542700.3542719"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322389"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-020-01516--6"},{"key":"e_1_2_2_6_1","unstructured":"Manuel Bodirsky and Carsten Lutz. 2023. The Complexity of Resilience Problems via Valued Constraint Satisfaction Problems. (2023). arxiv: 2309.15654 [math.LO] https:\/\/arxiv.org\/abs\/2309.15654"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--1--4612-0619--4"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299881"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","unstructured":"Peter Buneman Sanjeev Khanna and Wang Chiew Tan. 2001. Why and Where: A Characterization of Data Provenance. In ICDT. 316--330. https:\/\/doi.org\/10.1007\/3--540--44503-x_20","DOI":"10.1007\/3--540--44503-x_20"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","unstructured":"Peter Buneman Sanjeev Khanna and Wang-Chiew Tan. 2002. On Propagation of Deletions and Annotations Through Views. In PODS. 150--158. https:\/\/doi.org\/10.1145\/543613.543633","DOI":"10.1145\/543613.543633"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","unstructured":"Peter Buneman and Wang-Chiew Tan. 2007. Provenance in Databases. In SIGMOD. 1171--1173. https:\/\/doi.org\/10.1145\/1247480.1247646","DOI":"10.1145\/1247480.1247646"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","unstructured":"Florent Capelli Nicolas Crosetti Joachim Niehren and Jan Ramon. 2022. Linear programs with conjunctive queries. (2022). https:\/\/doi.org\/10.4230\/LIPIcs.ICDT.2022.5","DOI":"10.4230\/LIPIcs.ICDT.2022.5"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/800105.803397"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","unstructured":"Surajit Chaudhuri and Moshe Y Vardi. 1993. Optimization of real conjunctive queries. In PODS. 59--70. https:\/\/doi.org\/10.1145\/153850.153856","DOI":"10.1145\/153850.153856"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1561\/9781601982339"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1613\/jair.1391"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3424305"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2005.12.033"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166--218X(01)00344--4"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1017\/cbo9780511852008.003"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-006-0004--3"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2395116.2395119"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/502807.502810"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/368273.368557"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/319732.319740"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304--3975(93)90073--3"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/bf01536399"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/261124.261126"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--642-03754--2_2"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1017\/s1471068405002577"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.4153\/cjm-1956-045--5"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850592"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","unstructured":"Cibele Freire Wolfgang Gatterbauer Neil Immerman and Alexandra Meliou. 2020. New Results for the Complexity of Resilience for Binary Conjunctive Queries with Self-Joins. In PODS. 271--284. https:\/\/doi.org\/10.1145\/3375395.3387647","DOI":"10.1145\/3375395.3387647"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3106237.3106277"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-016-0434--5"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.3233\/aic-2011-0491"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1017\/cbo9781139342124"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1561\/9781680838817"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1017\/cbo9780511852008.011"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/1148074.1148075"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--642--78240--4_4"},{"key":"e_1_2_2_42_1","unstructured":"LLC Gurobi Optimization. 2021. Mixed-Integer Programming (MIP) -- A Primer on the Basics. https:\/\/www.gurobi.com\/resource\/mip-basics\/"},{"key":"e_1_2_2_43_1","unstructured":"LLC Gurobi Optimization. 2022a. Gurobi Guidelines For Numerical Issues. https:\/\/www.gurobi.com\/documentation\/10.0\/refman\/guidelines_for_numerical_i.html"},{"key":"e_1_2_2_44_1","unstructured":"LLC Gurobi Optimization. 2022b. Gurobi Optimizer Reference Manual. http:\/\/www.gurobi.com"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1093\/bjps\/axi147"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1093\/bjps\/axi148"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687553.1687588"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.14778\/3425879.3425892"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453936"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--1--4684--2001--2_9"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3472391"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","unstructured":"Solmaz Kolahi. 2009. Functional Dependency (Encyclopedia of Database Systems). Springer 1200--1201. https:\/\/doi.org\/10.1007\/978-0--387--39940--9_1247","DOI":"10.1007\/978-0--387--39940--9_1247"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/focs.2015.80"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3294052.3319689"},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1017\/cbo9780511977152"},{"key":"e_1_2_2_56_1","doi-asserted-by":"crossref","unstructured":"Brian Y. Lim Anind K. Dey and Daniel Avrahami. 2009. Why and why not explanations improve the intelligibility of context-aware intelligent systems. In CHI. 2119--2128. http:\/\/doi.acm.org\/10.1145\/1518701.1519023","DOI":"10.1145\/1518701.1519023"},{"key":"e_1_2_2_57_1","unstructured":"Neha Makhija and Wolfgang Gatterbauer. 2023 a. A Unified Approach for Resilience and Causal Responsibility: Code and Experiments. https:\/\/github.com\/northeastern-datalab\/resilience-responsibility-ilp\/"},{"key":"e_1_2_2_58_1","unstructured":"Neha Makhija and Wolfgang Gatterbauer. 2023 b. A Unified Approach for Resilience and Causal Responsibility with Integer Linear Programming (ILP) and LP Relaxations. (2023). arxiv: 2212.08898 [cs.DB] https:\/\/arxiv.org\/abs\/2212.08898"},{"key":"e_1_2_2_59_1","first-page":"59","article-title":"Causality in Databases","volume":"33","author":"Meliou Alexandra","year":"2010","unstructured":"Alexandra Meliou, Wolfgang Gatterbauer, Joseph Y. Halpern, Christoph Koch, Katherine F. Moore, and Dan Suciu. 2010a. Causality in Databases. IEEE Data Eng. Bull., Vol. 33, 3 (2010), 59--67. http:\/\/sites.computer.org\/debull\/A10sept\/suciu.pdf","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_2_60_1","volume-title":"4th International Workshop on Management of Uncertain Data (MUD). CoRR, 3--17","author":"Meliou Alexandra","year":"2009","unstructured":"Alexandra Meliou, Wolfgang Gatterbauer, Katherine F. Moore, and Dan Suciu. 2009. Why so? or Why no? Functional Causality for Explaining Query Answers, In 4th International Workshop on Management of Uncertain Data (MUD). CoRR, 3--17. http:\/\/arxiv.org\/abs\/0912.5340"},{"key":"e_1_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.14778\/1880172.1880176"},{"key":"e_1_2_2_62_1","doi-asserted-by":"publisher","DOI":"10.14778\/3402755.3402803"},{"key":"e_1_2_2_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213875"},{"key":"e_1_2_2_64_1","volume-title":"PuLP: a linear programming toolkit for python","author":"Mitchell Stuart","year":"2011","unstructured":"Stuart Mitchell, Michael OSullivan, and Iain Dunning. 2011. PuLP: a linear programming toolkit for python. The University of Auckland, Auckland, New Zealand, Vol. 65 (2011). https:\/\/optimization-online.org\/?p=11731"},{"key":"e_1_2_2_65_1","unstructured":"the Potsdam Answer Set Solving Collection Potassco. 2022. clingo. https:\/\/potassco.org\/clingo\/"},{"key":"e_1_2_2_66_1","doi-asserted-by":"publisher","unstructured":"Romila Pradhan Jiongli Zhu Boris Glavic and Babak Salimi. 2022. Interpretable data-based explanations for fairness debugging. In SIGMOD. 247--261. https:\/\/doi.org\/10.1145\/3514221.3517886","DOI":"10.1145\/3514221.3517886"},{"key":"e_1_2_2_67_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF03037171"},{"key":"e_1_2_2_68_1","doi-asserted-by":"publisher","unstructured":"Sudeepa Roy and Dan Suciu. 2014. A Formal Approach to Finding Explanations for Database Queries. In SIGMOD. 1579--1590. https:\/\/doi.org\/10.1145\/2588555.2588578","DOI":"10.1145\/2588555.2588578"},{"key":"e_1_2_2_69_1","doi-asserted-by":"publisher","unstructured":"Babak Salimi Luke Rodriguez Bill Howe and Dan Suciu. 2019. Interventional fairness: Causal database repair for algorithmic fairness. In SIGMOD. 793--810. https:\/\/doi.org\/10.1145\/3299869.3319901","DOI":"10.1145\/3299869.3319901"},{"key":"e_1_2_2_70_1","doi-asserted-by":"publisher","DOI":"10.1137\/1030065"},{"key":"e_1_2_2_71_1","volume-title":"Combinatorial optimization: polyhedra and efficiency. Algorithms and Combinatorics","author":"Schrijver Alexander","unstructured":"Alexander Schrijver. 2003. Combinatorial optimization: polyhedra and efficiency. Algorithms and Combinatorics, Vol. 24. Springer. https:\/\/doi.org\/book\/9783540443896"},{"key":"e_1_2_2_72_1","volume-title":"Proceedings of the 7th Python in science conferences (SciPy","volume":"2008","author":"Schult Daniel A","year":"2008","unstructured":"Daniel A Schult and P Swart. 2008. Exploring network structure, dynamics, and function using NetworkX. In Proceedings of the 7th Python in science conferences (SciPy 2008), Vol. 2008. Pasadena, CA, 11--16. https:\/\/permalink.lanl.gov\/object\/tr?what=info:lanl-repo\/lareport\/LA-UR-08-05495"},{"key":"e_1_2_2_73_1","unstructured":"TPC-H. 2022. TPC-H Homepage. https:\/\/www.tpc.org\/tpch\/"},{"key":"e_1_2_2_74_1","volume-title":"Principles of Database and Knowledge-Base Systems: Volume II: The New Technologies","author":"Ullman Jeffrey D.","unstructured":"Jeffrey D. Ullman. 1990. Principles of Database and Knowledge-Base Systems: Volume II: The New Technologies. W. H. Freeman & Co., New York, NY, USA."},{"key":"e_1_2_2_75_1","doi-asserted-by":"publisher","unstructured":"Moshe Y. Vardi. 1982. The Complexity of Relational Query Languages (Extended Abstract). In STOC. 137--146. https:\/\/doi.org\/10.1145\/800070.802186","DOI":"10.1145\/800070.802186"},{"key":"e_1_2_2_76_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--662-04565--7"},{"key":"e_1_2_2_77_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824117"},{"key":"e_1_2_2_78_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035925"},{"key":"e_1_2_2_79_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536354.2536356"},{"key":"e_1_2_2_80_1","doi-asserted-by":"publisher","DOI":"10.1145\/3542700.3542718"},{"key":"e_1_2_2_81_1","volume-title":"On Explaining Confounding Bias. arXiv preprint arXiv:2210.02943","author":"Youngmann Brit","year":"2022","unstructured":"Brit Youngmann, Michael Cafarella, Yuval Moskovitch, and Babak Salimi. 2022. On Explaining Confounding Bias. arXiv preprint arXiv:2210.02943 (2022). https:\/\/arxiv.org\/abs\/2210.02943"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3626715","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3626715","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T13:03:15Z","timestamp":1755867795000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3626715"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,8]]},"references-count":81,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,12,8]]}},"alternative-id":["10.1145\/3626715"],"URL":"https:\/\/doi.org\/10.1145\/3626715","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,12,8]]}}}