#+TITLE: Incremental maintenance
* Purpose
An [[file:../lib/kernel/EphemeralRelation.ml][ephemeral relation]] is computed when it is read. That is right for a
relation read rarely, and wrong for one read on every commit or over a
large input, where each read repeats the whole computation. A
materialized ephemeral relation would store its tuples, so that reading
it costs what reading a substantial relation costs. Every commit that
changes its inputs then has to change it as well.
Recomputing it from scratch on each commit costs as much as the
relation itself. Incremental maintenance computes only the change, from
the change to the inputs. The literature calls this [[https://en.wikipedia.org/wiki/Materialized_view][incremental view
maintenance]], and Gupta and Mumick survey it in "Maintenance of
Materialized Views: Problems, Techniques, and Applications" (1995).
RNT has none of it yet. This document is the design it should follow.
* Deltas
A commit changes each relation it touches by a set of inserted tuples,
Δ⁺, and a set of deleted tuples, Δ⁻. For a relation =D= derived from
inputs =R₁ … Rₙ=, maintenance computes =ΔD⁺= and =ΔD⁻= from the =ΔRᵢ= and
the states before and after the commit, operator by operator.
- =Base r= changes exactly as =r= does.
- =Project (p, A)= gains the projection of each tuple in =Δp⁺= that it
did not hold before. It loses the projection of a tuple in =Δp⁻= only
if no other tuple of =p= projects to the same tuple, which is the
problem [[*Counting][counting]] solves.
- =Where (p, b)= changes as =p= does, keeping only the changed tuples
that agree with =b=.
- A join, once [[file:../lib/evaluators/FOL.ml][FOL]] has one, gains =ΔR⁺ ⋈ S= and =R ⋈ ΔS⁺=, against the
right states. Computing =ΔR⁺ ⋈ S= means asking =S= for the tuples that
agree with each inserted tuple of =R= on the join attributes.
That last question binds some attributes of =S= and leaves the rest
free. FOL states it as =Where (S, b)=, for the binding =b= each inserted
tuple puts on the join attributes, and answers it from the index of a
stored =S=, as [[file:partial-bindings.org][partial bindings]] describes. Without the index, the only
way to compute a delta through a join would be to read =S= whole, which
is recomputation by another name.
* Counting
Deletion through a projection needs to know how many tuples of the input
produce each tuple of the output. A materialized relation can store that
count beside each tuple. An inserted input tuple raises the count of
its projection, a deleted one lowers it, and the projected tuple leaves
the relation when its count reaches zero. This is the counting algorithm
of Gupta, Mumick and Subrahmanian ("Maintaining Views Incrementally",
1993). The same paper gives DRed for recursive relations, where counts
do not terminate, by deleting an overestimate and rederiving what
survives.
* Denials are the simplest case
A [[file:denial.org][denial]] is an ephemeral relation that must stay empty, and checking it
incrementally is maintenance with most of the work removed.
- Only insertions matter. The state before the commit was admitted, so
every denial was empty, and an empty relation has nothing to lose.
=ΔD⁻= is always empty.
- Only emptiness matters. One tuple of =ΔD⁺= is enough to refuse the
commit, so the check stops at the first.
- Nothing is stored. A denial is never materialized, and its delta is
thrown away once judged.
- Nothing is counted, because nothing is ever deleted from a denial.
Incremental denial checking therefore reuses the insertion half of the
delta rules, stopped at the first tuple. Full maintenance adds
deletions, counts and storage on top of it.
* What it needs
Two pieces both depend on are in place: FOL's =Where=, which restricts a
plan to a binding and pushes it down to the stored relations, and
indexes, which answer such a restriction by lookup rather than by a
filtered scan. Other pieces are shared with incremental denial checking.
1. Read sets, so that RNT knows which relations a derived relation
reads and how their attributes line up with its own, and can tell
which relations a commit touches.
2. Tuple deltas. [[file:../lib/kernel/Path.mli][Path.diff]] names the relations that changed between
two states, and skips subtrees with equal addresses. The tuples that
changed inside a relation can be found the same way, by diffing its
two tuple sets, since a prolly tree shares every unchanged subtree.
RNT does not expose that diff yet.
3. Joins in FOL, since the deltas worth computing run through them.
Others belong to maintenance alone.
4. Materialization, so that a derived relation can be stored with its
tuples, counts and indexes, and read like a substantial relation.
5. Deletion rules and counts, as above.
* When maintenance runs
A commit would apply its changes to the base relations, maintain every
materialized relation that reads them, then judge the denials against
the resulting state, and only then move the head. Maintenance has to
come before judgement, because a denial may read a materialized
relation. The maintained relations land in the same state as the change
that caused them, so no state ever holds a stale one.
* Checking it
A tuple set is content addressed. If the shape of its tree depended only
on the tuples it holds, and not on the order they were inserted in, a
maintained relation and the same relation recomputed from scratch would
have equal addresses exactly when maintenance was correct, and
comparing the two addresses would test the delta rules completely. The
chunking in [[file:../lib/kernel/Merkle.ml][Merkle]] is still naive and does not promise that, so until
it does, the test has to compare the tuples themselves.
