On the Expressive Power of Ontology-Mediated Queries: Capturing coNP

Abstract

The complexity and relative expressiveness of Ontology-mediated Queries (OMQs) is quite well understood now. In this paper we study the absolute expressive power of OMQs, where the central question is to understand if a given OMQ language is expressive enough to capture all queries that can be computed within some bound on time or space. We consider this problem, and show that the OMQ language that pairs instance queries with an ontology in the very expressive DL ALCHOIF with closed predicates, despite being coNP-complete in data complexity, cannot capture all Boolean queries computable in coNP. Then we identify an extension of this DL that increases its expressive power sufficiently to capture all Boolean queries computable in coNP. The extension involves path expressions and nominal schemata, which are restricted in a way that they can be carefully incorporated into the existing mosaic technique for ALCHOIF with closed predicates without affecting the coNP upper bound in data complexity. As a consequence we get an OMQ language that captures precisely all Boolean queries computable in coNP.