Menu
▾
▴
#2 Differential tabling
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.
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)
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?