on(red_box, table).
on(glove, red_box).
on(blue_box, table).
on(baseball, blue_box).
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).
Here's how the backtracking works.
- X = red_box, Y = table.
- There are no facts where Y is the first argument to the fact, so this fails.
- Prolog backtracks and sets X = glove, Y = red box.
- Y is matches the first fact, so we have our first answer.
- Prolog backtracks to match Y to another fact, but this fails.
- X = blue_box. Y = table
- Y does not match any first arguments, so this fails.
- Prolog backtracks again and sets X = baseball and Y = blue_box.
- Y matches the third fact, so we have our second answer.
- Prolog backtracks to match Y to another fact, but this fails.
- 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).
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. |