7.8 Monotonic tabling

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

abolish_monotonic_tables

Abolish all monotonic tables and their dependencies.

The list below describes properties of monotonic tabling and relation to other tabling primitives:

• When using retract/1 on a dynamic monotonic predicate, all dependent tables and dependency links are invalidated and marked for normal incremental update.

• abolish_all_tables/0 destroys all monotonic dependency relations.

• Dynamic predicates can be declared as both monotonic and incremental and it allowed to have both incremental and monotonic tabled predicates that depend on such dynamic predicates.

• A tabled predicate that depends on a monotonic tabled predicate must be tabled monotonic or incremental. If the dependent predicate is incremental a new answer invalidates the incremental table.

7.8.1 Eager and lazy monotonic tabling

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.

7.8.2 Tracking new answers to monotonic tables

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.^{188The 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.^{189This 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.

7.8.3 Monotonic tabling with external data

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

incr_propagate_calls(:Answer)

Activate the monotonic answer propagation similarly to when a new fact is asserted for a monotonic dynamic predicate. The Answer term must match a monotonic dynamic predicate. See section 7.8.3 for an example.

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.