Introduction to Logic Programming WhatversusHow

 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)