To demonstrate incremental table maintenance, we consider first the following simple program that does not use incremental tabling:
:- table p/2. p(X,Y) :- q(X,Y),Y =< 5. :- dynamic q/2. q(a,1). q(b,3). q(c,5). q(d,7).and the following queries and results:
| ?- p(X,Y),writeln([X,Y]),fail. [c,5] [b,3] [a,1] no | ?- assert(q(d,4)). yes | ?- p(X,Y),writeln([X,Y]),fail. [c,5] [b,3] [a,1] no | ?-Here we see that the table for p/2 depends on the contents of the dynamic predicate q/2. We first evaluate a query, p(X,Y), which creates a table. Then we use assert to add a fact to the q/2 predicate and re-evaluate the query. We see that the answers haven't changed, and this is because the table is already created and the second query just retrieves answers directly from that existing table. But in this case we have answers that are inconsistent with the current definition of p/2. I.e., if the table didn't exist (e.g. if p/2 weren't tabled), we would get a different answer to our p(X,Y) query, this time including the [d,4] answer. The usual solution to this problem is for the XSB programmer to explicitly abolish a table whenever changing (with assert or retract) a predicate on which the table depends.
By declaring that the tables for p/2 should be incrementally maintained, and using specific dynamic predicate update operations, the system will automatically keep the tables for p/2 correct. Consider the program:
:- table p/2. :- use_incremental_tabling p/2. p(X,Y) :- q(X,Y),Y =< 5. :- dynamic q/2. :- use_incremental_dynamic q/2. q(a,1). q(b,3). q(c,5). q(d,7).in which p/2 is declared to be incrementally tabled (with :- use_incremental_tabling) and q/2 is declared to be :- use_incremental_dynamic, meaning that an incremental table depends on it. Consider the following goals and execution:
| ?- import incr_assert/1 from increval. yes | ?- p(X,Y),writeln([X,Y]),fail. [c,5] [b,3] [a,1] no | ?- incr_assert(q(d,4)). yes | ?- p(X,Y),writeln([X,Y]),fail. [d,4] [c,5] [b,3] [a,1] no | ?-Here again we call p(X,Y) and generate a table for it and its answers. (We have imported the incr_assert predicate we need to interact with the incremental table maintenance subsystem.) Then we update q/2 by using the incremental version of assert, incr_assert/1. Now when we call p(X,Y) again, the table has been updated and we get the correct answer.
In this case after every incr_assert and/or incr_retractall, the tables are incrementally updated to reflect the change. The system keeps track of what tabled goals depend on what other tabled goals and (incremental) dynamic goals, and tries to minimize the amount of recomputation necessary. Incrementally tabled predicates may depend on other tabled predicates. In this case, those tabled predicates must also be declared as incremental (or opaque). The algorithm used is described in [].
We note that there is a more efficient way to program incremental updates when there are several changes made to the base predicates at one time. In this case the incr_assert_inval and incr_retractall_inval operations should be used for each individual update. These operations leave the dependent tables unchanged (and thus inconsistent.) Then to update the tables for all the changes made, the user should call incr_table_update.