Orchestrata Ultimate › Plans › prolog-tabling-strategy

SPEC-106 FR-006: Prolog Tabling Strategy for kg_relevance.pl

Source: plans/prolog-tabling-strategy.md at 8a2cb42ad · last changed 2026-07-27 · first committed 2026-07-10 · 235 lines.

Prose pending.

Plan text

SPEC-106 FR-006: Prolog Tabling Strategy for kg_relevance.pl

Author: codewhale (Brother Whale) Date: 2026-07-10 For: claude — P1 investigation task

1. Problem

kg_relevance.pl defines two transitive/relational predicates:

• contains/2 — transitive closure over kg_defines/2 (DEFINES containment tree)
• shares_requirement/2 — relational join: "A and B both TRACES_TO the same RequirementItem"

The retriever (KgRelevanceRetriever.refine()) asserts N ground facts (candidates, roots, traces, defines edges) then queries kg_relevance_tier/2 once. That single query triggers multiple evaluations of contains/2 (via defines_from_root/1 → build/refactor/document core rules) and shares_requirement/2 (via shares_requirement_with_root/1 → all task-type core rules).

Without tabling:

• contains/2: for a DEFINES DAG of D depth, naive transitive closure re-derives every path on each call — worst-case O(N·D) per call, repeated by each task-type rule that calls defines_from_root/1.
• shares_requirement/2: the join kg_traces(A,R), kg_traces(B,R) on N nodes with R requirements costs O(N²) per evaluation. Called by shares_requirement_with_root/1 which is called from every task-type clause.

At repo scale (762K nodes in the KG, subgraph selections of 100–1000 nodes), repeated un-tabled evaluation adds latency that violates the p50 < 500ms selection+packing NFR.

2. Tabling Strategy

SWI-Prolog (via janus-swi, which PrologBridge uses) supports tabling via :- table directives. When a tabled predicate is called, results are memoized by variant (SWI default) — subsequent calls with the same arguments return cached answers instantly.

2.1 Table contains/2

:- table contains/2.

contains(Parent, Child) :-
    kg_defines(Parent, Child).
contains(Parent, Child) :-
    kg_defines(Parent, Mid),
    Mid \== Child,
    contains(Mid, Child).

Why variant tabling (default) works here:

• contains/2 is called with ground arguments (both Parent and Child are atom node-ids from ground kg_root/1 and kg_defines/2 facts).
• Variant tabling memoizes by exact argument terms — ground calls hit the table directly.
• After the first contains(root, X) call fills the table, subsequent defines_from_root/1 invocations from different task-type rules (build, refactor, document all call it) are instant table lookups.

Cost:

• Untabled: O(N·D) per defines_from_root call (3 task types → 3×)
• Tabled: O(N·D) once, then O(1) per subsequent call. Net: ~3× speedup for typical subgraphs.

2.2 Table shares_requirement/2

:- table shares_requirement/2.

shares_requirement(A, B) :-
    kg_traces(A, R),
    kg_traces(B, R),
    A \== B.

Why variant tabling works:

• shares_requirement/2 is called with one ground arg via shares_requirement_with_root/1: shares_requirement(N, Root) where Root is ground (from kg_root/1).
• The table fills with all pairs (A, B) that share a requirement.
• Subsequent calls from different task-type rules re-use the table.

Cost:

• Untabled: O(N²) per call (join on kg_traces), called from 5 task types → 5×
• Tabled: O(N²) once, then O(1) per subsequent call. Net: ~5× speedup.

2.3 Table shares_requirement_with_root/1

:- table shares_requirement_with_root/1.

shares_requirement_with_root(N) :-
    kg_root(Root),
    shares_requirement(N, Root).

This is called by every task-type rule for core/related tier assignment. Tabling it means the expensive shares_requirement/2 join only fires once per refinement.

2.4 Table defines_from_root/1

:- table defines_from_root/1.

defines_from_root(Child) :-
    kg_root(Parent),
    contains(Parent, Child).

Called by build/refactor/document core rules. With both contains/2 and defines_from_root/1 tabled, these rules become pure table lookups.

2.5 Complete tabled version

