Pourquoi les programmes Datalog suivants sont-ils équivalents?

Question

Pour certains existentional prédicats a, b pourquoi est-ce:

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

équivalent à ceci:

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

? Pourquoi la récursion supérieure ne peut-elle pas continuer à se développer?

Answer 1

Si vous développez la première clause une fois, vous obtenez a(X,Y), a(Z,Y), b(Z′,Y). Depuis Z est libre, a(Z,Y) est un simple quantificateur existentiel sur Y, qui a déjà été affirmé par la première clause, de sorte que l'expression se réduit à a(X,Y), b(Z′,Y), ce qui est évidemment équivalent à a(X,Y), b(Z,Y), puisque Z ' est également une variable libre.