A journey to the frontiers of query rewritability - Ostropolski-Nalewaja, P. et al.

apropos: DBLP:conf/pods/Ostropolski-Nalewaja22

In this paper, the authors study the FUS/FES conjecture : saying that existential rule sets that are FES and FUS are also uniformly bounded.

They use the Bounded Derivation Depth (BDD) property, which is equivalent to FUS. It can be expressed as follow: \[\forall \phi~ \exists i~ \forall D~ Ch_{i}(D,R) \models \phi \Leftrightarrow D,R \models \phi\]

The observation about BDD/FUS class of rule sets is interesting (in the HAL tech report):

facts about terms are produced by the chase soon after the terms are created (with only a constant delay).

The observation should be true on guarded rules also see experiments with bounded chase in DBLP:journals/pvldb/BenediktBGKM22

They use the notion of local rule sets, i.e. rule sets for which the chase from any instance can be obtained from uniformly bounded subset of the data instance.

Prop: local rule sets are BDD. Th1 : every BDD over binary signature is local

Th2 : if a rule set is local and FES then it is UBDD

This post accepts webmentions. Do you have the URL to your post?

Otherwise, send your comment on my service.

Or interact from the fediverse with your username:

fediverse logo Share on the Fediverse