First-Order Rewritability of Frontier-Guarded Ontology-Mediated Queries
This work addresses a fundamental problem for database and knowledge representation researchers concerning the expressivity and computability of ontology-mediated queries.
This paper investigates the first-order (FO) rewritability of ontology-mediated queries (OMQs) built upon frontier-guarded existential rules and conjunctive queries. The authors demonstrate that this problem is 2ExpTime-complete, providing semantic characterizations of FO-rewritability using both standard two-way alternating parity tree automata and more sophisticated cost automata.
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.