Efficient Answer Enumeration in Description Logics with Functional Roles

We study the enumeration of answers to ontology-mediated queries when the ontology is formulated in a description logic that supports functional roles and the query is a CQ. In particular, we show that enumeration is possible with linear preprocessing and constant delay when a certain extension of the CQ (pertaining to functional roles) is acyclic and free-connex acyclic. This holds both for complete answers and for partial answers. We provide matching lower bounds for the case where the query is self-join free. In ontology-mediated querying, a query is combined with an ontology to enrich querying with domain knowledge and to facilitate access to incomplete and heterogeneous data (Bienvenu et al. 2014; Calvanese et al. 2009; Calì, Gottlob, and Lukasiewicz 2012) . Intense research has been carried out on the complexity of ontology-mediated querying, considering in particular description logics and existential rules as the ontology languages and conjunctive queries (CQs) as the actual queries. Most of the existing studies have concentrated on the basic problem of single-testing which means to decide, given an ontology-mediated query (OMQ) Q, a database D, and a candidate answer ā, whether ā is indeed an answer to Q on D. From the viewpoint of many practical applications, however, the assumption that a candidate answer is provided is hardly realistic and it seems much more relevant to enumerate, given an OMQ Q and a database D, all answers to Q on D. The investigation of answer enumeration for OMQs has recently been initiated in (Lutz and Przybylko 2022a) which also introduces useful new notions of minimal partial answers; such answers may contain wildcards to represent objects that are known to exist, but whose exact identity is unknown. If, for example, the ontology stipulates that Researcher ⊑ ∃worksFor.University Unversity ⊑ Academia and the database D is Researcher(mary), then there are no complete answers to the CQ q(x, y) = worksFor(x, y) ∧ Academia(y), but (mary, * ) is a minimal partial answer that conveys information which is otherwise lost. The ontologies in (Lutz