International Conference on Database Theory (ICDT) 2026
Résumé
Bibtex
@InProceedings{bienvenu_et_al:LIPIcs.ICDT.2026.20,
author = {Bienvenu, Meghyn and Figueira, Diego and Lafourcade, Pierre},
title = {{Responsibility Measures for Conjunctive Queries with Negation}},
booktitle = {29th International Conference on Database Theory (ICDT 2026)},
pages = {20:1--20:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-413-0},
ISSN = {1868-8969},
year = {2026},
volume = {365},
editor = {ten Cate, Balder and Funk, Maurice},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2026.20},
URN = {urn:nbn:de:0030-drops-256340},
doi = {10.4230/LIPIcs.ICDT.2026.20},
annote = {Keywords: query responsibility measures, conjunctive queries with negation, non-monotone queries, Shapley value, explainability, weighted sums of minimal supports (WSMS)},
abstract = {We contribute to the recent line of work on responsibility measures that quantify the contributions of database facts to obtaining a query result. In contrast to existing work which has almost exclusively focused on monotone queries, here we explore how to define responsibility measures for unions of conjunctive queries with negated atoms (UCQ^¬s). After first investigating the question of what constitutes a reasonable notion of qualitative explanation or relevance for queries with negated atoms, we propose two approaches, one assigning scores to (positive) database facts and the other also considering negated facts. Our approaches, which are orthogonal to the previously studied score of Reshef et al. [Alon Reshef et al., 2020], can be used to lift previously studied scores for monotone queries, known as drastic Shapley and weighted sums of minimal supports (WSMS), to UCQ^¬s. We investigate the data and combined complexity of the resulting measures, notably showing that the WSMS measures are tractable in data complexity for all UCQ^¬s and further establishing tractability in combined complexity for suitable classes of conjunctive queries with negation.}
}