Introduction to
Logic Programming
What
versus
How
 

Exercise 6.1 - Subgoal Ordering


For each of the following sets of equivalent queries, say which query is best in terms of worst case evaluation complexity using our standard algorithm without indexing.

goal(X,Y,Z) :- p(X,Y) & q(X,X) & r(X,Y,Z)
goal(X,Y,Z) :- p(X,Y) & r(X,Y,Z) & q(X,X)
goal(X,Y,Z) :- q(X,X) & p(X,Y) & r(X,Y,Z)
goal(X,Y,Z) :- q(X,X) & r(X,Y,Z) & p(X,Y)
goal(X,Y,Z) :- r(X,Y,Z) & p(X,Y) & q(X,X)
goal(X,Y,Z) :- r(X,Y,Z) & q(X,X) & p(X,Y)
 
goal(X,Y,Z) :- p(X,Y) & q(a,b) & r(X,Y,Z)
goal(X,Y,Z) :- p(X,Y) & r(X,Y,Z) & q(a,b)
goal(X,Y,Z) :- q(a,b) & p(X,Y) & r(X,Y,Z)
goal(X,Y,Z) :- q(a,b) & r(X,Y,Z) & p(X,Y)
goal(X,Y,Z) :- >r(X,Y,Z) & p(X,Y) & q(a,b)
goal(X,Y,Z) :- r(X,Y,Z) & q(a,b) & p(X,Y)
 
goal(X,Y,Z) :- p(X,Y,Z) & q(X) & ~r(X,Y)
goal(X,Y,Z) :- p(X,Y,Z) & ~r(X,Y) & q(X)
goal(X,Y,Z) :- q(X) & p(X,Y,Z) & ~r(X,Y)
goal(X,Y,Z) :- q(X) & ~r(X,Y) & p(X,Y,Z)
goal(X,Y,Z) :- ~r(X,Y) & q(X) & p(X,Y,Z)
goal(X,Y,Z) :- ~r(X,Y) & p(X,Y,Z) & q(X)