Beefy Boxes and Bandwidth Generously Provided by pair Networks
more useful options
 
PerlMonks  

Re: Re: Choosing a data structure for AI applications

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


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

While driving into work I realized the problem with a pure database solution: backtracking. If I have to do much backtracking across several tables, disk access times are going to completely kill the performance. Imagine trying to issue a new SQL call every time I need to backtrack. Yuck. Of course, I can cache the SQL statements, but the only way to get around this problem (that occurs to me right now) is to preload the data. For the issues with that, see the root post of this thread :)

I think for small to medium size datasets, the database solution may be okay, though. I'll have to play with it.

Cheers,
Ovid

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


Comment on Re: Re: Choosing a data structure for AI applications
Re: Re: Re: Choosing a data structure for AI applications
by dragonchild (Archbishop) on Jul 16, 2002 at 15:55 UTC
    Can you give an example of backtracking issues that might arise?

    ------
    We are the carpenters and bricklayers of the Information Age.

    Don't go borrowing trouble. For programmers, this means Worry only about what you need to implement.

        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

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

      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.

      Cheers,
      Ovid

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

Re: Re: Re: Choosing a data structure for AI applications
by Anonymous Monk on Jul 16, 2002 at 17:03 UTC
    DBI can cache the results of db queries as well. There is also a RAM DB driver which I would be compatible with if I were you so that people can use your system with scripts without dealing with a RDBMS

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://182113]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others making s'mores by the fire in the courtyard of the Monastery: (15)
As of 2014-07-22 13:45 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My favorite superfluous repetitious redundant duplicative phrase is:









    Results (113 votes), past polls