{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,12]],"date-time":"2025-11-12T16:10:42Z","timestamp":1762963842826,"version":"3.45.0"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"5","funder":[{"DOI":"10.13039\/501100001659","name":"German Research Foundation","doi-asserted-by":"crossref","award":["GR 1492\/16-1, KI 2348\/1-1, GRK 2236"],"award-info":[{"award-number":["GR 1492\/16-1, KI 2348\/1-1, GRK 2236"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["101054974 (SymSim)"],"award-info":[{"award-number":["101054974 (SymSim)"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,11,10]]},"abstract":"<jats:p>In recent years, the Shapley value has emerged as a general game-theoretic measure for assessing the contribution of a tuple to the result of a database query. We study the complexity of calculating the Shapley value of a tuple for an aggregate conjunctive query, which applies an aggregation function to the result of a conjunctive query (CQ) based on a value function that assigns a number to each query answer. Prior work by Livshits, Bertossi, Kimelfeld, and Sebag (2020) established that this task is #P-hard for every nontrivial aggregation function when the query is non-hierarchical with respect to its existential variables, assuming the absence of self-joins. They further showed that this condition precisely characterizes the class of intractable CQs when the aggregate function is sum or count. In addition, they posed as open problems the complexity of other common aggregate functions such as min, max, count-distinct, average, and quantile (including median).<\/jats:p>\n                  <jats:p>Towards the resolution of these problems, we identify for each aggregate function a class of hierarchical CQs where the Shapley value is tractable with every value function, as long as it is local (i.e., determined by the tuples of one relation). We further show that each such class is maximal: for every CQ outside of this class, there is a local (easy-to-compute) value function that makes the Shapley value #P-hard. Interestingly, our results reveal that each aggregate function corresponds to a different generalization of the class of hierarchical CQs from Boolean to non-Boolean queries. In particular, max, min, and count-distinct match the class of CQs that are all-hierarchical (i.e., hierarchical with respect to all variables), and average and quantile match the narrower class of q-hierarchical CQs introduced by Berkholz, Keppeler, and Schweikardt (2017) in the context of the fine-grained complexity of query answering. Finally, we show an example of an aggregate function---''has-duplicates''---that gives rise to a new variation of hierarchy that is more restricted than q-hierarchy.<\/jats:p>","DOI":"10.1145\/3767720","type":"journal-article","created":{"date-parts":[[2025,11,12]],"date-time":"2025-11-12T15:06:02Z","timestamp":1762959962000},"page":"1-21","source":"Crossref","is-referenced-by-count":0,"title":["Tractability Frontiers of the Shapley Value for Aggregate Conjunctive Queries"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3034-730X","authenticated-orcid":false,"given":"Christoph","family":"Standke","sequence":"first","affiliation":[{"name":"RWTH Aachen University, Aachen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7156-1572","authenticated-orcid":false,"given":"Benny","family":"Kimelfeld","sequence":"additional","affiliation":[{"name":"Technion - Israel Institute of Technology, Haifa, Israel and RelationalAI, Berkeley, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,11,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3654926"},{"key":"e_1_2_1_2_1","volume-title":"Advancing Fact Attribution for Query Answering: Aggregate Queries and Novel Algorithms. CoRR","author":"Abramovich Omer","year":"2025","unstructured":"Omer Abramovich, Daniel Deutch, Nave Frost, Ahmet Kara, and Dan Olteanu. 2025. Advancing Fact Attribution for Query Answering: Aggregate Queries and Novel Algorithms. CoRR, Vol. abs\/2506.16923 (2025)."},{"key":"e_1_2_1_3_1","first-page":"129","article-title":"Answering aggregate queries in data exchange","author":"Afrati Foto N.","year":"2008","unstructured":"Foto N. Afrati and Phokion G. Kolaitis. 2008. Answering aggregate queries in data exchange. In PODS. ACM, 129-138.","journal-title":"PODS. ACM"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3685980.3685982"},{"key":"e_1_2_1_5_1","first-page":"99","article-title":"Shapley meets Shapley. In STACS (LIPIcs, Vol. 25)","author":"Aziz Haris","year":"2014","unstructured":"Haris Aziz and Bart de Keijzer. 2014. Shapley meets Shapley. In STACS (LIPIcs, Vol. 25). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 99-111.","journal-title":"Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik"},{"key":"e_1_2_1_6_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_7_1","first-page":"303","article-title":"Answering Conjunctive Queries under Updates","author":"Berkholz Christoph","year":"2017","unstructured":"Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt. 2017. Answering Conjunctive Queries under Updates. In PODS. ACM, 303-318.","journal-title":"PODS. ACM"},{"key":"e_1_2_1_8_1","first-page":"402","article-title":"Probabilistic Databases under Updates","author":"Berkholz Christoph","year":"2021","unstructured":"Christoph Berkholz and Maximilian Merz. 2021. Probabilistic Databases under Updates: Boolean Query Evaluation and Ranked Enumeration. In PODS. ACM, 402-415.","journal-title":"Boolean Query Evaluation and Ranked Enumeration. In PODS. ACM"},{"key":"e_1_2_1_9_1","article-title":"Data Quality and Explainable AI","volume":"12","author":"Bertossi Leopoldo E.","year":"2020","unstructured":"Leopoldo E. Bertossi and Floris Geerts. 2020. Data Quality and Explainable AI. ACM J. Data Inf. Qual., Vol. 12, 2 (2020), 11:1-11:9.","journal-title":"ACM J. Data Inf. Qual."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3615952.3615954"},{"key":"e_1_2_1_11_1","first-page":"156","article-title":"Shapley Value Computation in Ontology-Mediated Query Answering","author":"Bienvenu Meghyn","year":"2024","unstructured":"Meghyn Bienvenu, Diego Figueira, and Pierre Lafourcade. 2024a. Shapley Value Computation in Ontology-Mediated Query Answering. In KR. 156-166.","journal-title":"KR."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3651606"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3725249"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1458484.1458500"},{"key":"e_1_2_1_15_1","first-page":"277","article-title":"Conjunctive Queries With Self-Joins, Towards a Fine-Grained Enumeration Complexity Analysis","author":"Carmeli Nofar","year":"2023","unstructured":"Nofar Carmeli and Luc Segoufin. 2023. Conjunctive Queries With Self-Joins, Towards a Fine-Grained Enumeration Complexity Analysis. In PODS. ACM, 277-289.","journal-title":"PODS. ACM"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.inffus.2021.11.003"},{"key":"e_1_2_1_17_1","volume-title":"Dalvi and Dan Suciu","author":"Nilesh","year":"2004","unstructured":"Nilesh N. Dalvi and Dan Suciu. 2004. Efficient Query Evaluation on Probabilistic Databases. In VLDB. Morgan Kaufmann, 864-875."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/S00778-006-0004-3"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2395116.2395119"},{"key":"e_1_2_1_20_1","volume-title":"Computing the Shapley Value of Facts in Query Answering. In SIGMOD Conference. ACM, 1570-1583","author":"Deutch Daniel","year":"2022","unstructured":"Daniel Deutch, Nave Frost, Benny Kimelfeld, and Mika\u00ebl Monet. 2022. Computing the Shapley Value of Facts in Query Answering. In SIGMOD Conference. ACM, 1570-1583."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989727.1989729"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/2140436.2140445"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2877203"},{"key":"e_1_2_1_24_1","unstructured":"Amir Gilad Martin Grohe Benny Kimelfeld Peter Lindner and Christoph Standke. 2024. The Importance of Parameters in Database Queries. arXiv:2401.04606 [cs.DB] https:\/\/arxiv.org\/abs\/2401.04606"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1561\/1900000074"},{"key":"e_1_2_1_26_1","first-page":"227","article-title":"The Complexity of Query Reliability","author":"Gr\u00e4del Erich","year":"1998","unstructured":"Erich Gr\u00e4del, Yuri Gurevich, and Colin Hirsch. 1998. The Complexity of Query Reliability. In PODS. ACM, 227-234.","journal-title":"PODS. ACM"},{"key":"e_1_2_1_27_1","first-page":"1","article-title":"The Importance of Parameters in Database Queries. In ICDT (LIPIcs, Vol. 290)","volume":"14","author":"Grohe Martin","year":"2024","unstructured":"Martin Grohe, Benny Kimelfeld, Peter Lindner, and Christoph Standke. 2024. The Importance of Parameters in Database Queries. In ICDT (LIPIcs, Vol. 290). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 14:1-14:17.","journal-title":"Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik"},{"volume-title":"Introduction to Number Theory","author":"Hua Loo-Keng","key":"e_1_2_1_28_1","unstructured":"Loo-Keng Hua. 1982. Introduction to Number Theory. Springer-Verlag. xviii572 pages."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2010.06.001"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064027"},{"key":"e_1_2_1_31_1","first-page":"1167","article-title":"Towards Efficient Data Valuation Based on the Shapley Value. In AISTATS (Proceedings of Machine Learning Research, Vol. 89)","author":"Jia Ruoxi","year":"2019","unstructured":"Ruoxi Jia, David Dao, Boxin Wang, Frances Ann Hubis, Nick Hynes, Nezihe Merve G\u00fcrel, Bo Li, Ce Zhang, Dawn Song, and Costas J. Spanos. 2019. Towards Efficient Data Valuation Based on the Shapley Value. In AISTATS (Proceedings of Machine Learning Research, Vol. 89). PMLR, 1167-1176.","journal-title":"PMLR"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3651142"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3651593"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3471485.3471504"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.46298\/lmcs-17(3:22)2021"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.46298\/lmcs-18(2:20)2022"},{"key":"e_1_2_1_37_1","volume-title":"From local explanations to global understanding with explainable AI for trees. Nature machine intelligence","author":"Lundberg Scott M","year":"2020","unstructured":"Scott M Lundberg, Gabriel Erion, Hugh Chen, Alex DeGrave, Jordan M Prutkin, Bala Nair, Ronit Katz, Jonathan Himmelfarb, Nisha Bansal, and Su-In Lee. 2020. From local explanations to global understanding with explainable AI for trees. Nature machine intelligence, Vol. 2, 1 (2020), 2522-5839."},{"key":"e_1_2_1_38_1","unstructured":"Scott M Lundberg and Su-In Lee. 2017. A unified approach to interpreting model predictions. In Advances in neural information processing systems. 4765-4774."},{"key":"e_1_2_1_39_1","volume-title":"Applications and Computation of the Shapley Value in Databases and Machine Learning. In SIGMOD Conference Companion. ACM, 630-635","author":"Luo Xuan","year":"2024","unstructured":"Xuan Luo and Jian Pei. 2024. Applications and Computation of the Shapley Value in Databases and Machine Learning. In SIGMOD Conference Companion. ACM, 630-635."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.14778\/1880172.1880176"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.14778\/2733004.2733070"},{"key":"e_1_2_1_42_1","first-page":"1","article-title":"Enumeration and Updates for Conjunctive Linear Algebra Queries Through Expressibility. In ICDT (LIPIcs, Vol. 290)","volume":"12","author":"Thomas Mu","year":"2024","unstructured":"Thomas Mu n, oz, Cristian Riveros, and Stijn Vansummeren. 2024. Enumeration and Updates for Conjunctive Linear Algebra Queries Through Expressibility. In ICDT (LIPIcs, Vol. 290). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 12:1-12:20.","journal-title":"Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik"},{"key":"e_1_2_1_43_1","first-page":"326","article-title":"Using OBDDs for Efficient Query Evaluation on Probabilistic Databases. In SUM (Lecture Notes in Computer Science, Vol. 5291)","author":"Olteanu Dan","year":"2008","unstructured":"Dan Olteanu and Jiewen Huang. 2008. Using OBDDs for Efficient Query Evaluation on Probabilistic Databases. In SUM (Lecture Notes in Computer Science, Vol. 5291). Springer, 326-340.","journal-title":"Springer"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3651137"},{"key":"e_1_2_1_45_1","volume-title":"Opportunities for Data Management Research. In SIGMOD Conference. ACM, 2452-2457","author":"Pradhan Romila","year":"2022","unstructured":"Romila Pradhan, Aditya Lahiri, Sainyam Galhotra, and Babak Salimi. 2022. Explainable AI: Foundations, Applications, Opportunities for Data Management Research. In SIGMOD Conference. ACM, 2452-2457."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212053"},{"key":"e_1_2_1_47_1","first-page":"285","article-title":"The Impact of Negation on the Complexity of the Shapley Value in Conjunctive Queries","author":"Reshef Alon","year":"2020","unstructured":"Alon Reshef, Benny Kimelfeld, and Ester Livshits. 2020. The Impact of Negation on the Complexity of the Shapley Value in Conjunctive Queries. In PODS. ACM, 285-297.","journal-title":"PODS. ACM"},{"volume-title":"The Shapley value: essays in honor of Lloyd S. Shapley","author":"Roth Alvin E","key":"e_1_2_1_48_1","unstructured":"Alvin E Roth. 1988. The Shapley value: essays in honor of Lloyd S. Shapley. Cambridge University Press."},{"key":"e_1_2_1_49_1","doi-asserted-by":"crossref","unstructured":"Benedek Rozemberczki Lauren Watson P\u00e9ter Bayer Hao-Tsung Yang Oliver Kiss Sebastian Nilsson and Rik Sarkar. 2022. The Shapley Value in Machine Learning. In IJCAI. ijcai.org 5572-5579.","DOI":"10.24963\/ijcai.2022\/778"},{"volume-title":"Quantifying Causal Effects on Query Answering in Databases","author":"Salimi Babak","key":"e_1_2_1_50_1","unstructured":"Babak Salimi, Leopoldo E. Bertossi, Dan Suciu, and Guy Van den Broeck. 2016. Quantifying Causal Effects on Query Answering in Databases. In TaPP. USENIX Association."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1515\/9781400829156-012"},{"key":"e_1_2_1_52_1","unstructured":"Christoph Standke and Benny Kimelfeld. 2025. Tractability Frontiers of the Shapley Value for Aggregate Conjunctive Queries. arXiv:2509.13565 [cs.DB] https:\/\/arxiv.org\/abs\/2509.13565"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(79)90044-6"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.14778\/3579075.3579080"},{"key":"e_1_2_1_55_1","first-page":"563","article-title":"Explainable AI: A Brief Survey on History, Research Areas, Approaches and Challenges. In NLPCC (2) (Lecture Notes in Computer Science, Vol. 11839)","author":"Xu Feiyu","year":"2019","unstructured":"Feiyu Xu, Hans Uszkoreit, Yangzhou Du, Wei Fan, Dongyan Zhao, and Jun Zhu. 2019. Explainable AI: A Brief Survey on History, Research Areas, Approaches and Challenges. In NLPCC (2) (Lecture Notes in Computer Science, Vol. 11839). Springer, 563-574.","journal-title":"Springer"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3767720","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,12]],"date-time":"2025-11-12T16:09:05Z","timestamp":1762963745000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3767720"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,11,10]]},"references-count":55,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2025,11,10]]}},"alternative-id":["10.1145\/3767720"],"URL":"https:\/\/doi.org\/10.1145\/3767720","relation":{},"ISSN":["2836-6573"],"issn-type":[{"type":"electronic","value":"2836-6573"}],"subject":[],"published":{"date-parts":[[2025,11,10]]}}}