Datalog rewriting

We talk about datalog rewriting when we rewriting a query using a set of existential rules into a datalog program. It is also possible to rewriting directly a set of existential rules into a datalog program in order to derive all ground facts.

Open Questions

  • Is the existence of Datalog rewriting it decidable for general existential rules set ?
  • Can we build a Datalog rewriting of a rule set, when we know that it exists ?

Datalog rewriting of guarded rule set

The Datalog rewriting of guarded rule set is decidable.

In its master thesis DBLP:journals/corr/abs-1911-03679, Kevin Kappelmann studies some procedures for Datalog rewriting for (disjunctive) guarded rules. The hardness of the time complexity of Datalog rewriting algorithm is in general 2EXPTIME and EXPTIME, if the arity is bounded. There is algorithm that reaches this bound.

It is possible to rewriting a guarded rule set into a Datalog rule set of polynomial size DBLP:conf/icdt/AhmetajOS18.


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