From Conjunctive Queries to Instance Queries in Ontology-Mediated Querying

We consider ontology-mediated queries (OMQs) based on expressive description\nlogics of the ALC family and (unions) of conjunctive queries, studying the\nrewritability into OMQs based on instance queries (IQs). Our results include\nexact characterizations of when such a rewriting is possible and tight\ncomplexity bounds for deciding rewritability. We also give a tight complexity\nbound for the related problem of deciding whether a given MMSNP sentence is\nequivalent to a CSP.\n