The idea: one rule base, two directions

A knowledge base here is a list of if-then rules plus some known facts. The page uses 8 rules about animals and 4 facts: the animal gives milk, eats meat, is tawny and has spots. The question is "is it a cheetah?" (or a tiger, or a penguin). There are two ways to answer it with the same rules. Forward chaining starts from the facts and applies rules until the goal appears: it is data-driven. Backward chaining starts from the goal and asks which rule could prove it, then what that rule needs: it is goal-driven.

The 8 rules as an AND-OR graph: the starting facts milk, meat, tawny and spots at the bottom, derived facts mammal, animal and carnivore in the middle, goals cheetah, tiger and penguin at the top. Arcs join the premises of each rule. An arrow up on the left is labelled forward, from the facts; an arrow down on the right is labelled backward, from the goal
Forward chaining climbs from the facts at the bottom; backward chaining digs down from the goal at the top.
ruleif all ofthen
R1hairmammal
R2milkmammal
R3feathersbird
R4mammal ∧ meatcarnivore
R5mammalanimal
R6carnivore ∧ tawny ∧ spotscheetah
R7carnivore ∧ tawny ∧ stripestiger
R8bird ∧ swimspenguin

Horn clauses and modus ponens

Each rule has one conclusion and a conjunction of premises. In logic this is a definite clause (a Horn clause with exactly one positive literal): carnivore ∧ tawny ∧ spots ⇒ cheetah. A fact is a rule with no premises. The only inference step both methods need is modus ponens: if all premises are known, the conclusion is known. For Horn clauses this step is sound and complete, so both methods give the same yes or no for every goal. They differ in how much work they do and in which order.

Forward chaining: agenda and counts

The forward algorithm (PL-FC-ENTAILS in Russell & Norvig) keeps an agenda, a queue of facts not yet processed, and for each rule a count of premises not yet known. It pops a fact, lowers the count of every rule that uses it, and when a count reaches 0 the rule fires: its conclusion is added to memory and to the agenda. It stops when the goal is added, or when the agenda is empty, a fixpoint where nothing new can be derived. Each fact is popped once and each premise is counted down once, so the run is linear in the size of the knowledge base. The count is the same trick as the indegree in Topological Sort (Using Indegree array).

For the cheetah, forward chaining fires R2 (mammal), R4 (carnivore), R5 (animal) and R6 (cheetah). It derives animal although the question never needed it (Demo 1). For the penguin it derives all 4 facts it can and only then, with an empty agenda, says no (Demo 4).

Backward chaining: a depth-first goal tree

Backward chaining proves a goal if it is in memory, or if some rule concludes it and every premise of that rule can be proved in turn. That is an AND-OR search: the rules for a goal are alternatives (OR), the premises of one rule must all hold (AND). The page tries rules in their order and premises left to right, depth first, like Prolog. When a premise fails, the rule fails at once and the search backtracks to the next rule. For mammal, R1 needs hair, which is not a fact and has no rule, so the search goes back and proves mammal with R2 and milk (Demo 2). The tiger fails at stripes after 8 goals (Demo 3); the penguin fails after only 3 goals, because bird needs feathers and the search never looks at mammals at all (Demo 5).

A goal that is already on the current path is treated as failed. Without this loop check, rules such as a ⇒ b and b ⇒ a would make the search run forever. Backward chaining also never writes to memory, so it can prove the same subgoal again for another query; real systems cache proved goals (tabling).

See also Depth-First Search for the order the goal tree is explored in, and Constraint Satisfaction: Backtracking Search for backtracking over variable values.

Which direction to use

The query penguin both ways. Left, forward chaining pops 8 facts: milk makes R2 add mammal, mammal makes R4 and R5 add carnivore and animal, carnivore makes R6 add cheetah; the agenda empties and the answer is no after 4 rules fired. Right, backward chaining: penguin needs bird by R8, bird needs feathers by R3, feathers has no fact and no rule, so all three fail, swims is never tried, 3 goals, answer no
For "is it a penguin?" forward chaining derives 4 facts that do not help; backward chaining touches 3 goals and stops.
forward chainingbackward chaining
starts fromthe factsthe goal
work doneeverything the facts imply, needed or notonly rules relevant to the goal
costlinear in the knowledge basecan be much less, but may repeat subgoals
good whennew facts keep arriving and you want every consequence (monitoring, production systems)you ask a specific question (diagnosis, Prolog queries)
work for cheetah / tiger / penguin4 / 4 / 4 rules fired8 / 8 / 3 goals tried

The probabilistic cousin of this reasoning, with degrees of belief instead of true and false, is Bayesian Network Inference.

What the page leaves out

The rules are propositional: no variables, so there is no unification as in first-order forward chaining or Prolog. There is no negation, no conflict resolution strategy (salience, recency) as in production systems like CLIPS or Drools, and no Rete network that shares premise tests between rules. Backward chaining here has no tabling or caching, and the page leaves out resolution, the inference rule that also handles clauses that are not Horn.