Incremental tabling (section 7.7) maintains the consistency of tables that depend directly or indirectly on (incremental) dynamic predicates. This is done by invalidating dependent tables on an assert or retract and lazily re-evaluate invalid tables when their content is needed. Incremental tabling preserves all normal tabling properties, including well founded semantics. The downside is that re-evaluation recomputes the table from scratch. This section deals with monotonic tabling, a mechanism that propagates the consequences of assert/1 and friends without recomputing the dependent tables from scratch. Unlike incremental tabling though, monotonic tabling can only deal with monotonic programs, in particular it does not deal with negation.
The example below defines the transitive closure of a bi-directional graph using monotonic tabling. This program builds tables for the connected/2 and maintains these tables when new facts are added for link/2 .
:- table connected/2 as monotonic.
:- dynamic link/2 as monotonic.
connected(X, Y) :-
connected(Y, X).
connected(X, Z) :-
connected(X, Y),
connected(Y, Z).
connected(X, Y) :-
link(X, Y).
The list below describes properties of monotonic tabling and relation to other tabling primitives:
monotonic
and
incremental and it allowed to have both incremental and
monotonic tabled predicates that depend on such dynamic predicates.
There are two types of monotonic tabling. The default is eager,
which implies that an asserted clause is immediately propagated through
the dependency network. Possibly resulting new answers can be tracked as
described in section
7.8.2. The alternative is
lazy. A predicate is marked for lazy using the lazy
option as shown below, or by setting the table_monotonic flag to lazy.
:- table p/1 as (monotonic,lazy).
If a predicate is tabled as monotonic and lazy and an answer is added to one of the monotonic dynamic predicates, all dependent monotonic or incremental tables are invalidated and the answer is queued together with the dependency. A subsequent call to one of the invalidated tabled predicates re-evaluates the tables. For a monotonic table this implies pushing the queued answers through the dependencies. Removing a clause from one of a monotonic dynamic predicates invalidates all dependent tables and marks all these tables for forced re-evaluation, which implies they are re-evaluated using the same algorithm as used for incremental tabling.
Lazy monotonic tables may depend on eager monotonic tables. There is no point in making an eager monotonic table depend on a lazy monotonic table as one would have to re-evaluate the lazy table to make the eager table consistent. Therefore, a dependency of an eager table on a lazy table is silently converted into a lazy dependency.
The prolog_listen/2 interface allows for tracking new facts that are added to monotonic tables. For example, we can print new possible connections from the above program using this code:
:- prolog_listen(connected/2, connection_change).
connection_change(new_answer, _:connected(From, To)) :-
format('~p and ~p are now connected~n', [From, To]).
Currently, failure of the hook are ignored. If the hook throws an exception this is propagated. The hook is executed outside the current tabling context.190The final behavior may be different in both aspects.
After loading the connected/2 program and the above declarations we can observe the interaction below. Note that query 1 establishes the dependencies and fills the tables using normal tabling. In the current implementation, possibly discovered connections do not trigger the hook.191This is likely to change in the future.. Adding a single link/2 fact links both locations to itself and to each other in both directions. Adding a second fact extends the network.
1 ?- connected(_,_).
false.
2 ?- assert(link('Amsterdam', 'Haarlem')).
'Amsterdam' and 'Haarlem' are now connected
'Amsterdam' and 'Amsterdam' are now connected
'Haarlem' and 'Amsterdam' are now connected
'Haarlem' and 'Haarlem' are now connected
true.
3 ?- assert(link('Leiden', 'Haarlem')).
'Leiden' and 'Haarlem' are now connected
'Haarlem' and 'Leiden' are now connected
'Amsterdam' and 'Leiden' are now connected
'Leiden' and 'Amsterdam' are now connected
'Haarlem' and 'Leiden' are now connected
'Leiden' and 'Haarlem' are now connected
'Leiden' and 'Amsterdam' are now connected
'Leiden' and 'Leiden' are now connected
'Amsterdam' and 'Leiden' are now connected
true.
Monotonic tables depend on monotonic dynamic predicates. In some situations there is external dynamic data such as a database. One solution is to maintain a shadow copy of all the external data in a dynamic predicate. This wastes resources and introduces maintenance problems. The system allows to use this information directly from the external source. To do this, create a dynamic and monotonic predicate that accesses the data:
:- dynamic my_data/2 as monotonic.
my_data(X, Y) :-
<access external data>.
Any monotonic table that depends on my_data/2 will be populated
correctly and build a dependency. Next, if a new answer is added to the
external data the user must call incr_propagate_calls/1
from the Prolog library library(increval). Similarly, when
an answer is removed from the extenal data we use incr_invalidate_calls/1.
Both notification calls must be made after the external data
has been updated, i.e., my_data/2 must reflect the new situation before
calling incr_propagate_calls/1
or incr_invalidate_calls/1.
:- use_module(library(increval)).
on_new_my_data(X, Y) :-
incr_propagate_calls(my_data(X, Y)).
on_removed_my_data(X,Y) :-
incr_invalidate_calls(my_data(X, Y)).
Status
Monotonic tabling is experimental and incomplete. Notably support for answer subsumption and call subsumption is probably possible and may greatly improve the application domain and resource usage. Monotonic tabling should work with both shared and private tables. Concurrency issues have not yet been tested though.