Home / Projects / Orchestrata Ultimate / Decisions / ADR index / ADR-0026

ADR-0026: A governance predicate may not return a truncated answer set

← ADR-0025 · ADR-0027 →

The record

• Status: Accepted
• Date: 2026-07-24
• Spec: SPEC-106 (REQ-106-066, amended); SPEC-033 §1, §4
• Amends: REQ-106-066 (original max_answers(20) restraint)

Context

knowledge.pl:ownership_chain/3 was tabled as (incremental, max_answers(20)). The restraint existed for a real reason: a cyclic owns/depends_on graph generates chains of unbounded length, and without a bound the query does not terminate. SWI's max_answers(N) terminates evaluation and marks the overflow undefined, and REQ-106-066 required call sites to treat any undefined answer as deny + escalate.

So the cap was declared, spec-traced, and tested — not a silent truncation. But it bounded the answer set by truncating it, and that is the wrong shape for a predicate a governance gate reads:

• An ownership graph deeper than 20 yields incomplete evidence. The correct chain may be the 21st.
• "Treat undefined as deny" converts an evidence-completeness failure into a denial, which is fail-closed and therefore safe — but it is a liveness failure that scales with graph depth, and the constant 20 has no derivation. It is a magic number standing between a legitimate agent and its work.
• More importantly it sets a precedent: that a governance predicate may answer partially. Every gate in SPEC-033 scores on the facts a predicate returns; a predicate that can silently return "some of the truth" is a false-green generator wherever a caller forgets the undefined check.

The general principle was missing: termination must be achieved by making the answer set finite, never by cutting a finite prefix out of an infinite one.

Decision

No governance predicate may return a truncated answer set. Where recursion over a possibly-cyclic graph is required, terminate by construction — carry the set of already-visited nodes and refuse to revisit one, so every answer is a simple path and a finite graph admits finitely many simple paths.

Applied to ownership_chain/3:

• max_answers(20) is removed; the predicate stays tabled as incremental.
• The public /3 predicate delegates to an untabled /4 walker carrying a visited-node set.
• The /4 walker is deliberately not tabled: its visited-set argument makes every call a distinct subgoal, so tabling it would grow one table entry per path and buy nothing.

Verified against SWI-Prolog 10.1.9: on a two-node cycle the answer set is complete and finite, every answer is ground, no undefined answer is produced, and incremental table invalidation still propagates correctly through the untabled helper (assert/retract of owns/2 invalidates and restores exactly the affected answers).

Alternatives rejected

• Keep max_answers(N) with a larger N — moves the cliff, does not remove it, and leaves the magic constant undermined.
• Keep the cap and rely on the call-site deny — fail-closed, so safe, but a liveness failure keyed to graph depth, and it normalises partial answers in the governance rulebase.
• Table the /4 walker — one table entry per distinct visited set; unbounded table growth for no memoization benefit, since no two paths share a subgoal.
• Cycle-detect and error — turns a legitimate cyclic ownership graph into a hard failure rather than answering the question that was actually asked ("which simple ownership paths exist").

Consequences

• Cost is now bounded by the number of simple paths, which is worst-case exponential in a dense graph rather than a flat 20. In the ownership graph's actual shape (sparse, shallow delegation) this is cheaper than the cap; a pathological dense graph would be slower, and that case wants a measured budget, not a truncation.
• Answer order out of the table changed. Any assertion on tabled answer order was always unsound — SWI does not contract it — and the REQ-106-066 tests were updated to compare sorted answer sets.
• REQ-106-066, its checklist entry, docs/rtm.md, and the three tests were amended; test_ownership_chain_rejects_undefined_tail became test_ownership_chain_produces_no_undefined_answers, since there is no longer an undefined tail to reject.
• The principle now generalises: any future governance predicate needing a restraint must justify why its answer set is finite, rather than reaching for max_answers.

Provenance

Raised during the 2026-07-24 engine review while surveying the existing rulebases for the Prolog-vs-Datalog question (ADR-0027). Ratified by the human. Note the initial characterisation of the cap as a silent truncation was wrong — it was declared and tested; the defect is that it truncates at all.

Related ADRs

• Also mentioned: ADR-0027

Rulings cited

None.

Specs cited

• SPEC-106
• SPEC-033