Using Prolog Tabling (SLG Resolution) for Memoized Knowledge‑Base Queries

Requirements

When a knowledge base contains recursive rules (transitive closure, graph reachability), naive Prolog evaluation can repeat the same subgoal many times, leading to exponential blow‑up or non‑termination. Tabling, also called SLG resolution, addresses this by storing subgoal results in a global table so each distinct call is evaluated at most once. The design must:

1. Cache results of subgoal calls to prevent redundant computation and guarantee termination for left‑recursive programs.
2. Preserve the declarative semantics of pure Prolog for code that does not use side effects.
3. Keep the memoization table invisible to external callers; they should see only the final answer set.
4. Allow the table to be cleared or refreshed when the underlying facts change.
5. Detect unbounded table growth and provide a way to limit it.

Smallest Suitable Design

The minimal construction is a single module that declares the predicates needing memoization with :- table/1 directives, while keeping the rest of the program pure Prolog.

:- module(kb, [path/2]).\n\n:- table path/2.   % memoize all calls to path/2\n\npath(X, Y) :- edge(X, Y).\npath(X, Y) :- edge(X, Z), path(Z, Y).\n\nedge(a, b).\nedge(b, c).\nedge(c, d).\nedge(a, d).

Save this as kb.pl and load it in a Prolog session, for example SWI‑Prolog:

?- [kb].\ntrue.

A query such as ?- path(a, Y). now computes each distinct path/2 subgoal once, stores results in the table, and reuses them on later calls. Without tabling, a cyclic graph would make this query loop forever; with tabling it terminates. This example assumes SWI‑Prolog 7.x or later, where tabling is built in; other systems (XSB, YAP, B‑Prolog) support tabling but differ in advanced features such as shared or incremental tables.

Trust and Data Boundaries

The table is internal state, not part of the module's contract. From the outside, the module exposes only path/2, and callers receive the same answer set they would get from a pure logical definition. Callers cannot inspect or modify the table directly, which prevents accidental dependence on memoization state. Treat any predicate that reads the table's internals as a debugging tool only, never as application logic.

Operational Checks

Run these in the Prolog top level as a normal user; no special OS permissions are required.

• Confirm tabling is active and measure the effect: wrap the query in time/1 and compare against a baseline with the :- table/1 line commented out. On a dense graph the untabled version should be dramatically slower or non‑terminating.
• Inspect table memory: ?- current_prolog_flag(table_space, Size). reports the space used by tables in SWI‑Prolog. Track this over time to spot unbounded growth.
• Clear stale entries after updates: when facts change (for example, new edge/2 facts are asserted), run ?- abolish_table(path/2). so the next query recomputes from current data. Verify by asserting a new edge, abolishing the table, and checking that the new reachable pair appears in query results.

Failure Modes

The most serious failure mode is unbounded table growth. If a tabled predicate's arguments can generate infinitely many variants, such as a predicate that accumulates an ever‑growing list, the table keeps inserting new entries until memory is exhausted. Mitigate by bounding argument domains (limit list length, use finite integer ranges) or by restructuring the predicate so the tabled argument comes from a finite set.

The second failure mode is stale results from side effects. Tabled results are cached based on the state at first execution. If assert/1, retract/1, or I/O interleaves with tabled calls, later queries return cached answers that no longer reflect the database. The rule is simple: never mix side effects into tabled predicates, and abolish affected tables whenever the underlying facts change.

When the Design Must Change

Reconsider the single‑module tabling approach if:

• The application needs concurrent access to shared tables across threads; you then need a system with shared tabling support, and you must verify that feature in your specific Prolog version.
• Frequent incremental updates make abolishing and rebuilding whole tables too costly; a fine‑grained invalidation scheme, incremental tabling where available, or an external cache may be preferable.
• Side effects are essential to a predicate's logic; keep that predicate untabled and handle memoization explicitly outside the core rules.

Following this design, declaring the minimal set of tabled predicates, treating the table as hidden state, monitoring its size, and abolishing it on updates, gives you a memoized query engine that terminates for many recursive patterns while staying easy to inspect and reset.