A Procedure for Thinking - Thinking as Computation - page 34

Establish the query john is a child of P .
1. Look for john is a child of P in the KB.
Found: john is a child of sue , which matches for P=sue .
Return success for john is a child of P with P=sue .
Establish the query sue is male .
Let us stop here and review what has happened so far. The query john is a child of P
succeeded. But the first answer found, looking from top to bottom in the KB, was sue .
This answer is going to be a problem later: the subquery P is male with P=sue will
fail. If there were no backtracking, the whole query would fail. So after discovering
that the subquery sue is male fails, the back-chaining procedure must backtrack to the
subquery john is a child of P and look for other possibilities. The value sam for P will
then be found, and the rest of the query will eventually succeed.
So just as step 4 of the back-chaining procedure requires going back to step 2 and
considering other options if things do not work out for the P i subqueries, backtracking
requires going back and reconsidering the choice of values for variables if things do
not work out.
It is possible to redesign the back-chaining procedure in figure 2.2 to make this
backtracking explicit, but this is not done here. (The back-chaining procedure shown
in figure 3.12 does take this complication into account.) Suffice it to say that the
procedure searches the KB for a matching atomic or conditional sentence, from top to
bottom and from left to right, and returns the first match found. But it must be able
to search for other matches if the first match causes problems later.
2.4.3 A more complex query
Let us now consider a more complex query: george is a grandfather of john . The trace
is shown in figure 2.4. Although this query does not itself include variables, variables
are introduced for subqueries along the way. For example, a matching conditional in
step 2 gives us a value for the variables X and Z but leaves the Y unspecified. This is
why in the next step there is a subquery with a variable: george is a father of Y .So
even if a top-level query has no variables, back-chaining would still need to handle
subqueries with variables.
Next, in step 3 of figure 2.4, there are two subqueries: george is a father of Y and Yis
a parent of john . The first one was traced in figure 2.3 and succeeds with Y=sue . (This
is a good value, and no backtracking will be needed.)