nucleation

QUESTION-105: What is the least an evolving inquiry must retain, beyond its current conclusions and a closed belief set, which do not fix its revisions, to support a stated family of future revisions, and does the optimal retained state look like provenance, dependencies and defeated alternatives, or like something else?

3 min read

Properties7
StatusOpen
Version2
Tagsepistemology, information-theory
Linenucleating-argument
RefinesQUESTION-003 — For a family of communicative decisions, what is the minimum information rate at which a translation preserves decision performance within a tolerance?
Refined byQUESTION-188 — Is delete-and-rederive correct for recursive Datalog views with stratified negation and aggregation, and how large is its overestimate of deletions against the deletions actually needed?, QUESTION-225 — Are why-provenance and, for traceable queries, where-provenance preserved by Buneman, Khanna and Tan's rewrite system, and is traceability necessary for where-provenance to be preserved?, QUESTION-289 — Is an inquiry's current set of conclusions, or its logically closed belief set, enough to retain to fix its future revisions, and if not, what must a single AGM change of a closed theory have besides the theory?
BearingTHEORY-387 — For positive recursive Datalog views under set semantics, deleting every derived tuple that has any derivation through a deleted base fact, then restoring each deleted tuple that still has a derivation from what remains, then adding what insertions derive, leaves exactly the tuples derivable from the new base (E − Δ⁻) ∪ Δ⁺, with no derivation counts stored; the extension to stratified negation and aggregation is asserted, not shown, and the size of the overestimate is not measured, THEORY-373 — For positive relational algebra on relations whose tuples are annotated from a commutative semiring, every query's annotated answer equals its answer over provenance polynomials N[X] in the input tuple ids, evaluated at the input annotations, so set, bag, c-table and event-table semantics all factor through the polynomials; revaluing inputs can remove output tuples but never add them, and nothing is shown for negation, difference or aggregation, THEORY-362 — For nonrecursive Datalog or SQL views with safe stratified negation and stratified aggregation, under set or duplicate semantics, storing with each derived tuple only the number of its derivations suffices to maintain the view under insertions and deletions of base tuples: signed counts propagated through delta rules stratum by stratum give each tuple's change as its new count minus its old, a tuple leaves when its count reaches zero, and a MIN or MAX group whose extreme is deleted is recomputed from the stored lower stratum

Graph View

Why it is a question

A4 and A5 posed it as a decision-relative compression problem. With H an inquiry’s history, M what is kept, and Q a family of future revision decisions, find the least I(H; M) such that sup over q in Q of R_q(M) − R_q(H) stays within ε. A5: “The question is whether this optimization yields recognizable structures corresponding to evidence provenance, premise dependencies, alternative hypotheses, and revision histories.”

It is QUESTION-003’s problem with a different decision family. The exchange’s own results bound it from both sides: CLAIM-294 shows current conclusions can fall short, and CLAIM-300 shows a sufficient state makes the rest redundant for a fixed family. Neither says what the optimum looks like for a family of revisions.

An answer characterizes the optimal retained state for a non-trivial family of synthetic inquiries and compares it with explicit record formats. A5: “The interesting result might be that justification graphs are sometimes approximately sufficient—or that they are systematically missing crucial information. Either outcome would advance the theory.” The belief-revision literature has a one-step answer for full belief, and it narrows the question rather than starting it. A closed belief set does not fix its own revision: AGM adds a selection function or ordering (LIT-1050, read in NOTE-874), and Hansson’s survey shows two bases with the same closure revising to opposite conclusions (LIT-1072, read in NOTE-866). Two retained states do the job there, a base marking which beliefs are held in their own right, or an ordering on the closed set. Neither is provenance, dependencies or defeated alternatives, which are what this question asks about, and both results concern single revisions. For iterated revision Hansson reports that “opinions differ widely”. The structures the question names are nearer to Doyle’s truth maintenance systems, which the survey mentions only historically.

Database readings, 2026-10-15. Three readings answer the question for revisions given as changes to base facts under a fixed program. For acyclic support, one count of derivations per conclusion suffices (Gupta, Mumick and Subrahmanian 1993, LIT-1114, NOTE-915, THEORY-362); for cyclic support, nothing beyond base, rules and stored results is kept, and support is rechecked at revision time (THEORY-387). Provenance polynomials (Green, Karvounarakis and Tannen 2007, LIT-1110, NOTE-913) suffice for every revision that re-scores existing inputs in a commutative semiring, for positive queries (THEORY-373, THEORY-380); why-provenance as a witness basis (Buneman, Khanna and Tan 2001, LIT-1104, NOTE-920, THEORY-367) keeps one witness per derivation. None covers added facts, defeat or contraction, and none proves minimality, so the question’s optimum is still open. The retained structures are provenance and dependencies, not defeated alternatives.

Note of 2026-10-27: the lower edge split off

The status review of this date split this question under ADR-049. Whether current conclusions or a closed belief set are enough to retain is QUESTION-289, Answered No by CLAIM-294 and THEORY-347; what a single AGM change of a closed theory needs besides it, a selection function on its remainders, is THEORY-353’s part of that answer. This question keeps what is still open: the least retained state for a family of revisions, including added facts, defeat and iterated change, and whether it looks like provenance, dependencies and defeated alternatives. THEORY-362, THEORY-373 and THEORY-387 keep their links here: they give retained states that suffice for changes to base facts, not least ones.

Backlinks