Why are the following Datalog programs equivalent?

Question

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?

Answer 1

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.