Why(-Not)-Provenance for Datalog with Negation

Datalog is a powerful rule-based language with numerous applications in databases and knowledge representation. Explaining why a fact belongs to the output of a Datalog program over a database is an essential task towards explainable and transparent data-intensive applications. A standard way of explaining a fact is the so-called why-provenance, which provides witnesses in the form of subsets of the input database that as a whole can be used to derive that fact. While why-provenance for Datalog has been extensively studied in the literature, the analogous notion for Datalog with negation remains unexplored. We extend why-provenance to Datalog with negation under the standard well-founded and stable model semantics, inherited from Logic Programming, by building on justification theory. We then perform a thorough data complexity analysis of the underlying explainability problem and show that it is in general intractable for both well-founded and stable model semantics; in particular, it is NP-complete, which is the best that we can hope for since the problem is already NP-complete for positive Datalog.