
doi: 10.1145/3725238
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.
Bounded Derivation Depth Property, CCS Concepts: Theory of computation → Constraint and logic programming Finite Model Theory Automated reasoning Logic and databases Chase, Logic and databases Chase, Automated reasoning, CCS Concepts:, Finite unification sets, TGDs, FC/BDD Conjecture, Theory of computation → Constraint and logic programming, [INFO.INFO-DB] Computer Science [cs]/Databases [cs.DB], Existential Rules, Tuple Generating Dependencies, BDD, FO-Rewritability, Finite Model Theory, FUS, Finite Controllability
Bounded Derivation Depth Property, CCS Concepts: Theory of computation → Constraint and logic programming Finite Model Theory Automated reasoning Logic and databases Chase, Logic and databases Chase, Automated reasoning, CCS Concepts:, Finite unification sets, TGDs, FC/BDD Conjecture, Theory of computation → Constraint and logic programming, [INFO.INFO-DB] Computer Science [cs]/Databases [cs.DB], Existential Rules, Tuple Generating Dependencies, BDD, FO-Rewritability, Finite Model Theory, FUS, Finite Controllability
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
