Abstract
We consider ontology-mediated queries (OMQs) based on an EL
ontology and an atomic query (AQ), provide an ultimately
fine-grained analysis of data complexity and study rewritability
into linear Datalog-aiming to capture linear recursion in SQL.
Our main results are that every such OMQ is in AC0,
NL-complete or PTime-complete, and that containment in NL
coincides with rewritability into linear Datalog (whereas
containment in AC0 coincides with rewritability into first-order
logic). We establish natural characterizations of the three cases,
show that deciding linear Datalog rewritability (as well as the
mentioned complexities) is ExpTime-complete, give a way to
construct linear Datalog rewritings when they exist, and prove that
there is no constant bound on the arity of IDB relations in linear
Datalog rewritings.
Keywords
- Knowledge Representation, Reasoning, and Logic: Description Logics and Ontologies
- Multidisciplinary Topics and Applications: Database Systems
