Leif Sabellek

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

2019 · arXiv (Cornell University)

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). Our main results are that every such OMQ is …