Preferred explanations for ontology−mediated queries under existential rules
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 minimalit...
| Main Authors: | , , , , |
|---|---|
| Format: | Conference item |
| Language: | English |
| Published: |
AAAI Press
2021
|
| _version_ | 1797064912042721280 |
|---|---|
| author | Ceylan, II Lukasiewicz, T Malizia, E Molinaro, C Vaicenavicius, A |
| author_facet | Ceylan, II Lukasiewicz, T Malizia, E Molinaro, C Vaicenavicius, A |
| author_sort | Ceylan, II |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-06T21:21:05Z |
| format | Conference item |
| id | oxford-uuid:417870c0-b88a-4bc1-bca7-28ac3c599006 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T21:21:05Z |
| publishDate | 2021 |
| publisher | AAAI Press |
| record_format | dspace |
| spelling | oxford-uuid:417870c0-b88a-4bc1-bca7-28ac3c5990062022-03-26T14:43:57ZPreferred explanations for ontology−mediated queries under existential rulesConference itemhttp://purl.org/coar/resource_type/c_5794uuid:417870c0-b88a-4bc1-bca7-28ac3c599006EnglishSymplectic ElementsAAAI Press2021Ceylan, IILukasiewicz, TMalizia, EMolinaro, CVaicenavicius, ARecently, 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. |
| spellingShingle | Ceylan, II Lukasiewicz, T Malizia, E Molinaro, C Vaicenavicius, A Preferred explanations for ontology−mediated queries under existential rules |
| title | Preferred explanations for ontology−mediated queries under existential rules |
| title_full | Preferred explanations for ontology−mediated queries under existential rules |
| title_fullStr | Preferred explanations for ontology−mediated queries under existential rules |
| title_full_unstemmed | Preferred explanations for ontology−mediated queries under existential rules |
| title_short | Preferred explanations for ontology−mediated queries under existential rules |
| title_sort | preferred explanations for ontology mediated queries under existential rules |
| work_keys_str_mv | AT ceylanii preferredexplanationsforontologymediatedqueriesunderexistentialrules AT lukasiewiczt preferredexplanationsforontologymediatedqueriesunderexistentialrules AT maliziae preferredexplanationsforontologymediatedqueriesunderexistentialrules AT molinaroc preferredexplanationsforontologymediatedqueriesunderexistentialrules AT vaicenaviciusa preferredexplanationsforontologymediatedqueriesunderexistentialrules |