Hom commutation, token and annotation layer #
The value-level content of “compile once, evaluate many” for the general
evaluator: every ingredient of a row's annotation is an
⊕/⊗/⊖/δ-polynomial in the occurrence annotations, so it commutes
with every SemiringWithMonusHom:
GenAnn.finalize_mapHom– the finalized factored annotation commutes (this is wheremap_deltaenters, for the pending group factors);AggValue.predProv_mapAnn– the predicate provenance of a comparison against a token commutes: the world annotations are⊗/⊖-polynomials and the characteristic valuesχare{𝟘,𝟙}-valued, with the aggregate values themselves untouched by the pushforward;AggTok.predProvOf_mapAnn– the same for a column that is not nested; a nested column is related across a homomorphism by the correspondence of its worlds instead (NestedValue.WCorr, fromwcorr_of_rel), since two of its families whose keys the homomorphism merges are decided together after it;GenPredIn.predsem_mapAnn– the predicate provenance of a whole generalized predicate commutes (∧ ↦ ⊗,∨ ↦ ⊕throughmap_mulandmap_add,¬by polarity), on a row holding no nested token.
These do not by themselves give the
evaluator-level commutation AggQueryIn.evaluateAnnotated_hom at the
bottom of this file: the evaluator's supersede and cashing decisions
compare annotation lists for equality, which a non-injective hom can
conflate (licensing supersedes on the target side that the source side
does not take), and the ≼-order's annotation tie-break in
havingGroup need not be preserved. Both divergences are
value-neutral, so the theorem holds with no hypothesis on the hom, the
query or the m-semiring:
- an extra supersede only drops a group guard standing next to an
annotation that already contains an occurrence of that group, which
delta_absorbmakes redundant; - a changed tie-break only permutes occurrences carrying the same tuple
part, hence the same aggregated-term value, and the tie-block
congruence of
Provenance.AggValueCongrshows such a permutation leaves the predicate provenance alone.GenRow.Simbelow carries that slack row by row through the evaluator, andGenRow.Sim.toAnnotated_eqcashes it into an equality of finalized annotated tuples.
The annotation pushforward #
Pushforward of a factored annotation along h.
Equations
- GenAnn.mapHom h a = { base := h.toRingHom a.base, pending := Multiset.map (List.map ⇑h.toRingHom) a.pending }
Instances For
Dependency graph
The finalized factored annotation commutes with any hom (the pending
group factors through map_delta).
Dependency graph
The token pushforward #
Token-level hom commutation. The predicate provenance of a
comparison against a token commutes with every SemiringWithMonusHom:
it is an ⊕/⊗/⊖-polynomial in the occurrence annotations, and the
aggregate values compared are untouched by the pushforward.
Dependency graph
Nested values read through corresponding worlds #
Two nested values whose worlds correspond (NestedValue.WCorr) – both
enumerations the images of one bag of indices, the weights pushed through
the homomorphism and the readings equal – have every reading related: the
predicate provenance is pushed, the values a key reads are equal. That is
what a nested column reads under a homomorphism; the correspondence itself
is wcorr_of_rel's, from how the two values were built.
A comparison is one such test.
Dependency graph
The predicate pushforward #
Predicate-level hom commutation. The structural predicate
provenance of a generalized predicate commutes with every
SemiringWithMonusHom on a row holding no nested column: regular atoms
through χ, aggregate atoms through the token-level commutation,
∧ ↦ ⊗ and ∨ ↦ ⊕ through map_mul and map_add, and ¬ by polarity.
The evaluator reads a selection jointly, and its commutation, nested
columns included, is GenPredIn.predsemJ_hom_famPres.
Dependency graph
The group sequence under the pushforward #
Having.havingGroup sorts the group by the tuple part and breaks ties on
equal tuple parts by the alternative order on the annotations. The
pushforward changes the tie-break order, so the hom-side group sequence
coincides with the mapped base-side group sequence only up to a
permutation inside blocks of equal tuple parts – a TiePerm, which the
congruence layer of Provenance.AggValueCongr renders invisible to every
reading of the resulting tokens.
The hom-side group sequence is a tie-block permutation of the mapped base-side group sequence: both are sorted by the tuple part and carry the same multiset of annotated occurrences.
Dependency graph
Group-token hom commutation. The predicate provenance of a
comparison against the token of a group of the pushed-forward relation is
the image under the hom of the base-side predicate provenance: the two
tokens differ by a tie-block permutation of the payload, which
AggValue.predProv_congr makes invisible.
Dependency graph
The pending group factor – the sum of the occurrence annotations of the group – commutes with the pushforward, the tie-block permutation being invisible to a sum.
Dependency graph
The window's frame under the pushforward #
A frame is read off the values, so the pushforward carries it unchanged;
what it changes is the order the frame's occurrences are read in, and only
inside blocks of equal tuple parts – a TiePerm, as for a group.
The sorted reading of a pushed-forward relation is a tie-block permutation of the pushed-forward sorted reading: the pushforward keeps the tuple part, so only the tie-break between equal tuples can move.
Dependency graph
The occurrence payloads of a window's token – base-side pushed forward, and hom-side – differ by a tie-block permutation on equal values: the frame itself is carried unchanged, only the order inside a block of equal tuples can move.
Dependency graph
The simulation relation #
The evaluator-level commutation cannot be a per-row equality: the hom side
may supersede more pending factors (a non-injective hom conflates the
annotation-list equality tests) and its group sequences are only tie-block
permutations of the mapped base-side ones. The right invariant is a
row-wise simulation: regular values equal, aggregate columns reading as
the pushed-forward ones do, and the finalized annotation equal to the
image of the base-side finalized annotation. Both discrepancies are value-
neutral at that level: extra supersedes by guard absorption
(delta_absorb), tie-breaks by the congruence layer.
Equivalence of lifted values: equal regular values, or aggregate columns that read the same. On an ordinary token that is the same aggregate over tie-block-permuted payloads; on an expression and on a nested value it is the four readings the metatheory takes – the collapse, the convention, the values over the worlds and the predicate provenance of every test – since neither family is compared as a family: an expression's is listed by occurrence index, where a tie-block permutation of it is not an equality, and a nested value's is a bag, where the occurrences carry tokens that nothing orders.
The occurrence annotations are deliberately not compared: on either
kind the two sides' families agree only up to a tie-block permutation,
and the evaluator's own group bookkeeping travels in GenRow.Sim's
second component rather than here.
Equations
- One or more equations did not get rendered due to their size.
- GenValue.Equiv (Sum.inl v') (Sum.inl v) = (v' = v)
- GenValue.Equiv (Sum.inr (AggTok.tok a')) (Sum.inr (AggTok.tok a)) = (a'.agg = a.agg ∧ a'.scalar = a.scalar ∧ TiePerm (fun (p q : T × K) => p.1 = q.1) a'.occs a.occs)
- GenValue.Equiv (Sum.inr (AggTok.nest b')) (Sum.inr (AggTok.nest b)) = (b'.lev = b.lev ∧ b'.collapse = b.collapse ∧ b'.scalar = b.scalar ∧ b'.agg = b.agg)
- x✝¹.Equiv x✝ = False
Instances For
Dependency graph
What the equivalence gives #
Downstream never cases on the kind of token: it reads an aggregate column through its collapse, its convention, its values and its predicate provenance, and each of those is equal on the two sides.
The row-wise simulation relation underlying the evaluator-level hom commutation: regular columns equal, aggregate columns reading as the pushed-forward base-side ones do, and the finalized annotation the image of the base-side finalized annotation.
Equations
Instances For
Dependency graph
Simulated rows finalize to pushed-forward annotated tuples.
Dependency graph
Per-side finalize identities #
The three row transformations of the evaluator that rearrange the factored
annotation are finalize-equivalent on each side separately: cashing a
group factor moves δ between pending and base (projection), the
supersede drop is licensed exactly by the guard-absorption condition of
its filter (selection), and the product splits multiplicatively.
Cashing any sub-multiset of pending factors does not change the finalized annotation.
Dependency graph
Multiset relation plumbing #
The evaluator-level commutation #
The query syntax mentions no annotation values, so the same query
evaluates over any annotation semiring; the database argument determines
it. The main theorem relates the evaluation on the pushed-forward
database to the base-side evaluation, row by row, through GenRow.Sim;
finalizing both sides then yields the hypothesis-free hom commutation of
evaluateAnnotated.
Reading an aggregate column as a key commutes with a homomorphism: the values the column takes are untouched by the pushforward and by tie-block equivalence, so the two occurrences have the same alternatives, and each pair of them is again simulated. A nested column's values and tests are read through the world correspondence of its two sides.
Dependency graph
Families across the rows of an evaluation #
What the joint reading of a selection needs of a row is that its
families be presented on both sides. What a row carries for that is
stated over the pairs of corresponding values it holds (rowPairs), and
established for the whole evaluation at once below (RowG,
AggQueryIn.evaluate_hom_univ).
The pairs of corresponding aggregate values two rows hold.
Instances For
Dependency graph
Two environments related by a homomorphism: the context columns are equivalent at the arity read, and the rounds bound to each name simulate each other row for row.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
The joint simulation #
The value a grouping's aggregate builds over its group: an
ordinary token, or, under a FILTER clause, the one-leaf expression over
the whole group whose clause cuts what it reads.
Equations
- groupTok f t none sc U₀ γ = AggTok.tok (have __src := AggValue.ofGroup f t U₀ γ; { agg := __src.agg, occs := __src.occs, scalar := sc, fam := __src.fam, oids := __src.oids })
- groupTok f t (some φ) sc U₀ γ = AggTok.expr (AggExpr.ofSeqWhen f t φ.keeps U₀ sc γ)
Instances For
Dependency graph
How a grouping's aggregate reads a row of its group.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
One presentation for the whole evaluation #
Every aggregate value an evaluation holds is built by an operator of the
query, at one of the situations the evaluation passes through, or is
provided by the environment, up to terms (AggQueryIn.rowToks); and two
values carrying one identifier are one value, two of one family carry one
class (AggQueryIn.builds_coherent). So a family is presented once, by the
listing of the operator row that built it, for the whole evaluation: what a
row carries is that each of its pairs records one identifier on both sides
and that its class is so presented (ClassPres). Rows then merge with
nothing to check, and a selection reads the families of a row jointly
(famPres_of_good).
A pair of values of the two universes carrying one identifier.
Instances For
Dependency graph
A listing pair with nothing in it: what presents a family with no occurrence.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
The listing pair the universes give an expression family, by key: one presenting every pair of flat values of the universes with that key, where there is one.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
The expression pairs a nested value of the universes reads: the expressions of a pair of flat values of the universes, or one regular value read as an expression on both sides.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
The node pairs a nested value of the universes reads: those of a pair of nested values of the universes.
Equations
- NGU 𝒰₀ 𝒰₀' j N' N = GPair 𝒰₀ 𝒰₀' (AggTok.nest (NestedValue.ofNode N'), AggTok.nest (NestedValue.ofNode N))
Instances For
Dependency graph
Two nested values related as towers through the universes' presentations.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
The class of x is presented across the two universes: one
listing on each side presents every pair of the class, or every pair of
the class is a pair of nested values related as towers.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
What a row carries: each pair of corresponding values records one identifier, and its class is presented.
Equations
Instances For
Dependency graph
The universes of an evaluation: what the two sides build, with no
term recorded; one value per identifier and one class per family; each
operator, of label l, building fewer columns than its width in W.
Instances For
Dependency graph
A coherent evaluation keys its families faithfully: two related families have one key on one side exactly when they have one on the other, the family identifier deciding the key on each side.
Dependency graph
The families of pairs drawn from the universes, each class presented, are presented together.
Dependency graph
An environment of the evaluation: its context's values carry one identifier on both sides with their class presented, its rounds simulate each other with their rows carrying the same, and what it provides is drawn from the universes.
Instances For
Dependency graph
The column values a second-level aggregation reads on the two sides: equivalent, and, where they are aggregate values, a pair of the universes with its class presented.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
The joint row-wise simulation, over the universes of the evaluation.
Dependency graph
The row-wise simulation for a query read with nothing bound.
Dependency graph
Evaluator-level hom commutation: the final annotated relation
computed by the general evaluator commutes with every
SemiringWithMonusHom, over every m-semiring. Nothing is asked of the
hom: the extra supersedes a non-injective one can trigger are
value-neutral by guard absorption (delta_absorb), and the annotation
tie-breaks of the group sort are value-neutral by the tie-block
congruence layer.
What is asked of the query:
- that every window frame contain its current row exactly when it
contains its peers (
AggQueryIn.allFramesContainSelf): a multi-frame window lists its shared family by occurrence index, which a change of annotation semiring re-sorts inside blocks of equal rows, and a window over a frame that excludes the current row gives two rows with the same tuple different values, which one family identifier cannot tell apart. Every window function the library derives satisfies it; - that no two operators building aggregate values share a label
(
AggQueryIn.labelsDistinct), that every operator record the parameters its subtree reads (AggQueryIn.readsRecorded), and that no projection column apply an arbitrary function to an aggregate value (AggQueryIn.sourceCols). A selection reads the values of one family in one world of that family, and the two sides list the family's occurrences each in its own order; what makes the reading commute is that every value of a family is built from one listing on each side, the two tie-block permuted (FamPres,jointWorlds_of_famPres). Under these three conditions a family identifier determines its value across every evaluation the query performs, a recursion's rounds included (AggQueryIn.builds_coherent), so each family is presented once for the whole evaluation (ClassPres).
Nothing is asked of the semiring: a second-level aggregation's worlds are
read off its occurrences' data, the product a world keeps and the sum it
leaves out kept apart (NestedValue.WCorr).
These are hypotheses of this proof and not of the mathematics: every
output annotation is an expression in the input annotations over ⊕,
⊗, ⊖, δ, 𝟘, 𝟙, and a hom commutes with such an expression in
every m-semiring.