  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.
