{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,15]],"date-time":"2026-07-15T07:13:02Z","timestamp":1784099582545,"version":"3.55.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T00:00:00Z","timestamp":1623715200000},"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":[[2021,6,15]]},"abstract":"<jats:p>Database tuples can be seen as players in the game of jointly realizing the answer to a query. Some tuples may contribute more than others to the outcome, which can be a binary value in the case of a Boolean query, a number for a numerical aggregate query, and so on. To quantify the contributions of tuples, we use the Shapley value that was introduced in cooperative game theory and has found applications in a plethora of domains. Specifically, the Shapley value of an individual tuple quantifies its contribution to the query. We investigate the applicability of the Shapley value in this setting, as well as the computational aspects of its calculation in terms of complexity, algorithms, and approximation.<\/jats:p>","DOI":"10.1145\/3471485.3471504","type":"journal-article","created":{"date-parts":[[2021,6,18]],"date-time":"2021-06-18T05:22:06Z","timestamp":1623993726000},"page":"78-85","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Query Games in Databases"],"prefix":"10.1145","volume":"50","author":[{"given":"Ester","family":"Livshits","sequence":"first","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Leopoldo","family":"Bertossi","sequence":"additional","affiliation":[{"name":"Univ. Adolfo Ib\u00e1\u00f1ez and Millennium Inst. Foundations of Data (IMFD), Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Benny","family":"Kimelfeld","sequence":"additional","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Moshe","family":"Sebag","sequence":"additional","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,6,17]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Model counting for conjunctive queries without self-joins. CoRR, abs\/1908.07093","author":"Amarilli A.","year":"2019","unstructured":"A. Amarilli and B. Kimelfeld . Model counting for conjunctive queries without self-joins. CoRR, abs\/1908.07093 , 2019 . To appear at ICDT 2021. A. Amarilli and B. Kimelfeld. Model counting for conjunctive queries without self-joins. CoRR, abs\/1908.07093, 2019. To appear at ICDT 2021."},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of AAAI, 2021","author":"Arenas M.","year":"2007","unstructured":"M. Arenas , P. Barcel\u00b4o , L. Bertossi , and M. Monet . The tractability of SHAP-scores over deterministic and decomposable boolean circuits . In Proceedings of AAAI, 2021 . CoRR abs\/ 2007 .14045. M. Arenas, P. Barcel\u00b4o, L. Bertossi, and M. Monet. The tractability of SHAP-scores over deterministic and decomposable boolean circuits. In Proceedings of AAAI, 2021. CoRR abs\/2007.14045."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/1540612"},{"key":"e_1_2_1_4_1","first-page":"99","volume-title":"STACS","author":"Aziz H.","year":"2014","unstructured":"H. Aziz and B. de Keijzer . Shapley meets Shapley . In STACS , pages 99 -- 111 , 2014 . 84 SIGMOD Record , March 2021 (Vol. 50, No. 1) H. Aziz and B. de Keijzer. Shapley meets Shapley. In STACS, pages 99--111, 2014. 84 SIGMOD Record, March 2021 (Vol. 50, No. 1)"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-20528-7_15"},{"key":"e_1_2_1_6_1","volume-title":"Declarative approaches to counterfactual explanations for classification. CoRR, abs\/2011.07423","author":"Bertossi L.","year":"2020","unstructured":"L. Bertossi . Declarative approaches to counterfactual explanations for classification. CoRR, abs\/2011.07423 , 2020 . Extended version of RuleML +RR'20 paper. L. Bertossi. Declarative approaches to counterfactual explanations for classification. CoRR, abs\/2011.07423, 2020. Extended version of RuleML+RR'20 paper."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3399579.3399865"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ijar.2017.07.010"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-016-9718-9"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/645504.656274"},{"key":"e_1_2_1_11_1","volume-title":"An interpretable model with globally consistent explanations for credit risk. CoRR, abs\/1811.12615","author":"Chen C.","year":"2018","unstructured":"C. Chen , K. Lin , C. Rudin , Y. Shaposhnik , S. Wang , and T. Wang . An interpretable model with globally consistent explanations for credit risk. CoRR, abs\/1811.12615 , 2018 . C. Chen, K. Lin, C. Rudin, Y. Shaposhnik, S. Wang, and T. Wang. An interpretable model with globally consistent explanations for credit risk. CoRR, abs\/1811.12615, 2018."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/1622487.1622491"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1538788.1538810"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/1316689.1316764"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2395116.2395119"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.4.2.99"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/2832249.2832325"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3056125"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/2832581.2832671"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1093\/bjps\/axi147"},{"key":"e_1_2_1_21_1","volume-title":"NeurIPS","author":"Karimi A.","year":"2020","unstructured":"A. Karimi , B. J. von K\u00a8ugelgen , B. Sch\u00a8olkopf , and I. Valera . Algorithmic recourse under imperfect causal knowledge: a probabilistic approach . In NeurIPS , 2020 . A. Karimi, B. J. von K\u00a8ugelgen, B. Sch\u00a8olkopf, and I. Valera. Algorithmic recourse under imperfect causal knowledge: a probabilistic approach. In NeurIPS, 2020."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3452021.3458313"},{"key":"e_1_2_1_23_1","series-title":"LIPIcs","first-page":"1","volume-title":"ICDT","author":"Livshits E.","year":"2020","unstructured":"E. Livshits , L. Bertossi , B. Kimelfeld , and M. Sebag . The shapley value of tuples in query answering . In ICDT , volume 155 of LIPIcs , pages 20: 1 -- 20 :19, 2020 . E. Livshits, L. Bertossi, B. Kimelfeld, and M. Sebag. The shapley value of tuples in query answering. In ICDT, volume 155 of LIPIcs, pages 20:1--20:19, 2020."},{"key":"e_1_2_1_24_1","volume-title":"The shapley value of inconsistency measures for functional dependencies. CoRR, abs\/2009.13819","author":"Livshits E.","year":"2020","unstructured":"E. Livshits and B. Kimelfeld . The shapley value of inconsistency measures for functional dependencies. CoRR, abs\/2009.13819 , 2020 . To appear at ICDT 2021. E. Livshits and B. Kimelfeld. The shapley value of inconsistency measures for functional dependencies. CoRR, abs\/2009.13819, 2020. To appear at ICDT 2021."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1038\/s42256-019-0138-9"},{"issue":"3","key":"e_1_2_1_26_1","first-page":"59","article-title":"Causality in databases","volume":"33","author":"Meliou A.","year":"2010","unstructured":"A. Meliou , W. Gatterbauer , J. Y. Halpern , C. Koch , K. F. Moore , and D. Suciu . Causality in databases . IEEE Data Eng. Bull. , 33 ( 3 ): 59 -- 67 , 2010 . A. Meliou, W. Gatterbauer, J. Y. Halpern, C. Koch, K. F. Moore, and D. Suciu. Causality in databases. IEEE Data Eng. Bull., 33(3):59--67, 2010.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/1880172.1880176"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1093\/jigpal\/exr002"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3387664"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.2000.0819"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/3026947.3026949"},{"key":"e_1_2_1_32_1","volume-title":"A Value for n-Person Games","author":"Shapley L. S.","year":"1952","unstructured":"L. S. Shapley . A Value for n-Person Games . RAND Corporation , Santa Monica, CA , 1952 . L. S. Shapley. A Value for n-Person Games. RAND Corporation, Santa Monica, CA, 1952."},{"key":"e_1_2_1_33_1","volume-title":"Shapley","author":"Shapley L. S.","year":"1988","unstructured":"L. S. Shapley and A. E. Roth . The Shapley value : essays in honor of Lloyd S . Shapley . Cambridge , 1988 . L. S. Shapley and A. E. Roth. The Shapley value : essays in honor of Lloyd S. Shapley. Cambridge, 1988."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1574-6526(07)03010-6"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/2031527"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/1795114.1795176"},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of AAAI, 2021","author":"Van den Broeck G.","year":"2009","unstructured":"G. Van den Broeck , A. Lykov , M. Schleich , and D. Suciu . On the tractability of SHAP explanations . In Proceedings of AAAI, 2021 . CoRR abs\/ 2009 .08634. G. Van den Broeck, A. Lykov, M. Schleich, and D. Suciu. On the tractability of SHAP explanations. In Proceedings of AAAI, 2021. CoRR abs\/2009.08634."}],"container-title":["ACM SIGMOD Record"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3471485.3471504","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3471485.3471504","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:17:26Z","timestamp":1750191446000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3471485.3471504"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,6,15]]}},"alternative-id":["10.1145\/3471485.3471504"],"URL":"https:\/\/doi.org\/10.1145\/3471485.3471504","relation":{},"ISSN":["0163-5808"],"issn-type":[{"value":"0163-5808","type":"print"}],"subject":[],"published":{"date-parts":[[2021,6,15]]},"assertion":[{"value":"2021-06-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}