Information Technology Reference
In-Depth Information
query, and the procedure needs to have the right values for those variables when
going on to
A
2
.
As mentioned in chapter 2, the back-chaining procedure is
recursive
. This means
that part of what it takes to execute the procedure (for certain inputs) involves exe-
cuting that same procedure on some other inputs. In this case, part of what it takes
to do back-chaining on a query is to do back-chaining on another query. This is what
happens in step 3d.
To establish the query
A
1
,
A
2
, ...,
A
n
,
the procedure tries to establish the query
B
1
,
B
2
, ...,
B
m
,
A
2
, ...,
A
n
.
How can this possibly work? It might seem that working on this new query, the
procedure would get to step 3d again and find another clause whose head matches
B
1
and whose body is
C
1
,
...
,
C
k
. Does this not go on forever, producing longer and
longer queries?
It might. Back-chaining
can
get stuck in a loop and never finish.
However, in other cases, the query that arises in step 3d will be easier to solve than
the original one. For example, there may be no body at all in the clause that matches
A
1
, in which case, the procedure goes from a query with
n
atoms to one with
(
−
)
n
1
atoms (and eventually to
, and so on, until it gets to 0). Or perhaps there is a
body, but it may be able to deal with
B
1
directly in one step (when there is a matching
clause that has no body).
At any rate, for back-chaining to return
success
, it must first deal with
A
1
by dealing
with any
B
i
atoms that it finds, which may result in dealing with
C
i
atoms (and
perhaps
D
i
atoms, and so on). When these are all done, then (and only then) does
back-chaining go on to the
A
2
and the procedure continues (possibly leading to new
B
i
atoms, as before).
A
3
is dealt with in the same way. Eventually, one of two things
happens: either the procedure cannot establish one of these
A
i
no matter what it tries,
in which case it returns
failure
; or the procedure gets through all the
A
i
and ends up
with the empty conjunctive query, in which case it returns
success
.
Note that in handling
A
1
, the procedure looks for clauses to use and then tries to
establish a new conjunctive query. If this new query fails, it is not yet done. In fact,
it may have failed because the clause it chose for
A
1
was not a good one. (It may not
be a good one even if it has no body; the unification may require bindings for the
variables in
A
1
that will not work for
A
2
, say.) So instead of immediately returning
failure
after the recursive query fails in step 3d, the procedure backtracks and looks
(
−
)
n
2
