Recently, explanations for query answers under existential rules have been investigated, where an explanation is an inclusion-minimal subset of a given database that, together with the ontology, entails the query. In this paper, we take a step further and study explanations under different minimality criteria. In particular, we first study cardinality-minimal explanations and hence focus on deriving explanations of minimum size. We then study a more general preference order induced by a weight distribution. We assume that every database fact is annotated with a (penalization) weight, and we are interested in explanations with minimum overall weight. For both preference orders, we study a variety of explanation problems, such as recognizing a preferred explanation, all preferred explanations, a relevant or necessary fact, and the existence of a preferred explanation not containing forbidden sets of facts. We provide a detailed complexity analysis for all the aforementioned problems, thereby providing a more complete picture for explaining query answers under existential rules.
Preferred Explanations for Ontology-Mediated Queries under Existential Rules / CEYLAN İSMAIL İLKAN; LUKASIEWICZ THOMAS; MALIZIA E; MOLINARO CRISTIAN; VAICENAVIČIUS ANDRIUS. - STAMPA. - 35:7(2021), pp. 6262-6270. (Intervento presentato al convegno AAAI 2021 tenutosi a Online nel 2/02/2021 - 9/02/2021).
Preferred Explanations for Ontology-Mediated Queries under Existential Rules
MALIZIA E;
2021
Abstract
Recently, explanations for query answers under existential rules have been investigated, where an explanation is an inclusion-minimal subset of a given database that, together with the ontology, entails the query. In this paper, we take a step further and study explanations under different minimality criteria. In particular, we first study cardinality-minimal explanations and hence focus on deriving explanations of minimum size. We then study a more general preference order induced by a weight distribution. We assume that every database fact is annotated with a (penalization) weight, and we are interested in explanations with minimum overall weight. For both preference orders, we study a variety of explanation problems, such as recognizing a preferred explanation, all preferred explanations, a relevant or necessary fact, and the existence of a preferred explanation not containing forbidden sets of facts. We provide a detailed complexity analysis for all the aforementioned problems, thereby providing a more complete picture for explaining query answers under existential rules.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.