# Explaining Ontology-Mediated Query Answers using Proofs over Universal Models (Technical Report)

arXiv: https://arxiv.org/abs/2208.14381 · HTML: https://mlsanity.com/paper/2208.14381/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Aug 2022.

## Built on by (most cited first, 6 of 6)

- [Shapley Value Computation in Ontology-Mediated Query Answering](https://mlsanity.com/paper/2407.20058/) (2024)
- [Dialogue-based Explanations for Logical Reasoning using Structured Argumentation](https://mlsanity.com/paper/2502.11291/) (2025)
- [Tractable Responsibility Measures for Ontology-Mediated Query Answering](https://mlsanity.com/paper/2507.23191/) (2025)
- [Can You Tell the Difference? Contrastive Explanations for ABox Entailments](https://mlsanity.com/paper/2511.11281/) (2025)
- [How Hard is it to Decide if a Fact is Relevant to a Query?](https://mlsanity.com/paper/2604.22422/) (2026)
- [Recovering Explanations from Transformed Rule-Based Ontologies](https://mlsanity.com/paper/2608.06399/) (2026)

## Abstract (arXiv)

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.