{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,7]],"date-time":"2024-08-07T23:34:11Z","timestamp":1723073651797},"reference-count":68,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGMOD Rec."],"published-print":{"date-parts":[[2023,8,10]]},"abstract":"Attribution scores can be applied in data management to quantify the contribution of individual items to conclusions from the data, as part of the explanation of what led to these conclusions. In Artificial Intelligence, Machine Learning, and Data Management, some of the common scores are deployments of the Shapley value, a formula for profit sharing in cooperative game theory. Since its invention in the 1950s, the Shapley value has been used for contribution measurement in many fields, from economics to law, with its latest researched applications in modern machine learning. Recent studies investigated the application of the Shapley value to database management. This article gives an overview of recent results on the computational complexity of the Shapley value for measuring the contribution of tuples to query answers and to the extent of inconsistency with respect to integrity constraints. More specifically, the article highlights lower and upper bounds on the complexity of calculating the Shapley value, either exactly or approximately, as well as solutions for realizing the calculation in practice.<\/jats:p>","DOI":"10.1145\/3615952.3615954","type":"journal-article","created":{"date-parts":[[2023,8,11]],"date-time":"2023-08-11T10:12:20Z","timestamp":1691748740000},"page":"6-17","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["The Shapley Value in Database Management"],"prefix":"10.1145","volume":"52","author":[{"given":"Leopoldo","family":"Bertossi","sequence":"first","affiliation":[{"name":"SKEMA Business School, Montreal, Canada"}]},{"given":"Benny","family":"Kimelfeld","sequence":"additional","affiliation":[{"name":"Technion - Israel Institute of Technology, Haifa, Israel"}]},{"given":"Ester","family":"Livshits","sequence":"additional","affiliation":[{"name":"University of Edinburgh, Edinburgh, United Kingdom"}]},{"given":"Mika\u00ebl","family":"Monet","sequence":"additional","affiliation":[{"name":"Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189 CRIStAL, Lille, France"}]}],"member":"320","published-online":{"date-parts":[[2023,8,11]]},"reference":[{"key":"e_1_2_1_1_1","series-title":"LIPIcs","first-page":"1","volume-title":"ICDT","author":"Amarilli A.","year":"2023","unstructured":"A. Amarilli . Uniform reliability for unbounded homomorphism-closed graph queries . In ICDT , volume 255 of LIPIcs , pages 14: 1 -- 14 :17, 2023 . A. Amarilli. Uniform reliability for unbounded homomorphism-closed graph queries. In ICDT, volume 255 of LIPIcs, pages 14:1--14:17, 2023."},{"key":"e_1_2_1_2_1","first-page":"4788","volume-title":"CIKM","author":"Arad D.","year":"2022","unstructured":"D. Arad , D. Deutch , and N. Frost . LearnShapley: Learning to predict rankings of facts contribution based on query logs . In CIKM , pages 4788 -- 4792 , 2022 . D. Arad, D. Deutch, and N. Frost. LearnShapley: Learning to predict rankings of facts contribution based on query logs. In CIKM, pages 4788--4792, 2022."},{"key":"e_1_2_1_3_1","first-page":"6670","volume-title":"AAAI","author":"Arenas M.","year":"2021","unstructured":"M. Arenas , P. Barcel\u00f3 , L. Bertossi , and M. Monet . The tractability of SHAP-score-based explanations for classification over deterministic and decomposable boolean circuits . In AAAI , pages 6670 -- 6678 , 2021 . M. Arenas, P. Barcel\u00f3, L. Bertossi, and M. Monet. The tractability of SHAP-score-based explanations for classification over deterministic and decomposable boolean circuits. In AAAI, pages 6670--6678, 2021."},{"issue":"63","key":"e_1_2_1_4_1","first-page":"1","article-title":"On the complexity of SHAP-score-based explanations: Tractability via knowledge compilation and non-approximability results","volume":"24","author":"Arenas M.","year":"2023","unstructured":"M. Arenas , P. Barcel\u00f3 , L. Bertossi , and M. Monet . On the complexity of SHAP-score-based explanations: Tractability via knowledge compilation and non-approximability results . Journal of Machine Learning Research , 24 ( 63 ): 1 -- 58 , 2023 . M. Arenas, P. Barcel\u00f3, L. Bertossi, and M. Monet. On the complexity of SHAP-score-based explanations: Tractability via knowledge compilation and non-approximability results. Journal of Machine Learning Research, 24(63):1--58, 2023.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/303976.303983"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-007-0080-z"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3294052.3322190"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-20528-7_15"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-020-01516-6"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/978-3-031-31414-8","volume-title":"Reasoning Web. Causality, Explanations and Declarative Knowledge","author":"Bertossi L.","year":"2023","unstructured":"L. Bertossi . Attribution-scores and causal counterfactuals as explanations in artificial intelligence . In Bertossi, L., Xiao, G. (eds.) Reasoning Web. Causality, Explanations and Declarative Knowledge . Springer LNCS 13759, pages 1 -- 23 , 2023 . L. Bertossi. Attribution-scores and causal counterfactuals as explanations in artificial intelligence. In Bertossi, L., Xiao, G. (eds.) Reasoning Web. Causality, Explanations and Declarative Knowledge. Springer LNCS 13759, pages 1--23, 2023."},{"key":"e_1_2_1_11_1","volume-title":"ACM","author":"Bertossi L.","year":"2020","unstructured":"L. Bertossi , J. Li , M. Schleich , D. Suciu , and Z. Vagena . Causality-based explanation of classification outcomes. In DEEM@SIGMOD, pages 6:1--6:10 . ACM , 2020 . L. Bertossi, J. Li, M. Schleich, D. Suciu, and Z. Vagena. Causality-based explanation of classification outcomes. In DEEM@SIGMOD, pages 6:1--6:10. ACM, 2020."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ijar.2017.07.010"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-016-9718-9"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3316416.3316418"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1613\/jair.1.12228"},{"key":"e_1_2_1_16_1","first-page":"403","volume-title":"PODS","author":"Calautti M.","year":"2022","unstructured":"M. Calautti , E. Livshits , A. Pieris , and M. Schneider . Counting database repairs entailing a query: The case of functional dependencies . In PODS , pages 403 -- 412 . ACM, 2022 . M. Calautti, E. Livshits, A. Pieris, and M. Schneider. Counting database repairs entailing a query: The case of functional dependencies. In PODS, pages 403--412. ACM, 2022."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1613\/jair.1391"},{"key":"e_1_2_1_18_1","first-page":"1643","volume-title":"AAMAS","author":"Cholvy L.","year":"2015","unstructured":"L. Cholvy , L. Perrussel , W. Raynaut , and J.-M. Th\u00e9venin . Towards consistency-based reliability assessment . In AAMAS , pages 1643 -- 1644 . ACM, 2015 . L. Cholvy, L. Perrussel, W. Raynaut, and J.-M. Th\u00e9venin. Towards consistency-based reliability assessment. In AAMAS, pages 1643--1644. ACM, 2015."},{"key":"e_1_2_1_19_1","volume-title":"The dichotomy of probabilistic inference for unions of conjunctive queries. Journal of the ACM (JACM), 59(6):1--87","author":"Dalvi N.","year":"2013","unstructured":"N. Dalvi and D. Suciu . The dichotomy of probabilistic inference for unions of conjunctive queries. Journal of the ACM (JACM), 59(6):1--87 , 2013 . N. Dalvi and D. Suciu. The dichotomy of probabilistic inference for unions of conjunctive queries. Journal of the ACM (JACM), 59(6):1--87, 2013."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1538788.1538810"},{"key":"e_1_2_1_21_1","first-page":"328","volume-title":"Proceedings of ECAI","author":"Darwiche A.","year":"2004","unstructured":"A. Darwiche . New advances in compiling CNF to decomposable negation normal form . In Proceedings of ECAI , pages 328 -- 332 . Citeseer , 2004 . A. Darwiche. New advances in compiling CNF to decomposable negation normal form. In Proceedings of ECAI, pages 328--332. Citeseer, 2004."},{"key":"e_1_2_1_22_1","first-page":"2373","volume-title":"SIGMOD Conference","author":"Davidson S. B.","year":"2022","unstructured":"S. B. Davidson , D. Deutch , N. Frost , B. Kimelfeld , O. Koren , and M. Monet . ShapGraph: An holistic view of explanations through provenance graphs and Shapley values . In SIGMOD Conference , pages 2373 -- 2376 . ACM, 2022 . S. B. Davidson, D. Deutch, N. Frost, B. Kimelfeld, O. Koren, and M. Monet. ShapGraph: An holistic view of explanations through provenance graphs and Shapley values. In SIGMOD Conference, pages 2373--2376. ACM, 2022."},{"key":"e_1_2_1_23_1","first-page":"362","volume-title":"CIKM","author":"Deutch D.","year":"2021","unstructured":"D. Deutch , N. Frost , A. Gilad , and O. Sheffer . Explanations for data repair through Shapley values . In CIKM , pages 362 -- 371 . ACM, 2021 . D. Deutch, N. Frost, A. Gilad, and O. Sheffer. Explanations for data repair through Shapley values. In CIKM, pages 362--371. ACM, 2021."},{"key":"e_1_2_1_24_1","first-page":"1570","volume-title":"SIGMOD","author":"Deutch D.","year":"2022","unstructured":"D. Deutch , N. Frost , B. Kimelfeld , and M. Monet . Computing the Shapley value of facts in query answering . In SIGMOD , pages 1570 -- 1583 , 2022 . D. Deutch, N. Frost, B. Kimelfeld, and M. Monet. Computing the Shapley value of facts in query answering. In SIGMOD, pages 1570--1583, 2022."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2022.102060"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285060"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10844-006-2974-4"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22152-1_31"},{"key":"e_1_2_1_29_1","series-title":"LNCS","first-page":"230","volume-title":"ECSQARU","author":"Grant J.","year":"2013","unstructured":"J. Grant and A. Hunter . Distance-based measures of inconsistency . In ECSQARU , volume 7958 of LNCS , pages 230 -- 241 . Springer , 2013 . J. Grant and A. Hunter. Distance-based measures of inconsistency. In ECSQARU, volume 7958 of LNCS, pages 230--241. Springer, 2013."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ijar.2016.04.004"},{"key":"e_1_2_1_31_1","first-page":"93","volume-title":"PODS","author":"Green T. J.","year":"2017","unstructured":"T. J. Green and V. Tannen . The semiring framework for database provenance. In E. Sallinger, J. V. den Bussche, and F. Geerts, editors , PODS , pages 93 -- 99 . ACM, 2017 . T. J. Green and V. Tannen. The semiring framework for database provenance. In E. Sallinger, J. V. den Bussche, and F. Geerts, editors, PODS, pages 93--99. ACM, 2017."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3236009"},{"key":"e_1_2_1_33_1","doi-asserted-by":"crossref","unstructured":"J. Y. Halpern. Actual Causality. MIT Press 2016. J. Y. Halpern. Actual Causality. MIT Press 2016.","DOI":"10.7551\/mitpress\/10809.001.0001"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1093\/bjps\/axi147"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1093\/bjps\/axi148"},{"key":"e_1_2_1_36_1","first-page":"249","volume-title":"KR","author":"Hunter A.","year":"2006","unstructured":"A. Hunter and S. Konieczny . Shapley inconsistency values . In KR , pages 249 -- 259 . AAAI Press , 2006 . A. Hunter and S. Konieczny. Shapley inconsistency values. In KR, pages 249--259. AAAI Press, 2006."},{"key":"e_1_2_1_37_1","first-page":"358","volume-title":"KR","author":"Hunter A.","year":"2008","unstructured":"A. Hunter and S. Konieczny . Measuring inconsistency through minimal inconsistent sets . In KR , pages 358 -- 366 . AAAI Press , 2008 . A. Hunter and S. Konieczny. Measuring inconsistency through minimal inconsistent sets. In KR, pages 358--366. AAAI Press, 2008."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2010.06.001"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/2764565"},{"key":"e_1_2_1_40_1","volume-title":"The complexity of the Shapley value for regular path queries. arXiv preprint arXiv:2212.07720","author":"Khalil M.","year":"2022","unstructured":"M. Khalil and B. Kimelfeld . The complexity of the Shapley value for regular path queries. arXiv preprint arXiv:2212.07720 , 2022 . M. Khalil and B. Kimelfeld. The complexity of the Shapley value for regular path queries. arXiv preprint arXiv:2212.07720, 2022."},{"key":"e_1_2_1_41_1","first-page":"187","volume-title":"PODS","author":"Kimelfeld B.","year":"2011","unstructured":"B. Kimelfeld , J. Vondr\u00e1k , and R. Williams . Maximizing conjunctive views in deletion propagation . In PODS , pages 187 -- 198 . ACM, 2011 . B. Kimelfeld, J. Vondr\u00e1k, and R. Williams. Maximizing conjunctive views in deletion propagation. In PODS, pages 187--198. ACM, 2011."},{"key":"e_1_2_1_42_1","first-page":"106","volume-title":"IJCAI","author":"Konieczny S.","year":"2003","unstructured":"S. Konieczny , J. Lang , and P. Marquis . Quantifying information and contradiction in propositional logic through test actions . In IJCAI , pages 106 -- 111 . Morgan Kaufmann , 2003 . S. Konieczny, J. Lang, and P. Marquis. Quantifying information and contradiction in propositional logic through test actions. In IJCAI, pages 106--111. Morgan Kaufmann, 2003."},{"key":"e_1_2_1_43_1","volume-title":"The Shapley value of tuples in query answering. Log. Methods Comput. Sci., 17(3)","author":"Livshits E.","year":"2021","unstructured":"E. Livshits , L. Bertossi , B. Kimelfeld , and M. Sebag . The Shapley value of tuples in query answering. Log. Methods Comput. Sci., 17(3) , 2021 . E. Livshits, L. Bertossi, B. Kimelfeld, and M. Sebag. The Shapley value of tuples in query answering. Log. Methods Comput. Sci., 17(3), 2021."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3056107"},{"key":"e_1_2_1_45_1","volume-title":"The Shapley value of inconsistency measures for functional dependencies. Log. Methods Comput. Sci., 18(2)","author":"Livshits E.","year":"2022","unstructured":"E. Livshits and B. Kimelfeld . The Shapley value of inconsistency measures for functional dependencies. Log. Methods Comput. Sci., 18(2) , 2022 . E. Livshits and B. Kimelfeld. The Shapley value of inconsistency measures for functional dependencies. Log. Methods Comput. Sci., 18(2), 2022."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3360904"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2020.10.001"},{"key":"e_1_2_1_48_1","first-page":"1182","volume-title":"SIGMOD","author":"Livshits E.","year":"2021","unstructured":"E. Livshits , R. Kochirgan , S. Tsur , I. F. Ilyas , B. Kimelfeld , and S. Roy . Properties of inconsistency measures for databases . In SIGMOD , pages 1182 -- 1194 . ACM, 2021 . E. Livshits, R. Kochirgan, S. Tsur, I. F. Ilyas, B. Kimelfeld, and S. Roy. Properties of inconsistency measures for databases. In SIGMOD, pages 1182--1194. ACM, 2021."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1038\/s42256-019-0138-9"},{"key":"e_1_2_1_50_1","first-page":"4765","volume-title":"NIPS","author":"Lundberg S. M.","year":"2017","unstructured":"S. M. Lundberg and S. Lee . A unified approach to interpreting model predictions . In NIPS , pages 4765 -- 4774 , 2017 . S. M. Lundberg and S. Lee. A unified approach to interpreting model predictions. In NIPS, pages 4765--4774, 2017."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2010.2049205"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.14778\/1880172.1880176"},{"key":"e_1_2_1_53_1","first-page":"11","article-title":"Explainable artificial intelligence: a comprehensive review","volume":"55","author":"Minh D.","year":"2021","unstructured":"D. Minh , H. Wang , Y. Li , and T. Nguyen . Explainable artificial intelligence: a comprehensive review . Artificial Intelligence Review , 55 , 11 2021 . D. Minh, H. Wang, Y. Li, and T. Nguyen. Explainable artificial intelligence: a comprehensive review. Artificial Intelligence Review, 55, 11 2021.","journal-title":"Artificial Intelligence Review"},{"key":"e_1_2_1_54_1","volume-title":"https:\/\/christophm.github.io\/interpretable-ml-book\/","author":"Molnar C.","year":"2019","unstructured":"C. Molnar . Interpretable Machine Learning . https:\/\/christophm.github.io\/interpretable-ml-book\/ , 2019 . C. Molnar. Interpretable Machine Learning. https:\/\/christophm.github.io\/interpretable-ml-book\/, 2019."},{"key":"e_1_2_1_55_1","first-page":"149","volume-title":"Proceedings of PODS","author":"Monet M.","year":"2020","unstructured":"M. Monet . Solving a special case of the intensional vs extensional conjecture in probabilistic databases . In Proceedings of PODS , pages 149 -- 163 , 2020 . M. Monet. Solving a special case of the intensional vs extensional conjecture in probabilistic databases. In Proceedings of PODS, pages 149--163, 2020."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11750-007-0021-4"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/TASE.2010.2052042"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.5555\/1642718"},{"key":"e_1_2_1_59_1","first-page":"285","volume-title":"PODS","author":"Reshef A.","year":"2020","unstructured":"A. Reshef , B. Kimelfeld , and E. Livshits . The impact of negation on the complexity of the Shapley value in conjunctive queries . In PODS , pages 285 -- 297 . ACM, 2020 . A. Reshef, B. Kimelfeld, and E. Livshits. The impact of negation on the complexity of the Shapley value in conjunctive queries. In PODS, pages 285--297. ACM, 2020."},{"key":"e_1_2_1_60_1","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511528446","volume-title":"The Shapley value : essays in honor of Lloyd S. Shapley","author":"Roth A. E.","year":"1988","unstructured":"A. E. Roth , editor. The Shapley value : essays in honor of Lloyd S. Shapley . Cambridge University Press , 1988 . A. E. Roth, editor. The Shapley value : essays in honor of Lloyd S. Shapley. Cambridge University Press, 1988."},{"key":"e_1_2_1_61_1","volume-title":"Quantifying causal effects on query answering in databases","author":"Salimi B.","year":"2016","unstructured":"B. Salimi , L. Bertossi , D. Suciu , and G. V. den Broeck . Quantifying causal effects on query answering in databases . In TaPP. USENIX Association , 2016 . B. Salimi, L. Bertossi, D. Suciu, and G. V. den Broeck. Quantifying causal effects on query answering in databases. In TaPP. USENIX Association, 2016."},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.14778\/3229863.3236253"},{"key":"e_1_2_1_63_1","first-page":"307","volume-title":"Contributions to the Theory of Games II","author":"Shapley L. S.","year":"1953","unstructured":"L. S. Shapley . A value for n-person games. In H. W. Kuhn and A. W. Tucker, editors, Contributions to the Theory of Games II , pages 307 -- 317 . Princeton University Press , Princeton , 1953 . L. S. Shapley. A value for n-person games. In H. W. Kuhn and A. W. Tucker, editors, Contributions to the Theory of Games II, pages 307--317. Princeton University Press, Princeton, 1953."},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1574-6526(07)03010-6"},{"key":"e_1_2_1_65_1","volume-title":"Probabilistic Databases. Synthesis Lectures on Data Management","author":"Suciu D.","year":"2011","unstructured":"D. Suciu , D. Olteanu , C. R\u00e9 , and C. Koch . Probabilistic Databases. Synthesis Lectures on Data Management . Morgan & Claypool Publishers , 2011 . D. Suciu, D. Olteanu, C. R\u00e9, and C. Koch. Probabilistic Databases. Synthesis Lectures on Data Management. Morgan & Claypool Publishers, 2011."},{"issue":"1","key":"e_1_2_1_66_1","first-page":"31","article-title":"On the compliance of rationality postulates for inconsistency measures: A more or less complete picture","volume":"31","author":"Thimm M.","year":"2017","unstructured":"M. Thimm . On the compliance of rationality postulates for inconsistency measures: A more or less complete picture . KI , 31 ( 1 ): 31 -- 39 , 2017 . M. Thimm. On the compliance of rationality postulates for inconsistency measures: A more or less complete picture. KI, 31(1):31--39, 2017.","journal-title":"KI"},{"issue":"1","key":"e_1_2_1_67_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s13278-017-0480-z","article-title":"A new approximation method for the Shapley value applied to the WTC 9\/11 terrorist attack","volume":"8","author":"van Campen T.","year":"2018","unstructured":"T. van Campen , H. Hamers , B. Husslage , and R. Lindelauf . A new approximation method for the Shapley value applied to the WTC 9\/11 terrorist attack . Soc. Netw. Anal. Min. , 8 ( 1 ):3: 1 -- 3 :12, 2018 . T. van Campen, H. Hamers, B. Husslage, and R. Lindelauf. A new approximation method for the Shapley value applied to the WTC 9\/11 terrorist attack. Soc. Netw. Anal. Min., 8(1):3:1--3:12, 2018.","journal-title":"Soc. Netw. Anal. Min."},{"key":"e_1_2_1_68_1","doi-asserted-by":"crossref","first-page":"851","DOI":"10.1613\/jair.1.13283","article-title":"On the tractability of SHAP explanations","volume":"74","author":"den Broeck G. Van","year":"2022","unstructured":"G. Van den Broeck , A. Lykov , M. Schleich , and D. Suciu . On the tractability of SHAP explanations . J. Artif. Intell. Res. , 74 : 851 -- 886 , 2022 . 69] M. Y. Vardi. The complexity of relational query languages. In STOC, pages 137--146. ACM, 1982. G. Van den Broeck, A. Lykov, M. Schleich, and D. Suciu. On the tractability of SHAP explanations. J. Artif. Intell. Res., 74:851--886, 2022. 69] M. Y. Vardi. The complexity of relational query languages. In STOC, pages 137--146. ACM, 1982.","journal-title":"J. Artif. Intell. Res."}],"container-title":["ACM SIGMOD Record"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3615952.3615954","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,11]],"date-time":"2023-08-11T10:14:48Z","timestamp":1691748888000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3615952.3615954"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,10]]},"references-count":68,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,8,10]]}},"alternative-id":["10.1145\/3615952.3615954"],"URL":"https:\/\/doi.org\/10.1145\/3615952.3615954","relation":{},"ISSN":["0163-5808"],"issn-type":[{"value":"0163-5808","type":"print"}],"subject":[],"published":{"date-parts":[[2023,8,10]]},"assertion":[{"value":"2023-08-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}