An Existential Rule Framework for Computing Why-Provenance On-Demand for Datalog

Ali ElhalawatiAli Elhalawati, Markus KrötzschMarkus Krötzsch, Stephan MennickeStephan Mennicke

Ali Elhalawati, Markus Krötzsch, Stephan Mennicke
An Existential Rule Framework for Computing Why-Provenance On-Demand for Datalog
In Guido Governatori, Anni-Yasmin Turhan, eds., Proceedings of the 6th International Joint Conference on Rules and Reasoning (RuleML+RR 2022), volume 13752 of LNCS, 146--163, 2022. Springer

Details
Bibtex

KurzfassungAbstract
Why-provenance — explaining why a query result is obtained — is an essential asset for reaching the goal of Explainable AI. For instance, recursive (Datalog) queries may show unexpected derivations due to complex entanglement of database atoms inside recursive rule applications. Provenance, and why-provenance in particular, helps debugging rule sets to eventually obtain the desired set of rules. There are three kinds of approaches to computing why-provenance for Datalog in the literature: (1) the complete ones, (2) the approximate ones, and (3) the theoretical ones. What all these approaches have in common is that they aim at computing provenance for all IDB atoms, while only a few atoms might be requested to be explained. We contribute an on-demand approach: After deriving all entailed facts of a Datalog program, we allow for querying for the provenance of particular IDB atoms and the structures involved in deriving provenance are computed only then. Our framework is based on terminating existential rules, recording the different rule applications. We present two implementations of the framework, one based on the semiring solver FPsolve, the other one based Datalog(S), a recent extension of Datalog by set terms. We perform experiments on benchmark rule sets using both implementations and discuss feasibility of provenance on-demand.
Projekt:Project: Cfaed, CPEC, KIMEDS, SECAI, ScaDS.AI
Forschungsgruppe:Research Group: Wissensbasierte SystemeKnowledge-Based Systems

The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-031-21541-4_10.

@inproceedings{EKM2022,
  author    = {Ali Elhalawati and Markus Kr{\"{o}}tzsch and Stephan Mennicke},
  title     = {An Existential Rule Framework for Computing Why-Provenance
               On-Demand for Datalog},
  editor    = {Guido Governatori and Anni-Yasmin Turhan},
  booktitle = {Proceedings of the 6th International Joint Conference on Rules
               and Reasoning (RuleML+RR 2022)},
  series    = {LNCS},
  volume    = {13752},
  publisher = {Springer},
  year      = {2022},
  pages     = {146--163},
  doi       = {10.1007/978-3-031-21541-4_10}
}