:- table contains/2.
:- table shares_requirement/2.
:- table shares_requirement_with_root/1.
:- table defines_from_root/1.
:- table near_root/1.
:- table core_for/2.
:- table kg_relevance_tier/2.

Rationale for tabling core_for/2 and kg_relevance_tier/2: These are the leaves that the Python retriever actually queries (kg_relevance_tier(N, T)). Tabling them means the Python query collects results from a fully materialized table — single-pass, no backtracking re-derivation.

2.6 Fact-lifecycle compatibility

The retriever asserts all ground facts, queries once, then retracts. No facts change between assertion and query. This matches tabling's sweet spot:

• The table is built once during the first kg_relevance_tier/2 query
• No invalidation needed — facts are retracted after the query
• The table is discarded when the Prolog engine moves to the next refinement (janus-swi re-consults the ruleset on load_rules, which clears tables)

3. CLIPS/RETE vs SWI-Prolog Tabling

3.1 RETE algorithm (CLIPS, Drools)

RETE is a forward-chaining pattern-matching network. When a fact is asserted:

1. The network propagates the fact through alpha (single-condition) and beta (join) nodes
2. Partial matches are stored in node memories
3. When a complete match is formed, the rule fires (right-hand side executes)

RETE's advantage: incremental maintenance. When one fact changes, only affected conclusions are recomputed. Ideal for long-running expert systems with streaming updates.

RETE's disadvantage for this use case:

• The fact set is batch-asserted per refinement, then fully retracted
• RETE would build the entire pattern-matching network, fill all alpha/beta memories, fire all rules — then discard everything on retraction
• The network construction overhead (rule compilation → node graph) is paid per refinement
• Each rule firing triggers additional assertions (from right-hand sides), cascading through the network again

3.2 Comparison matrix

3.3 Verdict

SWI-Prolog tabling wins for this use case. The fact lifecycle is batch-assert-then-query — RETE's incremental advantage is never exercised. Tabling adds 6 directives to the existing .pl file; RETE would require a separate CLIPS runtime, a Python bridge, and fact-translation layer. The complexity budget is better spent on the tabling directives and measurement hooks (REQ-106-065).

The one scenario where RETE would pull ahead: If kg_relevance.pl were to become a long-lived, incrementally-updated reasoning engine (e.g., watching the KG change stream and maintaining live relevance tiers). That is explicitly out of scope for FR-006 (request-scoped, retract-after-use).

4. Implementation Plan

Phase A: Add tabling directives (5 minutes)

Add to prolog/kg_relevance.pl, after the :- dynamic declarations:

:- table contains/2.
:- table shares_requirement/2.
:- table shares_requirement_with_root/1.
:- table defines_from_root/1.
:- table near_root/1.
:- table core_for/2.
:- table kg_relevance_tier/2.

Phase B: Verify determinism (REQ-106-062)

Tabling must not change results — same facts → same tiers. Add a test that:

1. Runs KgRelevanceRetriever.refine() on a fixed subgraph
2. Re-runs with identical facts
3. Asserts byte-identical tier maps

Phase C: Measure (REQ-106-065)

Add timing instrumentation to KgRelevanceRetriever.refine() — record:

• Fact projection time (Python → Prolog asserts)
• Query time (Prolog deduction)
• Per-tier node counts

Phase D: Benchmark

Run against subgraphs at 100, 500, 1000 nodes with and without tabling. Verify p50 < 500ms NFR is maintained at scale.

5. Risk: janus-swi Tabling Support

janus-swi wraps SWI-Prolog's C FFI. Tabling is a compile-time SWI feature (enabled by default in SWI 8.x+). Verify with:

?- current_prolog_flag(table_space, _).

If the flag is absent, SWI was compiled without tabling. Fallback: manual memoization using assertz/retract for contains/2 — less elegant but functional for request-scoped use.

6. Recommendation

Add the 7 table directives, verify determinism, ship. CLIPS/RETE is not the right tool for a batch-assert-then-query lifecycle. If incremental reasoning becomes a requirement later (FR-007 or beyond), re-evaluate at that point.

Related

• Plans
• Orchestrata Ultimate — project index
• Workflow
• Tasks