| Summary: | Ontology-mediated query answering is a paradigm that
seeks to exploit the semantic knowledge expressed in terms of ontologies to improve query answers over incomplete data sources. In
this paper, we focus on description logic ontologies, and study the
problem of explaining why an ontology-mediated query is entailed
from a given data source. Specifically, we view explanations as minimal sets of assertions from an ABox, which satisfy the ontologymediated query. Based on such explanations, we study a variety of
problems taken from the recent literature on explanations (studied
for existential rules), such as recognizing all minimal explanations.
Our results establish tight connections between intractable explanation problems and variants of propositional satisfiability problems.
We provide insights on the inherent computational difficulty of deriving explanations for ontology-mediated queries.
|
|---|