Learn how easy it is to sync an existing GitHub or Google Code repo to a SourceForge project! See Demo

Close

#2 Differential tabling

open
nobody
None
5
2004-08-15
2004-08-15
Jim Bowery
No

The reason I ran across XSB was I was looking for a
relational system that did not only memoization (I then
discovered "tabling" was a synonym used in the prolog
world) but, could support ongoing observation of a
query for changes in the database. This would result
in a feature something like:

:-observe(p(X)).

which would operate as a normal query except that
instead of terminating after ouputting the current
state of the query, it would start delivering asserts
and retracts to modify the current state of the query
in accordance with the changes in the underlying database.

Is this pie-in-the-sky wishful thinking or is it
doable? Seems to me with tabling you're one step away
from making it doable.

Most real world programming problems boil down to
nothing more than keeping a currently observed state up
to date, but people keep solving the problem in bad ways.

Discussion

  • Logged In: YES
    user_id=13069

    It is not completely pie-in-the-sky, but I think it is still
    somewhat wishful thinking. You might look at work by
    C.R.Ramakrishnan on incremental updates. He and his
    students were looking at how to maintain tables in XSB as
    the underlying database changes; a kind of view maintenance.
    But with arbitrary recursive views (i.e. Prolog
    definitions), this is a very difficult problem.

    I've been thinking about a slightly less ambitious system.
    Here what happens is that when a database relation changes,
    we want to invalidate (well, delete) the tables that depend
    on it, i.e. those whose values might now have changed. So
    rather than computing what the new tables should be, we just
    delete the tables that are now wrong, and if anyone wants to
    look at that view again, the table (or view) will be
    recomputed.

    The other thing that is added is a "notification" facility.
    That is, a user of a view (or table) tells the XSB system
    that it is using this view and it wants to be notified if
    the view changes. So then when the underlying database
    changes to cause a table to become invalid, all users who
    asked to be notified, are indeed notified. Then if they
    want, they can ask again for the veiw, in which case it will
    be recomputed.

    This fits in well in a GUI framework, based on the
    Model-View-Controller paradigm. Then the underlying
    database relations and the tables make up the Model component.

    -David (warren at cs.sunysb.edu)

     
  • Jim Bowery
    Jim Bowery
    2004-08-16

    Logged In: YES
    user_id=279988

    dwarren writes:
    > rather than computing what the new tables should be, we just
    > delete the tables that are now wrong, and if anyone wants to
    > look at that view again, the table (or view) will be
    > recomputed. ..
    > a user of a view (or table) tells the XSB system
    > that it is using this view and it wants to be notified if
    > the view changes.

    Yes. Just these would be a huge step forward.

    Combining the updates with transaction logic may be
    necessary to prevent spurious notifications.

    There is an additional and very valuable feature that should
    be relatively easy to implement with the above system:

    If a view dependency graph is under observation, recompute
    each node's table before deleting the prior table for that
    node. That way it is possible to see if there was an actual
    change made to the table's state before propagating what
    might, in fact, be a null change. This could result in huge
    savings -- particularly if a MD5 hash were kept to identify
    the table states.

    > This fits in well in a GUI framework, based on the
    > Model-View-Controller paradigm. Then the underlying
    > database relations and the tables make up the Model component.

    Precisely. The MVC paradigm, as implemented in an XForms
    system I'm working on is in fact what was driving me to look
    for someone who saw the light here. My question now is how
    long before XSB hence Flora can benefit from this less
    ambitious system?