Ontology-Mediated Querying with the Description Logic EL: Trichotomy and Linear Datalog Rewritability
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.
Cite
Text
Lutz and Sabellek. "Ontology-Mediated Querying with the Description Logic EL: Trichotomy and Linear Datalog Rewritability." International Joint Conference on Artificial Intelligence, 2017. doi:10.24963/IJCAI.2017/164Markdown
[Lutz and Sabellek. "Ontology-Mediated Querying with the Description Logic EL: Trichotomy and Linear Datalog Rewritability." International Joint Conference on Artificial Intelligence, 2017.](https://mlanthology.org/ijcai/2017/lutz2017ijcai-ontology/) doi:10.24963/IJCAI.2017/164BibTeX
@inproceedings{lutz2017ijcai-ontology,
title = {{Ontology-Mediated Querying with the Description Logic EL: Trichotomy and Linear Datalog Rewritability}},
author = {Lutz, Carsten and Sabellek, Leif},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2017},
pages = {1181-1187},
doi = {10.24963/IJCAI.2017/164},
url = {https://mlanthology.org/ijcai/2017/lutz2017ijcai-ontology/}
}