Here's a very simple example that I pulled from http://www.csm.astate.edu/~rossa/cs3543/plect5.html.

on(red_box, table).
on(glove, red_box).
on(blue_box, table).
on(baseball, blue_box).
[download]

Let's say that I want to find all X that is on Y that, in turn, is on Z. I would issue the following query:

?- on(X,Y),on(Y,Z).
[download]

Here's how the backtracking works.

1. X = red_box, Y = table.
2. There are no facts where Y is the first argument to the fact, so this fails.
3. Prolog backtracks and sets X = glove, Y = red box.
4. Y is matches the first fact, so we have our first answer.
5. Prolog backtracks to match Y to another fact, but this fails.
6. X = blue_box. Y = table
7. Y does not match any first arguments, so this fails.
8. Prolog backtracks again and sets X = baseball and Y = blue_box.
9. Y matches the third fact, so we have our second answer.
10. Prolog backtracks to match Y to another fact, but this fails.
11. Prolog backtracks again and tries to set X to another argument, but no more arguments are available, so this fails and the unification of arguments to variables halts.

This is a trivial example (and I took some shortcuts - see the actual link above), but imagine what happens why we have facts embedded in facts and we need to gain information from those subfacts:

gives(ovid,book(learning_perl,[merlyn,rootbeer],publisher(o_reilly),th
+ird_edition),grep).
[download]

Now, if I issue queries against that (and we're in a proper SQL database), I have at least three tables that I need to span and potentially backtrack across. If my query is more complicated, the number of tables can rise dramatically.

You can also read this link for a more complicated example, or an example of how a bad database can lead to infinite recursion with backtracking.

Cheers,
Ovid

Join the Perlmonks Setiathome Group or just click on the the link and check out our stats.