Explaining Ontology-Mediated Query Answers Using Proofs over Universal Models

Research output: Contribution to book/conference proceedings/anthology/reportConference contributionContributedpeer-review


In ontology-mediated query answering, access to incomplete data sources is mediated by a conceptual layer constituted by an ontology, which can be formulated in a description logic (DL) or using existential rules. In the literature, there exists a multitude of complex techniques for incorporating ontological knowledge into queries. However, few of these approaches were designed for explainability of the query answers. We tackle this challenge by adapting an existing proof framework toward conjunctive query answering, based on the notion of universal models. We investigate the data and combined complexity of determining the existence of a proof below a given quality threshold, which can be measured in different ways. By distinguishing various parameters such as the shape of the query, we obtain an overview of the complexity of this problem for several Horn DLs.


Original languageEnglish
Title of host publicationProceedings of the 6th International Joint Conference on Rules and Reasoning (RuleML+RR’22)
EditorsGuido Governatori, Anni-Yasmin Turhan
PublisherSpringer, Berlin [u. a.]
Number of pages16
Publication statusPublished - 2022

Publication series

SeriesLecture Notes in Computer Science, Volume 13752

External IDs

Scopus 85145264903
dblp conf/ruleml/AlrabbaaBKK22
Mendeley a8b325a3-3a6c-31aa-9319-79ac11dfedd5
ORCID /0000-0001-9936-0943/work/142238130


Library keywords