{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:14:09Z","timestamp":1779174849974,"version":"3.51.4"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2024,5,29]],"date-time":"2024-05-29T00:00:00Z","timestamp":1716940800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100006374","name":"European Research Council","doi-asserted-by":"publisher","award":["804302"],"award-info":[{"award-number":["804302"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]},{"name":"UZH Global Strategy and Partnerships Funding Scheme"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,5,29]]},"abstract":"<jats:p>Quantifying the contribution of database facts to query answers has been studied as means of explanation. The Banzhaf value, originally developed in Game Theory, is a natural measure of fact contribution, yet its efficient computation for select-project-join-union queries is challenging. In this paper, we introduce three algorithms to compute the Banzhaf value of database facts: an exact algorithm, an anytime deterministic approximation algorithm with relative error guarantees, and an algorithm for ranking and top-k. They have three key building blocks: compilation of query lineage into an equivalent function that allows efficient Banzhaf value computation; dynamic programming computation of the Banzhaf values of variables in a Boolean function using the Banzhaf values for constituent functions; and a mechanism to compute efficiently lower and upper bounds on Banzhaf values for any positive DNF function.<\/jats:p>\n          <jats:p>We complement the algorithms with a dichotomy for the Banzhaf-based ranking problem: given two facts, deciding whether the Banzhaf value of one is greater than of the other is tractable for hierarchical queries and intractable for non-hierarchical queries.<\/jats:p>\n          <jats:p>We show experimentally that our algorithms significantly outperform exact and approximate algorithms from prior work, most times up to two orders of magnitude. Our algorithms can also cover challenging problem instances that are beyond reach for prior work.<\/jats:p>","DOI":"10.1145\/3654926","type":"journal-article","created":{"date-parts":[[2024,5,30]],"date-time":"2024-05-30T09:44:53Z","timestamp":1717062293000},"page":"1-26","source":"Crossref","is-referenced-by-count":8,"title":["Banzhaf Values for Facts in Query Answering"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0009-0003-3116-7196","authenticated-orcid":false,"given":"Omer","family":"Abramovich","sequence":"first","affiliation":[{"name":"Tel Aviv University, Tel Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-0838-0162","authenticated-orcid":false,"given":"Daniel","family":"Deutch","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Tel Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-8002-0578","authenticated-orcid":false,"given":"Nave","family":"Frost","sequence":"additional","affiliation":[{"name":"eBay, Tel Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8155-8070","authenticated-orcid":false,"given":"Ahmet","family":"Kara","sequence":"additional","affiliation":[{"name":"University of Zurich, Zurich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4682-7068","authenticated-orcid":false,"given":"Dan","family":"Olteanu","sequence":"additional","affiliation":[{"name":"University of Zurich, Zurich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,5,30]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Foundations of Databases","author":"Abiteboul Serge","unstructured":"Serge Abiteboul, Richard Hull, and Victor Vianu. 1995. Foundations of Databases. Vol. 8. Addison-Wesley Reading. http:\/\/webdam.inria.fr\/Alice\/"},{"key":"e_1_2_1_2_1","unstructured":"Omer Abramovich Daniel Deutch Nave Frost Ahmet Kara and Dan Olteanu. 2023 a. Banzhaf Values for Facts in Query Answering. arxiv: 2308.05588 [cs.DB] Extended Version."},{"key":"e_1_2_1_3_1","unstructured":"Omer Abramovich Daniel Deutch Nave Frost Ahmet Kara and Dan Olteanu. 2023 b. GitHub Repository. https:\/\/github.com\/Omer-Abramovich\/AdaBan."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3511808.3557204"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v35i8.16825"},{"key":"e_1_2_1_6_1","article-title":"On the Complexity of SHAP-Score-Based Explanations: Tractability via Knowledge Compilation and Non-Approximability Results","volume":"24","author":"Arenas Marcelo","year":"2023","unstructured":"Marcelo Arenas, Pablo Barcel\u00f3, Leopoldo E. Bertossi, and Mika\u00eb l Monet. 2023. On the Complexity of SHAP-Score-Based Explanations: Tractability via Knowledge Compilation and Non-Approximability Results. J. Mach. Learn. Res. , Vol. 24 (2023), 63:1--63:58. http:\/\/jmlr.org\/papers\/v24\/21-0389.html","journal-title":"J. Mach. Learn. Res."},{"key":"e_1_2_1_7_1","first-page":"317","article-title":"Weighted Voting Doesn't Work: A Mathematical Analysis","volume":"19","author":"Banzhaf J.F.","year":"1965","unstructured":"J.F. Banzhaf. 1965. Weighted Voting Doesn't Work: A Mathematical Analysis. Rutgers Law Review, Vol. 19, 2 (1965), 317--343.","journal-title":"Rutgers Law Review"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3615952.3615954"},{"key":"e_1_2_1_9_1","volume-title":"Proc","author":"Buneman Peter","unstructured":"Peter Buneman, Sanjeev Khanna, and Tan Wang-Chiew. 2001. Why and Where: A Characterization of Data Provenance. In Proc. of ICDT. Springer, 316--330."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559901"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1561\/1900000006"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/357775.357777"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-019-00606-4"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1613\/jair.989"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3520172"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517912"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2022.102060"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1073-y"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1111\/risa.14156"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01240041"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-013-0310--5"},{"key":"e_1_2_1_22_1","volume-title":"Provenance Semirings. In Proc. of PODS. 31--40","author":"Green Todd J","year":"2007","unstructured":"Todd J Green, Grigoris Karvounarakis, and Val Tannen. 2007. Provenance Semirings. In Proc. of PODS. 31--40. https:\/\/repository.upenn.edu\/cgi\/viewcontent.cgi?article=1022&context=db_research"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3056125"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-017-0486--1"},{"key":"e_1_2_1_25_1","volume-title":"Proc. of UAI (PMLR","volume":"979","author":"Karczmarz Adam","year":"2022","unstructured":"Adam Karczmarz, Tomasz P. Michalak, Anish Mukherjee, Piotr Sankowski, and Piotr Wygocki. 2022. Improved Feature Importance Computation for Tree Models based on the Banzhaf Value. In Proc. of UAI (PMLR, Vol. 180). PMLR, 969--979. https:\/\/proceedings.mlr.press\/v180\/karczmarz22a.html"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICDT.2023.11"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00355-009-0387--3"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/3380750.3380760"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01254541"},{"key":"e_1_2_1_30_1","volume-title":"Proc. of ICDT (LIPIcs","volume":"19","author":"Livshits Ester","year":"2020","unstructured":"Ester Livshits, Leopoldo E. Bertossi, Benny Kimelfeld, and Moshe Sebag. 2020. The Shapley Value of Tuples in Query Answering. In Proc. of ICDT (LIPIcs, Vol. 155). 20:1--20:19. https:\/\/arxiv.org\/abs\/1904.08679"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3471485.3471504"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.46298\/lmcs-17(3:22)2021"},{"key":"e_1_2_1_33_1","volume-title":"Proc. of NeurIPS. 4765--4774","author":"Lundberg Scott M","year":"2017","unstructured":"Scott M Lundberg and Su-In Lee. 2017. A Unified Approach to Interpreting Model Predictions. In Proc. of NeurIPS. 4765--4774. http:\/\/papers.nips.cc\/paper\/7062-a-unified-approach-to-interpreting-model-predictions.pdf"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/1880172.1880176"},{"key":"e_1_2_1_35_1","volume-title":"TaPP,","author":"Meliou Alexandra","unstructured":"Alexandra Meliou, Wolfgang Gatterbauer, and Dan Suciu. 2011. Bringing Provenance to Its Full Potential Using Causal Reasoning. In TaPP, , Peter Buneman and Juliana Freire (Eds.). USENIX Association."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/2733004.2733070"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3300066"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.14778\/3352063.3352071"},{"key":"e_1_2_1_39_1","volume-title":"Proc","author":"Olteanu Dan","unstructured":"Dan Olteanu and Jiewen Huang. 2008. hrefhttps:\/\/www.cs.ox.ac.uk\/people\/dan.olteanu\/papers\/oh-sum08.pdfUsing OBDDs for Efficient Query Evaluation on Probabilistic Databases. In Proc. of SUM. Springer, 326--340."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2010.5447826"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.61"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.2307\/2981392"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3387664"},{"key":"e_1_2_1_44_1","doi-asserted-by":"crossref","unstructured":"Mustapha Ridaoui Michel Grabisch and Christophe Labreuche. 2018. An Axiomatisation of the Banzhaf Value and Interaction Index for Multichoice Games. In MDAI. https:\/\/shs.hal.science\/halshs-02381119","DOI":"10.1007\/978-3-030-00202-2_12"},{"key":"e_1_2_1_45_1","volume-title":"Proc. of TaPP. USENIX Association. http:\/\/web.cs.ucla.edu\/ guyvdb\/papers\/SalimiTaPP16","author":"Salimi Babak","year":"2016","unstructured":"Babak Salimi, Leopoldo E. Bertossi, Dan Suciu, and Guy Van den Broeck. 2016. Quantifying Causal Effects on Query Answering in Databases. In Proc. of TaPP. USENIX Association. http:\/\/web.cs.ucla.edu\/ guyvdb\/papers\/SalimiTaPP16.pdf"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1213\/ANE.0000000000002864"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1968.10480934"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.14778\/3229863.3236253"},{"key":"e_1_2_1_49_1","first-page":"39","volume-title":"A Value for n-Person Games. Contributions to the Theory of Games","author":"Shapley Lloyd S","year":"1953","unstructured":"Lloyd S Shapley. 1953. A Value for n-Person Games. Contributions to the Theory of Games , Vol. 2, 28 (1953), 307--317. http:\/\/www.library.fa.ru\/files\/Roth2.pdf#page=39"},{"key":"e_1_2_1_50_1","volume-title":"The Shapley-Shubik and Banzhaf Power Indices as Probabilities. The Shapley value: essays in honor of Lloyd S. Shapley","author":"Strafiin Philip D","year":"1988","unstructured":"Philip D Strafiin Jr. 1988. The Shapley-Shubik and Banzhaf Power Indices as Probabilities. The Shapley value: essays in honor of Lloyd S. Shapley (1988), 71."},{"key":"e_1_2_1_51_1","doi-asserted-by":"crossref","unstructured":"Dan Suciu Dan Olteanu Christopher R\u00e9 and Christoph Koch. 2011. Probabilistic Databases. Morgan & Claypool. https:\/\/www.morganclaypool.com\/doi\/abs\/10.2200\/S00362ED1V01Y201105DTM016","DOI":"10.1007\/978-3-031-01879-4"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.neunet.2018.06.006"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/s003550050125"},{"key":"e_1_2_1_54_1","first-page":"2","article-title":"Negotiating the Lisbon Treaty: Redistribution, Efficiency and Power Indices","volume":"6","author":"Varela Diego","year":"2012","unstructured":"Diego Varela and Javier Prado-Dominguez. 2012. Negotiating the Lisbon Treaty: Redistribution, Efficiency and Power Indices. Czech Economic Review, Vol. 6, 2 (July 2012), 107--124.","journal-title":"Czech Economic Review"},{"key":"e_1_2_1_55_1","volume-title":"Wang and Ruoxi Jia","author":"Jiachen","year":"2023","unstructured":"Jiachen T. Wang and Ruoxi Jia. 2023. Data Banzhaf: A Robust Data Valuation Framework for Machine Learning. In Proc. of AISTATS. 6388--6421. io"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3654926","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3654926","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T14:42:16Z","timestamp":1755787336000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3654926"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,29]]},"references-count":55,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,5,29]]}},"alternative-id":["10.1145\/3654926"],"URL":"https:\/\/doi.org\/10.1145\/3654926","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,29]]}}}