Ontology-based query answering is a problem that takes as input an ontology ℛ (typically expressed by existential rules), a set ℱ of facts, and a Boolean conjunctive query (CQ) , and asks whether ℛ, ℱ |= . This problem is undecidable in general, and a widely investigated approach to tackle it in some cases is query rewriting: given some “rule query” ⟨ℛ, ⟩, we compute a Boolean query ℛ such that, for any fact set ℱ , it holds that ℛ, ℱ |= if and only if ℱ |= ℛ. Previous work has mostly focused on output queries ℛ expressed as union of Boolean conjunctive queries (UCQs), and an efective algorithm that computes such a query ℛ 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 diference between datalog expressibility and datalog rewritability. More precisely, we show that query answering under datalog expressible rule queries is undecidable.
Eficiently accessing data is an important step in many real-world applications. Ontologies have been identified as an important tool to help a user to express their information needs, allowing them to use a vocabulary they are familiar with, while enabling a system to perform automated reasoning, leading to more complete answers. Ontology-based query answering (OBQA) is a core problem therein, where a set of facts is queried while taking into account the domain knowledge expressed in an ontology. These ontologies may be expressed in a variety of formalisms, such as Description Logics or existential rules. The OBQA problem is typically framed as follows: given a fact set ℱ , an ontology ℛ, and a Boolean CQ , check if ℱ , ℛ |= , where |= denotes the classical first-order logic entailment.
This problem is undecidable when the ontology can range over any set of existential rules. Thus,
a lot of research has focused on finding decidable and even tractable classes of rule sets; see [
Arbitrary Query Sig. Implemented ℋℐ ℋℐ Horn-ℒℋℐ
Horn-ℛℐ Bounded Detph rules Frontier guarded rules Nearly Guarded Rules
Guarded disj. rules
Guarded rules Warded rules
Linear Sticky(-join) disj. dat. disj. dat. datalog datalog datalog datalog datalog disj. datalog datalog datalog non rec. dat. non rec. dat.
×
×
×
×
×
✓
✓
×
✓
✓
×
×
×
×
×
×
×
✓
✓
✓
×
×
✓
✓
[
Syntactic conditions such as linearity [
As discussed in Section 2, there are many known and interesting classes for which specific datalog rewriting algorithms have been designed. However, no generic algorithm, such as in the case of UCQ expressibility, is known so far. The contribution of this paper is to show that, unfortunately, no such algorithm exists. This is done by proving that the problem of checking ℛ, ℱ |= under the assumption that ⟨ℛ, ⟩ is datalog expressible is undecidable, contradicting the existence of a rewriting algorithm for datalog expressible queries. We prove the result by reduction from the halting problem of Turing machines to OBQA, where the dificulty lies in ensuring that rule queries produced by the reduction are datalog expressible.
An extended version of this work with fully detailed proofs can be found in [
Let us first point out that there are several variations around the notion of datalog rewriting. A first dimension is that, rather than rewriting a specific rule query ⟨ℛ, ⟩, one can wish to rewrite ℛ into a datalog rule set ℛ′, and use ℛ′ to compute answers for a class of queries. Another variation is focused on the fact sets on which the rewriting should output the same answer as the original rule query. In this paper, we consider the strong version where answers should be the same on every fact set over the signature used in the rewritings. Quite often, defined datalog rewritings only preserve answers over fact sets on the original signature – this allows one to introduce fresh predicates which are known not to belong to fact sets on which the datalog program is to be evaluated. There are cases for which there exist datalog rewritings of rule queries for this relaxed definition but not for our restricted one; this is a consequence of Theorem 3 in [20]. Our undecidability result implies undecidability of this more relaxed notion.
The use of datalog as a target language for rewritings has been studied over the last 15 years. The
goal was to reduce reasoning task over expressive ontologies towards query answering over datalog,
for which optimization techniques have been developed in the database community. This is even more
important today, as a variety of eficient datalog reasoners have been implemented [ 21, 22]. Such an
approach has been proposed for providing disjunctive1 datalog rewritings for ℋℐ for fact entailment
over the original signature [
Beyond these fragment-specific reductions, the limits of datalog rewritability have been explored. In [13], it is shown that whenever rule queries have bounded depth (meaning that if they are entailed, they are entailed by a portion of the chase that uses only Skolem terms of bounded depth), they are datalog rewritable. This result applies for all syntactic fragment for which the chase is known to terminate [25], but datalog rewritability is not guaranteed (and not always possible) for rule sets having terminating restricted chase [26] – this is proven by a data complexity argument.
Another question of interest is the size of the obtained rewritings. In [16], the authors provide polynomial (disjunctive) datalog rewritings for (disjunctive) guarded rules queries. Non-recursive datalog has also been studied: while it does not increase the expressivity with respect to UCQs, the re-use of predicates allows to significanlty reduce the size of rewritings, reaching polynomiality in some cases [19, 27].
All of these contributions are summarised in Table 1.
To conclude, we discuss two distinct lines for future research, which naturally follow from our work. Answer Expressible Rule Sets We intend to study an even more restrictive class of rewritable rule sets: a rule set ℛ is answer datalog expressible if, for every CQ [⃗], the rule query ⟨ℛ, [⃗]⟩ admits some datalog rewriting that preserves all answers. That is, a datalog query ⟨ℛ′, ′[⃗]⟩ such that, for every fact set ℱ and every list ⃗ of constants occurring in ℱ , we have that ⟨ℛ, ℱ ⟩ |= [⃗/⃗] if and only if ⟨ℛ′, ℱ ⟩ |= [⃗/⃗]. With this definition in place, we consider the following problem: Open Problem 1. Consider a knowledge base = ⟨ℛ, ℱ ⟩, a CQ , and a list ⃗ of constants occurring in ℱ . Is there a procedure to check if ⃗ is an answer of with respect to ⟨ℛ, ℱ ⟩ that is sound, complete, and terminating if ℛ is answer datalog expressible?
The above question is quite relevant for our field of research, where we often study the theoretical properties of classes of rule sets and not of rule queries.
At the moment, we believe that the answer to this open problem is negative, which would yield a result strictly stronger than the one of this paper. However, a diferent proof strategy is required to show this since there are rule sets in the range of the reduction used for this result that are not answer datalog-rewritable.
Alternative Rewriting Languages In this paper, our primary focus is on datalog; in the future, we plan to study alternative query languages for rewritings. For instance, one could consider unions of Boolean conjunctive regular path queries (UBCRPQs) [28] and then consider the following problem: Open Problem 2. Is the class of all UBCRPQ expressible queries is UBCRPQ rewritable? Is there a procedure to check if a knowledge base ⟨ℛ, ℱ ⟩ entails a BCQ that is sound, complete, and terminates if the rule query ⟨ℛ, ⟩ is UCRPQ expressible?
We can instantiate diferent versions of this open problem by considering diferent output rewriting languages. For instance, we could consider as unions of (non-conjunctive) regular path queries, monadic 1For disjunctive existential rules and datalog, the reader is invited to consult [23] datalog, query languages based on context-free grammars [29], or any of the query languages considered by [30].
As a closing remark, note that the answers to the first and second questions in Open Problem 2 might be negative and positive, respectively. That is, it is possible that we can solve entailment for UCRPQ expressible rule queries even if we cannot efectively compute rewritings for these. This is an exciting possibility that may lead us to the discovery of a novel kind of reasoning procedure for this expressive class of rule queries. Or perhaps future research will just result in another undecidability result, which would again be strictly stronger than the main result of this paper. Either way, we look forward to researching (and hopefully settling!) these questions.
During the preparation of this work, the authors used Chat GPT in order to do grammar and spelling checks. After using this tool, the authors reviewed and edited the content as needed and take full responsibility for the publication’s content. shiqbs using decision diagrams and disjunctive datalog, Log. Methods Comput. Sci. 8 (2012). URL: https://doi.org/10.2168/LMCS-8(1:12)2012. doi:10.2168/LMCS-8(1:12)2012. [11] D. Carral, I. Dragoste, M. Krötzsch, The combined approach to query answering in horn-alchoiq, in: M. Thielscher, F. Toni, F. Wolter (Eds.), Principles of Knowledge Representation and Reasoning: Proceedings of the Sixteenth International Conference, KR 2018, Tempe, Arizona, 30 October - 2 November 2018, AAAI Press, 2018, pp. 339–348. URL: https://aaai.org/ocs/index.php/KR/KR18/ paper/view/18076. [12] D. Carral, L. González, P. Koopmann, From horn-sriq to datalog: A data-independent transformation that preserves assertion entailment, in: The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, The Thirty-First Innovative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, Honolulu, Hawaii, USA, January 27 - February 1, 2019, AAAI Press, 2019, pp. 2736–2743.
URL: https://doi.org/10.1609/aaai.v33i01.33012736. doi:10.1609/AAAI.V33I01.33012736. [13] B. Marnette, Resolution and Datalog rewriting under value invention and equality constraints,
CoRR abs/1212.0254 (2012). URL: http://arxiv.org/abs/1212.0254. arXiv:1212.0254. [14] V. Bárány, M. Benedikt, B. ten Cate, Rewriting guarded negation queries, in: K. Chatterjee, J. Sgall (Eds.), Mathematical Foundations of Computer Science 2013 - 38th International Symposium, MFCS 2013, Klosterneuburg, Austria, August 26-30, 2013. Proceedings, volume 8087 of Lecture Notes in Computer Science, Springer, 2013, pp. 98–110. URL: https://doi.org/10.1007/978-3-642-40313-2_11. doi:10.1007/978-3-642-40313-2\_11. [15] G. Gottlob, S. Rudolph, M. Simkus, Expressiveness of guarded existential rule languages, in: R. Hull, M. Grohe (Eds.), Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS’14, Snowbird, UT, USA, June 22-27, 2014, ACM, 2014, pp. 27–38. URL: https://doi.org/10.1145/2594538.2594556. doi:10.1145/2594538.2594556. [16] S. Ahmetaj, M. Ortiz, M. Simkus, Rewriting guarded existential rules into small datalog programs, in: B. Kimelfeld, Y. Amsterdamer (Eds.), 21st International Conference on Database Theory, ICDT 2018, March 26-29, 2018, Vienna, Austria, volume 98 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, pp. 4:1–4:24. URL: https://doi.org/10.4230/LIPIcs.ICDT.2018.4. doi:10.4230/ LIPICS.ICDT.2018.4. [17] M. Benedikt, M. Buron, S. Germano, K. Kappelmann, B. Motik, Rewriting the infinite chase, Proc.
VLDB Endow. 15 (2022) 3045–3057. URL: https://www.vldb.org/pvldb/vol15/p3045-benedikt.pdf. doi:10.14778/3551793.3551851. [18] G. Berger, G. Gottlob, A. Pieris, E. Sallinger, The space-eficient core of vadalog, ACM Trans.
Database Syst. 47 (2022) 1:1–1:46. URL: https://doi.org/10.1145/3488720. doi:10.1145/3488720. [19] G. Gottlob, T. Schwentick, Rewriting ontological queries into small nonrecursive datalog programs, in: G. Brewka, T. Eiter, S. A. McIlraith (Eds.), Principles of Knowledge Representation and Reasoning: Proceedings of the Thirteenth International Conference, KR 2012, Rome, Italy, June 10-14, 2012, AAAI Press, 2012. URL: http://www.aaai.org/ocs/index.php/KR/KR12/paper/view/4510. [20] M. Krötzsch, Eficient rule-based inferencing for OWL EL, in: T. Walsh (Ed.), IJCAI 2011, Proceedings of the 22nd International Joint Conference on Artificial Intelligence, Barcelona, Catalonia, Spain, July 16-22, 2011, IJCAI/AAAI, 2011, pp. 2668–2673. URL: https://doi.org/10.5591/ 978-1-57735-516-8/IJCAI11-444. doi:10.5591/978-1-57735-516-8/IJCAI11-444. [21] Y. Nenov, R. Piro, B. Motik, I. Horrocks, Z. Wu, J. Banerjee, Rdfox: A highly-scalable RDF store, in: M. Arenas, Ó. Corcho, E. Simperl, M. Strohmaier, M. d’Aquin, K. Srinivas, P. Groth, M. Dumontier, J. Heflin, K. Thirunarayan, S. Staab (Eds.), The Semantic Web - ISWC 2015 - 14th International Semantic Web Conference, Bethlehem, PA, USA, October 11-15, 2015, Proceedings, Part II, volume 9367 of Lecture Notes in Computer Science, Springer, 2015, pp. 3–20. URL: https: //doi.org/10.1007/978-3-319-25010-6_1. doi:10.1007/978-3-319-25010-6\_1. [22] J. Urbani, M. Krötzsch, C. J. H. Jacobs, I. Dragoste, D. Carral, Eficient model construction for horn logic with vlog - system description, in: D. Galmiche, S. Schulz, R. Sebastiani (Eds.), Automated Reasoning - 9th International Joint Conference, IJCAR 2018, Held as Part of the Federated Logic Conference, FloC 2018, Oxford, UK, July 14-17, 2018, Proceedings, volume 10900 of Lecture Notes in