Practical Datalog Rewriting for Existential Rules.

Existential rules is an expressive ontology formalism for ontology-mediated query answering and as a trade-off, query answering is of high complexity, while several tractable fragments have been identified. Existing systems are based on first-order rewriting methods and the resulting queries can be too large for DBMS to handle. It is shown that datalog rewriting can result in more compact queries but the previous study is mostly theoretical. A practical datalog rewriting algorithm is still missing. In this paper, we fill the gap by proposing a practical datalog rewriting algorithm for conjunctive query answering over existential rules, and establish its correctness over well known fragments of existential rules. Experiments on our prototype system showed superior or comparable performance over state-of-the-art systems on both the compactness of rewritings and the efficiency of query answering.