Почему следующие программы Datalog эквивалентны?

Question

Для некоторых существующих предикатов A, B Почему это:

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

эквивалентно этому:

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

? Почему верхняя рекурсия не может продолжать расширяться?

Answer 1

Если вы развернете первый пункт один раз, вы получите a(X,Y), a(Z,Y), b(Z′,Y). Анкет С Z. бесплатно, a(Z,Y) это простой экзистенциальный квантификатор на У, который уже был утвержден первым пунктом, поэтому выражение падает на a(X,Y), b(Z′,Y), что, конечно, эквивалентно a(X,Y), b(Z,Y), поскольку Z ′ также свободная переменная.