3.2 Forward- and Backward-Chaining Rule Engines 55
there must be a mechanism to prevent rules from firing endlessly on the same
facts. A rule is normally only invoked once on a particular set of facts that
match the rule. When the rule engine finds that no new facts can be inferred,
it stops. At that point one can query the knowledge base.
Backward-chaining rule engines are much harder to understand. They
maintain a knowledge base of facts, but they do not perform all possible
inferences that a forward-chaining rule engine would perform. Rather, a
backward-chaining engine starts with the query to be answered. The engine
then tries to determine whether it is already known (i.e., it can be answered
with known facts in the knowledge base). If so, then it simply retrieves the
facts. If the query cannot be answered with known facts, then it examines
the rules to determine whether any one of them could be used to deduce the
answer to the query. If there are some, then it tries each one. For each such
rule, the rule engine tries to determine whether the hypothesis of the rule is
true. It does this the same way as it does for answering any query: the en-
gine first looks in the knowledge base and then the engine tries to deduce it
by using a rule.
Thus a backward-chaining rule engine is arguing backward from the de-
sired conclusion (sometimes called the “goal”) to the known facts in the
knowledge base. In contrast with the forward-chaining technique that match-
es the hypothesis and then performs the corresponding action, a backward-
chaining engine will match the conclusion and then proceed backward to the
hypothesis. Actions are performed only if the hypothesis is eventually veri-
fied. Rules are invoked only if they are relevant to the goal. Thus actions that
would be performed by a forward-chaining engine might not be performed
by a backward-chaining engine. On the other hand, actions that would be
performed just once by a forward-chaining engine could be performed more
than once by a backward-chaining engine.
The best-known example of a backward-chaining rule engine is the Prolog
programming language (Clocksin et al. 2003). However, there are many oth-
ers, especially commercial business rule engines, which are discussed later
in this chapter.
Backward chainers have some nice features. Because of their strong focus
on a goal, they only consider relevant rules. This can make them very fast.
However, they also have disadvantages. They are much more prone to infi-
nite loops than forward-chaining engines, and it is difficult to support some
forms of reasoning such as paramodulation, which is needed by OWL on-
tologies (see section 4.4). Programming in backward-chaining mode is also
counterintuitive. As a result it takes considerable skill to do it well com-