Beefy Boxes and Bandwidth Generously Provided by pair Networks
No such thing as a small change

Re: Re: Re: Re: Choosing a data structure for AI applications

by Ovid (Cardinal)
on Jul 16, 2002 at 16:25 UTC ( #182141=note: print w/replies, xml ) Need Help??

in reply to Re: Re: Re: Choosing a data structure for AI applications
in thread Choosing a data structure for AI applications

Here's a very simple example that I pulled from

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.

  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).

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.


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

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://182141]
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others studying the Monastery: (7)
As of 2017-02-25 16:39 GMT
Find Nodes?
    Voting Booth?
    Before electricity was invented, what was the Electric Eel called?

    Results (366 votes). Check out past polls.