A Complete Classification of the Complexity and Rewritability of Ontology-Mediated Queries based on the Description Logic EL

Carsten Lutz, Leif Sabellek

We provide an ultimately fine-grained analysis of the data complexity and rewritability of ontology-mediated queries (OMQs) based on an EL ontology and a conjunctive query (CQ). Ou…