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.

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

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.