No Cliques Allowed: The Next Step Towards BDD/FC Conjecture

Lucas Larroque, Piotr Ostropolski-Nalewaja, Michaël Thomazo

Abstract

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 $\Rightarrow$ 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, $\exists{x} E(x, x)$. This simple yet elegant result narrows the space of potential counterexamples to the (bdd $\Rightarrow$ fc) conjecture.
BibTeX
@article{larroque2025no,
  author = {Lucas Larroque and Piotr Ostropolski-Nalewaja and Michaël Thomazo},
  title = {{No Cliques Allowed: The Next Step Towards BDD/FC Conjecture}},
  journal = {Proc. ACM Manag. Data},
  year = {2025},
  doi = {10.1145/3725238},
}

Loading related content...

Figure