No Cliques Allowed: The Next Step Towards BDD/FC Conjecture
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917329527373824 |
|---|---|
| author | Larroque, Lucas Ostropolski-Nalewaja, Piotr Thomazo, Michaël |
| author_facet | Larroque, Lucas Ostropolski-Nalewaja, Piotr Thomazo, Michaël |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_09558 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | No Cliques Allowed: The Next Step Towards BDD/FC Conjecture Larroque, Lucas Ostropolski-Nalewaja, Piotr Thomazo, Michaël Databases 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. |
| title | No Cliques Allowed: The Next Step Towards BDD/FC Conjecture |
| topic | Databases |
| url | https://arxiv.org/abs/2603.09558 |