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. | [reply] [Watch: Dir/Any] [d/l] [select] |
This reminds me of Aristotelian logic and those circle diagrams. "All mammals have hair." "All mammals give birth live." "Some fish give birth live." "Do some fish have hair?" and be able to solve that.
I believe the backtracking issue has to do with finding out the answer to the question (ref:Above) What objects have attribute 'hair'?
The example maps to the following facts
- All mammals -> have hair
- All mammals -> give birth live
- Some fish -> give birth live
.. and then tries to backtrack to determine if 'giving birth live' maps to 'All mammals' and from there to 'have hair'.
--t. alex
"Mud, mud, glorious mud. Nothing quite like it for cooling the blood!"
--Michael Flanders and Donald Swann
| [reply] [Watch: Dir/Any] |