From Conjunctive Queries to Instance Queries in Ontology-Mediated Querying

We consider ontology-mediated queries (OMQs) based on expressive descriptionlogics of the ALC family and (unions) of conjunctive queries, studying therewritability into OMQs based on instance queries (IQs). Our results includeexact characterizations of when such a rewriting is possible and tightcomplexity bounds for deciding rewritability. We also give a tight complexitybound for the related problem of deciding whether a given MMSNP sentence isequivalent to a CSP.