4 April 2025, 10:30-11:30.
ENS, room S16/FS101 (Aile Rataud, level -1).
No Cliques Allowed: The Next Step Towards FUS/FC Conjecture
Querying data sometimes calls for a logical layer between the user and the data to address challenges arising from distributed datasets, overly specific vocabulary, or incompleteness. Existential rules form an expressive knowledge representation language used for this purpose. However, query answering in the presence of existential rules presents several challenges.
One such challenge is undecidability, which is addressed through various approaches, including query rewriting. We define FUS as the class of existential rule sets for which query rewriting successfully determines entailment. Another challenge arises from the distinction between entailment over finite and infinite models: these two semantics differ, yet most tools are designed with infinite models in mind, whereas finite models better reflect actual databases. We call an existential rule set finitely controllable (FC) if the two semantics coincide.
A natural question, and a long-standing open conjecture, is whether FUS implies FC. We take a step toward a positive resolution of this conjecture by showing that universal models generated by FUS rule sets cannot contain arbitrarily large cliques without entailing a loop query. This simple yet elegant result narrows the space of potential counterexamples to the FUS/FC conjecture.
