Information Technology Reference
In-Depth Information
Figure 2.3.
A trace of a query with a variable
Establish the query
george is a father of Y
.
1.
Look for
george is a father of Y
in the KB.
Nothing found.
2.
Look for
If . . . then george is a father of Y
in the KB.
Found:
If U is a child of V and V is male then V is a father of U.
This matches for
V=george
and
U=Y
.
3.
Work on the two if-parts of the matching conditional:
Establish the query
Y is a child of george
.
1. Look for
Y is a child of george
in the KB.
Found:
sue is a child of george
, which matches for
Y=sue
.
Return
success
for
Y is a child of george
with
Y=sue
.
Establish the query
george is male
.
1.
Look for
george is male
in the KB.
Found.
Return
success
for
george is male
.
Since both parts were successful, return
success
for the query
george is a father of Y
with
Y=sue
.
2.4.2 Another complication: Backtracking
Another complication can arise with variables in queries because there can be more
than one answer. It is possible that one answer is found, but that later in the back-
chaining procedure, the answer leads to failure. In this case, one must go back to
where the answer was found, and see if there is another answer to use in its place.
This is called
backtracking
and is best illustrated using an example.
Consider the query
P is a father of john
. The search is for someone whom John
is a child of and who is male, which is to say, Sam. How is the query handled by
back-chaining? A trace for it starts as follows:
1.
Look for
P is a father of john
in the KB.
Nothing found.
2.
Look for
If . . . then P is a father of john
in the KB.
Found:
If X is a child of Y and Y is male then Y is a father of X.
This matches for
X=john
and
Y=P
.
3.
Work on the two if-parts of the matching conditional:
