CODEWITHSUNDEEP
datalog
EpsilonVector
EpsilonVector

Reputation: 4053

Why are the following Datalog programs equivalent?

For some existentional predicates a,b why is this: 

q(X,Y) <-- a(X,Y), q(Z,Y)
q(X,Y) <-- b(X,Y)

equivalent to this: 

q(X,Y) <-- a(X,Y), b(Z,Y)
q(X,Y) <-- b(X,Y)

? Why can't the top recursion just continue to expand?

Upvotes: 0

Views: 221

Answers (1)

Marcelo Cantos
Marcelo Cantos

Reputation: 185892

If you expand the first clause once, you get a(X,Y), a(Z,Y), b(Z′,Y). Since Z is free, a(Z,Y) is a simple existential quantifier on Y, which has already been asserted by the first clause, so the expression collapses to a(X,Y), b(Z′,Y), which is of course equivalent to a(X,Y), b(Z,Y), since Z′ is also a free variable.

Upvotes: 4

Related Questions