Skip to main content

Explanations for Inconsistency−Tolerant Query Answering under Existential Rules

Thomas Lukasiewicz‚ Enrico Malizia and Cristian Molinaro


Querying inconsistent knowledge bases is a problem that has attracted a great deal of interest over the last decades. While several semantics of query answering have been proposed and their complexity is rather well-understood, little attention has been paid to the problem of explaining query answers. Explainability has recently become a prominent problem in different areas of AI. In particular, explaining query answers allow users to understand not only what is entailed by an inconsistent knowledge base, but also why. In this paper, we address the problem of explaining query answers for existential rules under three popular inconsistency-tolerant semantics, namely, the ABox repair (AR), the intersection of repairs (IAR), and the intersection of closed repairs (ICR) semantics. We provide a thorough complexity analysis for a wide range of existential rule languages and for different complexity measures.

Book Title
Proceedings of the 34th National Conference on Artificial Intelligence‚ AAAI 2020‚ New York‚ New York‚ USA‚ February 7–12‚ 2020
Vincent Conitzer and Fei Sha
AAAI Press