Résumé
Ontology-based query answering is a problem that takes as input an ontology R (in our context, a set of existential rules), a set F of facts, and a Boolean conjunctive query (CQ) q, and asks whether q follows from (R, F) under standard first-order semantics. This problem is undecidable in general, and a widely investigated approach to tackle it in some cases is query rewriting: given a "rule query" (R, q), we compute a Boolean query q' such that, for any fact set F, it holds that q follows from (R, F) if and only if q' follows from F. Insofar, previous work has mostly focused on output queries q' expressed as union of Boolean conjunctive queries (UCQs), and an effective algorithm that computes such a query q' whenever it exists has been proposed in the literature. However, UCQ-rewritability is not a very general notion and many real-world interesting rule queries do no admit UCQ-rewritings. This raises the question whether such a generic algorithm can be designed for a more expressive target language, such as datalog. We solve this question by the negative, by studying the difference between datalog-expressibility and datalog-rewritability. More precisely, we show that query answering under datalog-expressible rule queries is undecidable.