No Cliques Allowed: The Next Step Towards BDD/FC Conjecture
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, ∃ E (x,x). This simple yet elegant result narrows the space of potential counterexamples to the (bdd⇒fc) conjecture.
Authors
- Michaël Thomazo (ORCID: https://orcid.org/0000-0002-1437-6389)
- Lucas Larroque (ORCID: https://orcid.org/0009-0007-2351-2681)
- Piotr Ostropolski-Nalewaja (ORCID: https://orcid.org/0000-0002-8021-1638)
Institutions
- Centre National de la Recherche Scientifique (FR)
- Institut national de recherche en sciences et technologies du numérique (FR)
- University of Wrocław (PL)
- Université Paris Sciences et Lettres (FR)
- École Normale Supérieure - PSL (FR)
Publication Details
- Journal
- Proceedings of the ACM on Management of Data
- Published
- 2025-06-09
- DOI
- https://doi.org/10.1145/3725238
- Primary Topic
- Advanced Data Storage Technologies
- Type
- article
- Field-Weighted Citation Impact
- 0.00