Learn · The Concrete Discrete Math of Real Systems

growing

Stop When the Next Step Changes Nothing

Recursive rules become a terminating computation when facts only accumulate; the fixed point is both the answer and the proof that no new answer remains.

Published 2 weeks ago · Updated 2 weeks ago

discrete-math, fixed-points, datalog, recursion, databases, learn

The least fixpoint approach provides a natural semantics for recursive database rules.

— François Bancilhon and Raghu Ramakrishnan, “An Amateur's Introduction to Recursive Query Processing Strategies,” 1986

The previous chapter decomposed machines by how they transform state. Here the state is a set of known facts and every step is monotone growth. You will express transitive closure as rules, prove termination over a finite domain, identify the least fixed point as the intended answer, and derive semi-naive evaluation by asking only what the newest facts can contribute.

Routes from direct flights

Suppose the database contains:

flight(SFO, SEA)
flight(SEA, YVR)
flight(YVR, YYZ)

Define routes with two rules:

route(x, y) :- flight(x, y).
route(x, z) :- route(x, y), flight(y, z).

The first round adds the direct routes. The second discovers SFO→YVR and SEA→YYZ. The third discovers SFO→YYZ. The fourth adds nothing.

Let $F(X)$ be the old facts plus every consequence one rule can derive from $X$ . Starting from the empty set, compute

$\emptyset, F(\emptyset), F^2(\emptyset), \ldots.$

When $F(X)=X$ , $X$ is a fixed point.

Fixed point — a value unchanged by a function: $F(X)=X$ . For a monotone consequence operator, iteration from the least state obtains the least fixed point under suitable finiteness or continuity conditions.

Prediction — read silence as completion.

Why the first fixed point is the answer

The operator is monotone: $X\subseteq Y$ implies $F(X)\subseteq F(Y)$ . Knowing more facts cannot invalidate a positive rule consequence. Starting from nothing therefore produces an ascending chain.

On a finite domain there are only finitely many possible ground facts. Each changing round adds at least one, so the process terminates. Every fixed point satisfying the rules contains the facts produced from the empty set; therefore the limit is the least fixed point. It contains everything forced by the rules and nothing supported only by an arbitrary guess.

Monotone growth plus a finite ceiling turns “repeat until unchanged” into a terminating proof procedure.

This is induction wearing a database uniform. The base facts establish round zero; each rule preserves truth from one round to the next; the fixed point covers paths of every finite length.

Recursion is a query

The language above is Datalog, a relational rule language. Recursive definitions express reachability, ancestry, dependency closure, permission inheritance, and dataflow analysis without prescribing a stack or queue.

The engine may evaluate bottom-up as above, top-down from a particular question, or transform the rules. The declarative meaning remains the least model satisfying them. Separating meaning from traversal lets an optimizer choose indexes and join orders without changing the answer.

Datalog — a rule-based relational language, usually without function symbols, whose positive finite programs have a finite least-fixed-point semantics. It adds recursion to the relational query model while retaining strong analyzability.

Negation requires care. A rule such as “safe if not dangerous” can reverse when new facts arrive, breaking monotonicity. Stratified negation evaluates lower layers completely before higher negative queries; unrestricted negation needs a more elaborate semantics.

Compute only the difference

Naive iteration re-joins every old route with every flight on every round, repeatedly deriving facts already known. Let $\Delta_i$ be only the facts first discovered in round $i$ . Any new consequence in the next round must use at least one fact from $\Delta_i$ ; combinations of wholly old facts were already considered.

Semi-naive evaluation joins the delta, subtracts known results, and continues with the new delta. This is Chapter 10's edit shadow and Chapter 11's incremental merge applied to a fixed point.

Note

The people behind the standard semi-naive account. François Bancilhon and Raghu Ramakrishnan systematized recursive query strategies in their 1986 tutorial, including semi-naive evaluation. The optimization predates that paper and has multiple roots; the citation is to a canonical exposition, not a claim of sole invention.

Transfer — identify the only useful frontier.

Where fixed-point iteration runs out

Termination used a finite fact universe. Function symbols can create terms forever.
Positive rules are monotone; deletion and unrestricted negation can make conclusions retract.
A least fixed point may be finite but expensive. Join planning, indexing, deltas, and bounds remain engineering work.
“No new facts” proves closure under the stated rules, not truth of missing real-world premises.

Lessons

Recursive rules define a monotone consequence operator on fact sets.
Iteration from empty computes the least fixed point over a finite domain.
Datalog makes recursion declarative, allowing execution strategy to change without changing meaning.
Semi-naive evaluation propagates only the new frontier.

Practice

Write Datalog rules for ancestor from parent.
Count the rounds needed for a chain of $n$ parent edges under the two-rule evaluation above.
Give a rule with negation that can retract when one fact is added.
One week later, explain why unchanged-after-a-complete-round is a proof rather than a timeout.

The next question is how much space the answer needs

A fixed-point engine may derive an enormous static relation. Compressing it saves memory but usually requires unpacking before queries. The next chapter asks for something stricter: represent near the information minimum while still navigating and querying the representation directly.

References

Bancilhon and Ramakrishnan. “An Amateur's Introduction to Recursive Query Processing Strategies.” SIGMOD, 1986. — fixed-point semantics and evaluation strategies
Ullman. “Principles of Database and Knowledge-Base Systems, Volume I.” Computer Science Press, 1988. — relational and deductive database foundations
Arntzenius and Krishnaswami. “Seminaïve Evaluation for a Higher-Order Functional Language.” POPL, 2020. — modern derivation of delta-based fixed-point evaluation

Start with direct flights. Add every journey formed by appending one direct flight to a journey already known. Repeat. The table grows until a round adds no new city pair. At that moment “nothing changed” is not an optimization signal; it is the proof that every route derivable by the rules has been found. Recursion has become a query evaluated to its least fixed point.