This paper addresses one of the fundamental open questions in the realm of existential rules: the conjecture on the finite controllability of bounded derivation depth rule sets ( bdd ⇒fc). We take a step toward a positive resolution of this conjecture by demonstrating that universal models generated by bdd rule sets cannot contain arbitrarily large tournaments (arbitrarily directed cliques) without entailing a loop query, ∃ (, ). This simple yet elegant result narrows the space of potential counterexamples to the (bdd ⇒fc) conjecture.
ℐ, ℛ |= ⇐⇒ ℐ |= ℛ.
Given that the chase can produce an infinite structure, the UCQ-rewritability of a rule set ensures
decidable OBQA, as the rewriting can be computed and subsequently used to query the database.
Unsurprisingly, UCQ-rewritability has been the subject of extensive research, leading to the introduction
of numerous subclasses over the past few decades, including: linear theories, which permit at most a
single atom in rule bodies [
UCQ-rewritability is also studied independently under a number of diferent names — highlighting the fundamental nature of the property — with notable cases of finite unification sets class ( fus) and bounded derivation depth property (bdd). The fus class is closely tied to the concept of the backward chaining procedure, which is essentially a process of “chasing in reverse.” In this approach, to answer the entailment question, one starts with a query and attempts to derive a substructure of the database by applying rules in reverse. The bdd class has a much older origin, dating back to the 1980s. It stems from the classical notion of the boundedness of a Datalog program [17].
Definition 1. A rule set has bounded derivation depth (bdd) if for every CQ , there is some ≥ 0 such that for all instances ℐ, we have ⟨ ℐ, ℛ ⟩ |= if and only if is already entailed at step of the chase from ℐ and ℛ. We use bdd to denote the class of rule sets with bdd.
OBQA in the finite Databases, however, are finite structures, and under the understanding that ℐ is a partial description of the real world, and that ℛ are constraints that should hold on the finite real world, the classical notion of entailment provided by first-order logic does not correspond to the desired notion of entailment. Indeed, one should be more interested in knowing whether “q holds in any finite database that contains ℐ and is a model of ℛ”. This semantics is clearly related with the previous one, as a consequence of ℐ and ℛ in the unrestricted semantics is also one in the finite one. The converse is however not true, as the following prototypical example witnesses.
Example 2. Let us consider ℐ = {E(, )}, and ℛ containing the two rules ∀∀ E(, ) → ∃ E(, ) and ∀∀∀ E(, ) ∧ E(, ) → E(, ). The query ∃ E(, ) is not a consequence of ℐ, ℛ under the unrestricted semantics, as witnessed by the chase. In any finite model however, there must be a cycle, and hence a loop because of the transitivity enforced by the second rule.
Finite Controllability Finite reasoning provides us with a semi-decision procedure for nonentailment (enumerating finite interpretations, and checking whether there exists one that is not a model of ), but entailment is not semi-decidable anymore, as a finite universal model may not exist. An interesting question, already raised by Rosati [18], is, given a rule set ℛ, whether for any database ℐ and any query the unrestricted and the finite semantics coincide. If so, the rule set ℛ is said to be finitely controllable (fc). Note that whenever a rule set is fc, query answering becomes decidable. Indeed, the classical mathematical tools for semi-deciding first-order entailment are still available, while non-entailment can be witnessed by finite structures. Rosati showed that inclusion dependencies, a very restricted form of existential rules, enjoy finite controllability [ 18]. This has been generalized in two ways, for guarded rules [19], as well as for sticky rules [20]. Note that both classes generalize inclusion dependencies in various ways, guarded rules enjoying the bounded treewidth property, while sticky rules enjoy the bounded derivation depth property.
There is a well-known conjecture by Gogacz and Marcinkowski [21] stating that rule sets with the bounded derivation depth (bdd) property are finitely controllable ( bdd ⇒fc). Moreover, they demonstrated that the conjecture holds in a specific restricted setting where bdd rule sets are defined over a binary signature and have heads containing only a single atom [21]. However, this result applies to a highly limited case, and little progress has been made towards resolving the conjecture in its general form. The broader question of whether finite controllability extends to all bdd rule sets remains an important open problem.
Contributions Our main contribution is to show that bdd rule sets enjoy certain model-theoretic property. We write TournamentsE to denote the query: for all integers , there is a set { 1, . . . , } of elements in the given instance such that E(, ) or E( , ) holds in the instance for all ̸= , and write LoopE to denote the query ∃ E(, ). Then, the following is our main result: Theorem 3. For every bdd rule set ℛ and every instance ℐ: (ℐ, ℛ) |= LoopE. (ℐ, ℛ) |= TournamentsE ⇒
In addition to providing insights into the structural properties of universal models of bdd rule sets, this result serves as an important step towards proving the (bdd ⇒fc) conjecture. Specifically, it narrows the space of potential counterexamples to the conjecture by eliminating the most natural ones. We briefly explain why this is the case. First note that any model that entails TournamentsE and not LoopE is infinite, as the terms 1, . . . , in TournamentsE must be distinct for LoopE not to be entailed. Thus, TournamentsE does imply LoopE in the finite setting, and any bdd rule set for which this implication does not hold (in the unrestricted setting) would disprove (bdd ⇒fc).
Note however that Example 2 does not constitute such a counterexample, as its rule set is simply not bdd, since the transitivity rule has to be applied at least as many times as the distance between and to entail E(, ), which cannot be bounded independently of the size of the database. Expanding on that example, one could try to mimic the behavior using bdd rules by replacing the transitivity rule with ∀∀′∀∀′ E(, ′) ∧ E(, ′) → E(, ′), which entails it. With this change, the rule set is finally bdd, and the chase entails TournamentsE. However, this new rule triggers the entailment of ∃ E(, ) as soon as ∃∃ E(, ) is entailed, as expected due to Theorem 3.
While Theorem 3 does not entail the (bdd ⇒fc) conjecture, as a diferent type of counterexample could in principle exist, we are confident that the insights and carefully curated toolkit developed to tackle this case represent an important milestone in the efort to settle the ( bdd ⇒fc) conjecture in the general setting.
Organization of the proof The proof of Theorem 3 goes in two main steps. First, we introduce a series of rule set normalizations to constrain universal models of FUS rule sets in a more manageable structure. While some of these are well-known, the properties we require are tailored to the specific case at hand and need a separate formal proof. Then, we introduce the crucial notion of valley queries that are used to define the E predicate, and we show through a nice application of Ramsey theorem that such queries cannot define arbitrary tournaments.
An extended version of this work with fully detailed proofs can be found in [22].
Next steps A natural next step in this line of research is to establish that with UCQ-rewritable rule sets, one cannot define structures of arbitrarily high chromatic number without entailing the LoopE query: Conjecture 4. For every signature S, every UCQ-rewritable rule set ℛ over S, and every instance ℐ, we have: ℎ(ℐ, ℛ)|E cannot be colored with a finite number of colors ⇒
We believe that this conjecture, if proven, would constitute an elegant model-theoretic property of UCQ-rewritable rule sets and represent a significant step toward proving the ( bdd ⇒fc) conjecture. Let us elaborate. Similar to the results presented in this paper, if Conjecture 4 holds, it would eliminate a substantial portion of the potential counterexample space: any structure that cannot be colored with a finite number of colors cannot be homomorphically embedded into a finite structure that does not entail LoopE.
Our hope is that the tools developed throughout this paper will serve as a foundation for the proof of Conjecture 4. However, we note that such a proof would not be a straightforward extension of the techniques developed in this paper. The current proof aims at showing existence of four-tournament witnessed by a single valley query. We know, however, that there exists structures of arbitrarily high chromatic numbers that do not contain the four-clique: ℎ(ℐ, ℛ) |= LoopE.
Theorem 5 (Erdős [23]). There exist graphs with arbitrarily high girth and chromatic number. Piotr Ostropolski-Nalewaja was supported by grant 2022/45/B/ST6/00457 from the Polish National Science Centre (NCN).
Declaration on Generative AI The author(s) have not employed any Generative AI tools. [15] C. Civili, R. Rosati, On the first-order rewritability of conjunctive queries over binary guarded existential rules (extended abstract), 2015. [16] A. Calì, G. Gottlob, A. Pieris, Advanced processing for ontological queries, Proceedings of the
VLDB Endowment 3 (2010). doi:10.14778/1920841.1920912. [17] H. Gaifman, H. Mairson, Y. Sagiv, M. Y. Vardi, Undecidable optimization problems for database logic programs, J. ACM 40 (1993) 683–713. URL: https://doi.org/10.1145/174130.174142. doi:10. 1145/174130.174142. [18] R. Rosati, On the finite controllability of conjunctive query answering in databases under openworld assumption, J. Comput. Syst. Sci. 77 (2011) 572–594. URL: https://doi.org/10.1016/j.jcss.2010. 04.011. doi:10.1016/J.JCSS.2010.04.011. [19] V. Bárány, G. Gottlob, M. Otto, Querying the guarded fragment, in: 2010 25th Annual IEEE
Symposium on Logic in Computer Science, 2010, pp. 1–10. doi:10.1109/LICS.2010.26. [20] T. Gogacz, J. Marcinkowski, Converging to the chase – a tool for finite controllability, Journal of Computer and System Sciences 83 (2017) 180–206. URL: https://www.sciencedirect.com/science/ article/pii/S0022000016300617. doi:https://doi.org/10.1016/j.jcss.2016.08.001. [21] T. Gogacz, J. Marcinkowski, On the bdd/fc conjecture, in: Proceedings of the 32nd ACM SIGMODSIGACT-SIGAI Symposium on Principles of Database Systems, PODS ’13, Association for Computing Machinery, New York, NY, USA, 2013, p. 127–138. URL: https://doi.org/10.1145/2463664.2463668. doi:10.1145/2463664.2463668. [22] L. Larroque, P. Ostropolski-Nalewaja, M. Thomazo, No cliques allowed: The next step towards bdd/fc conjecture, Proc. ACM Manag. Data 3 (2025). doi:10.1145/3725238. [23] P. Erdös, Graph theory and probability, Canadian Journal of Mathematics 11 (1959) 34–38. doi:10.4153/CJM-1959-003-9.