First-Order Rewritability of Frontier-Guarded Ontology-Mediated Queries

First-Order Rewritability of Frontier-Guarded Ontology-Mediated Queries

Pablo Barceló, Gerald Berger, Carsten Lutz, Andreas Pieris

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Main track. Pages 1707-1713. https://doi.org/10.24963/ijcai.2018/236

We focus on ontology-mediated queries (OMQs) based on (frontier-)guarded existential rules and (unions of) conjunctive queries, and we investigate the problem of FO-rewritability, i.e., whether an OMQ can be rewritten as a first-order query. We adopt two different approaches. The first approach employs standard two-way alternating parity tree automata. Although it does not lead to a tight complexity bound, it provides a transparent solution based on widely known tools. The second approach relies on a sophisticated automata model, known as cost automata. This allows us to show that our problem is 2EXPTIME-complete. In both approaches, we provide semantic characterizations of FO-rewritability that are of independent interest.
Keywords:
Knowledge Representation and Reasoning: Description Logics and Ontologies
Multidisciplinary Topics and Applications: Databases