Is single sided unification sufficient for Datalog?

Admin 1
Viewed 59

Datalog is easily identified with a subset of Prolog that doesn't use function symbols, but only constants and variables. But pure Datalog that doesn't use negation has a further constraint(*):

  1. Every fact is ground.
  2. Every variable in the head of a rule, also occurs in the body of the rule.

Can we conclude that single sided unification is enough to answer hierarchical Datalog queries? Or are there examples, demonstrable in SWI-Prolog 8.3.19 which has (=>)/2 for single sided

unfication, that are pure Datalog but do not run with single sided uniification?

(*)
What You Always Wanted to Know About Datalog
Ceri et. al. - 1989
https://www.researchgate.net/publication/3296132

unification datalog prolog
1 Answers

The answer is negative. A direct translation to simgle sided unfication already doesn't work for the simplest of Datalog facts and query:

p(a).

?- p(X).
X = a

If we take a Prolog fact P as P :- true, rewrite the fact via (=>)/2 into P => true. The thingy doesn't work anymore, demonstrated with SWI-Prolog 8.3.19:

p(a) => true.

?- p(X).
ERROR: No rule matches p(_2556)

Even Picat was bugged by this problem, and had initially special processing for facts. The recent release v3 of Picat even reintroduced Horn clauses.

Admin1
Related