http://www.perlmonks.org?node_id=182103


in reply to Choosing a data structure for AI applications

Anon has it right when s/he suggests a DB to build an internal "database". If you're looking for schemas, I'd look at doing a traits-type thing. Essentially, you'd have a table of things ("giving", "ovid", "book", "merlyn") and you'd have another table to associate them together as attributes of each other.

You'd also have to have subordinate relationships, ala "This book has this title" ... "All mammals have hair" ... etc. Those statements already have easy translations to SQL.

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.

(Yes, I'm rambling, but this is a wonderful topic.)

Does Prolog have "and" or "or" capabilities? Those could be useful. However, I would be very careful about working "if-then" of any sort in just yet. If you're curious why, we can get a nice OT meditation going, but it's beyond the scope of this thread.

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

Replies are listed 'Best First'.
Re: Re: Choosing a data structure for AI applications
by Ovid (Cardinal) on Jul 16, 2002 at 15:40 UTC

    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.

      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.

        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.

          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

      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