Documentation

Provenance.AggQueryHom

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:

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:

The annotation pushforward #

Pushforward of a factored annotation along h.

Equations
Instances For
    Dependency graph

    The finalized factored annotation commutes with any hom (the pending group factors through map_delta).

    Dependency graph

    The token pushforward #

    theorem AggValue.predProv_mapAnn {T : Type} [ValueType T] {K K' : Type} [CommSemiringWithMonus K] [DecidableEq K] [CommSemiringWithMonus K'] [DecidableEq K'] (h : SemiringWithMonusHom K K') (a : AggValue T K) (op : CompOp) (c : T) :
    (mapAnn (⇑h.toRingHom) a).predProv op c = h.toRingHom (a.predProv op c)

    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.

    theorem AggTok.predProvOf_mapAnn {T : Type} [ValueType T] {K K' : Type} [CommSemiringWithMonus K] [DecidableEq K] [CommSemiringWithMonus K'] [DecidableEq K'] (h : SemiringWithMonusHom K K') (x : AggTok T K) (hx : x.isNested = false) (op : CompOp) (c : T) :
    predProvOf op c (mapAnn (⇑h.toRingHom) x) = h.toRingHom (predProvOf op c x)

    A comparison is one such test.

    Dependency graph

    The predicate pushforward #

    theorem GenPredIn.predsem_mapAnn {T : Type} [ValueType T] {K K' : Type} [CommSemiringWithMonus K] [DecidableEq K] [CommSemiringWithMonus K'] [DecidableEq K'] {c n : ℕ} {κ : Fin n → ColKind} (h : SemiringWithMonusHom K K') (φ : GenPredIn T c κ) {γ : Fin c → T} (neg : Bool) (u : Tuple (GenValue T K) n) (hnn : ∀ (k : Fin n) (x : AggTok T K), u k = Sum.inr x → x.isNested = false) :
    φ.predsem neg (fun (k : Fin n) => AggValue.mapAnnSum (⇑h.toRingHom) (u k)) γ = h.toRingHom (φ.predsem neg u γ)

    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.

    theorem havingGroup_tiePerm {T : Type} [ValueType T] {K K' : Type} [CommSemiringWithMonus K] [CommSemiringWithMonus K'] [DecidableEq K'] {m n₁ : ℕ} [HasAltLinearOrder K] [HasAltLinearOrder K'] (h : SemiringWithMonusHom K K') (is : Tuple (Fin m) n₁) (r : AnnotatedRelation T K m) (g : Tuple T n₁) :
    TiePerm (fun (p q : AnnotatedTuple T K' m) => p.1 = q.1) (List.map (fun (p : AnnotatedTuple T K m) => (p.1, h.toRingHom p.2)) (Having.havingGroup is r g)) (Having.havingGroup is (Multiset.map (fun (p : AnnotatedTuple T K m) => (p.1, h.toRingHom p.2)) r) g)

    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
    theorem ofGroup_predProv_hom {T : Type} [ValueType T] {K K' : Type} [CommSemiringWithMonus K] [DecidableEq K] [CommSemiringWithMonus K'] [DecidableEq K'] {m n₁ : ℕ} [HasAltLinearOrder K] [HasAltLinearOrder K'] (h : SemiringWithMonusHom K K') (f : SeqAggFunc T) {c : ℕ} (t : TermIn T c m) {γ : Fin c → T} (is : Tuple (Fin m) n₁) (r : AnnotatedRelation T K m) (g : Tuple T n₁) (op : CompOp) (c✝ : T) :
    (AggValue.ofGroup f t (Having.havingGroup is (Multiset.map (fun (p : AnnotatedTuple T K m) => (p.1, h.toRingHom p.2)) r) g) γ).predProv op c✝ = h.toRingHom ((AggValue.ofGroup f t (Having.havingGroup is r g) γ).predProv op c✝)

    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.

    theorem sortList_hom_tiePerm {T : Type} [ValueType T] {K K' : Type} [CommSemiringWithMonus K] [CommSemiringWithMonus K'] [DecidableEq K'] [HasAltLinearOrder K] [HasAltLinearOrder K'] (h : SemiringWithMonusHom K K') {n' : ℕ} (M : Multiset (AnnotatedTuple T K n')) :
    TiePerm (fun (a b : AnnotatedTuple T K' n') => a.1 = b.1) (List.map (fun (q : AnnotatedTuple T K n') => (q.1, h.toRingHom q.2)) (sortList M)) (sortList (Multiset.map (fun (q : AnnotatedTuple T K n') => (q.1, h.toRingHom q.2)) M))

    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
    theorem tokenOf_mapAnn_tiePerm {T : Type} [ValueType T] {K K' : Type} [CommSemiringWithMonus K] [CommSemiringWithMonus K'] [DecidableEq K'] [HasAltLinearOrder K] [HasAltLinearOrder K'] (h : SemiringWithMonusHom K K') {n' m' p' : ℕ} (P : Tuple (Fin n') m') (O : Tuple (Fin n') p') (o : OrderSpec p') (w : ValueFrame T p') {c : ℕ} (t : TermIn T c n') {γ : Fin c → T} (f : SeqAggFunc T) (X : Multiset (AnnotatedTuple T K n')) {x : AnnotatedTuple T K n'} (hx : x ∈ X) :
    TiePerm (fun (a b : T × K') => a.1 = b.1) (AggValue.mapAnn (⇑h.toRingHom) (ValueFrame.tokenOf P O o w t f X x γ)).occs (ValueFrame.tokenOf P O o w t f (Multiset.map (fun (q : AnnotatedTuple T K n') => (q.1, h.toRingHom q.2)) X) (x.1, h.toRingHom x.2) γ).occs

    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
    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.

      def GenRow.Sim {T : Type} [ValueType T] {K K' : Type} [CommSemiringWithMonus K] [CommSemiringWithMonus K'] [DecidableEq K'] (h : SemiringWithMonusHom K K') {n : ℕ} (r' : GenRow T K' n) (r : GenRow T K n) :

      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
        theorem GenRow.Sim.toAnnotated_eq {T : Type} [ValueType T] {K K' : Type} [CommSemiringWithMonus K] [CommSemiringWithMonus K'] [DecidableEq K'] (h : SemiringWithMonusHom K K') {n : ℕ} {r' : GenRow T K' n} {r : GenRow T K n} (hs : Sim h r' r) :

        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.

        theorem GenAnn.finalize_cash {K : Type} [CommSemiringWithMonus K] [DecidableEq K] (b : K) (P kept : Multiset (List K)) (hle : kept ≤ P) :
        { base := b * (Multiset.map (fun (l : List K) => SemiringWithMonus.delta l.sum) (P - kept)).prod, pending := kept }.finalize = { base := b, pending := P }.finalize

        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.

        theorem sim_alternativesAt {T : Type} [ValueType T] {K K' : Type} [CommSemiringWithMonus K] [DecidableEq K] [CommSemiringWithMonus K'] [DecidableEq K'] (h : SemiringWithMonusHom K K') {n : ℕ} {r' : GenRow T K' n} {r : GenRow T K n} (hs : GenRow.Sim h r' r) (k : Fin n) (hnest : ∀ (b : NestedValue T K) (b' : NestedValue T K'), r.1 k = Sum.inr (AggTok.nest b) → r'.1 k = Sum.inr (AggTok.nest b') → NestedValue.WCorr h.toRingHom b' b) :

        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).

        def rowPairs {T K K' : Type} {n : ℕ} (u' : Tuple (GenValue T K') n) (u : Tuple (GenValue T K) n) :
        AggTok T K' × AggTok T K → Prop

        The pairs of corresponding aggregate values two rows hold.

        Equations
        Instances For
          Dependency graph
          def EvalEnv.HomSim {T : Type} [ValueType T] {K K' : Type} [CommSemiringWithMonus K] [CommSemiringWithMonus K'] [DecidableEq K'] (h : SemiringWithMonusHom K K') (E' : EvalEnv T K') (E : EvalEnv T K) {c : ℕ} (γ : Fin c → T) :

          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 #

            def groupTok {T : Type} [ValueType T] {K₀ : Type} {c m : ℕ} (f : SeqAggFunc T) (t : TermIn T c m) (kp : Option (Selection T m)) (sc : Bool) (U₀ : List (AnnotatedTuple T K₀ m)) (γ : Fin c → T) :
            AggTok T K₀

            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
            Instances For
              Dependency graph
              def groupSpec {T : Type} [ValueType T] {c m : ℕ} (f : SeqAggFunc T) (t : TermIn T c m) (γ : Fin c → T) (sc : Bool) (kp : Option (Selection T m)) :
              LeafSpec (Tuple T m) T

              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).

                def GPair {T : Type} [ValueType T] {K K' : Type} (𝒰₀ : AggTok T K → Prop) (𝒰₀' : AggTok T K' → Prop) (p : AggTok T K' × AggTok T K) :

                A pair of values of the two universes carrying one identifier.

                Equations
                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
                    noncomputable def lpU {T : Type} [ValueType T] {K K' : Type} [CommSemiringWithMonus K] [CommSemiringWithMonus K'] (h : SemiringWithMonusHom K K') (𝒰₀ : AggTok T K → Prop) (𝒰₀' : AggTok T K' → Prop) (κ : LeafKey T K) :

                    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
                      def LGU {T : Type} [ValueType T] {K K' : Type} (𝒰₀ : AggTok T K → Prop) (𝒰₀' : AggTok T K' → Prop) (e' : AggExpr T K') (e : AggExpr T K) :

                      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
                        def NGU {T : Type} [ValueType T] {K K' : Type} (𝒰₀ : AggTok T K → Prop) (𝒰₀' : AggTok T K' → Prop) (j : ℕ) (N' : NestNode T K' (NestInner T K' j)) (N : NestNode T K (NestInner T K j)) :

                        The node pairs a nested value of the universes reads: those of a pair of nested values of the universes.

                        Equations
                        Instances For
                          Dependency graph
                          def NestRelU {T : Type} [ValueType T] {K K' : Type} [CommSemiringWithMonus K] [CommSemiringWithMonus K'] (h : SemiringWithMonusHom K K') (𝒰₀ : AggTok T K → Prop) (𝒰₀' : AggTok T K' → Prop) (b' : NestedValue T K') (b : NestedValue T K) :

                          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
                            def ClassPres {T : Type} [ValueType T] {K K' : Type} [CommSemiringWithMonus K] [CommSemiringWithMonus K'] (h : SemiringWithMonusHom K K') (𝒰₀ : AggTok T K → Prop) (𝒰₀' : AggTok T K' → Prop) (x : AggTok T K) :

                            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
                              def RowG {T : Type} [ValueType T] {K K' : Type} [CommSemiringWithMonus K] [CommSemiringWithMonus K'] (h : SemiringWithMonusHom K K') (𝒰₀ : AggTok T K → Prop) (𝒰₀' : AggTok T K' → Prop) {n : ℕ} (r' : GenRow T K' n) (r : GenRow T K n) :

                              What a row carries: each pair of corresponding values records one identifier, and its class is presented.

                              Equations
                              Instances For
                                Dependency graph
                                structure HomUniv {T : Type} [ValueType T] {K K' : Type} [CommSemiringWithMonus K] [CommSemiringWithMonus K'] (𝒰₀ : AggTok T K → Prop) (𝒰₀' : AggTok T K' → Prop) (W : List (ℕ × ℕ)) :

                                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
                                  theorem keysFaithful_of_homUniv {T : Type} [ValueType T] {K K' : Type} [CommSemiringWithMonus K] [CommSemiringWithMonus K'] {h : SemiringWithMonusHom K K'} {𝒰₀ : AggTok T K → Prop} {𝒰₀' : AggTok T K' → Prop} {W : List (ℕ × ℕ)} (hU : HomUniv 𝒰₀ 𝒰₀' W) :
                                  KeysFaithful h.toRingHom (lpU h 𝒰₀ 𝒰₀') (LGU 𝒰₀ 𝒰₀') (NGU 𝒰₀ 𝒰₀')

                                  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
                                  theorem famPres_of_good {T : Type} [ValueType T] {K K' : Type} [CommSemiringWithMonus K] [DecidableEq K] [CommSemiringWithMonus K'] [DecidableEq K'] {h : SemiringWithMonusHom K K'} {𝒰₀ : AggTok T K → Prop} {𝒰₀' : AggTok T K' → Prop} {W : List (ℕ × ℕ)} (hU : HomUniv 𝒰₀ 𝒰₀' W) {S : AggTok T K' × AggTok T K → Prop} (hS : ∀ (p : AggTok T K' × AggTok T K), S p → GPair 𝒰₀ 𝒰₀' p ∧ ClassPres h 𝒰₀ 𝒰₀' p.2) :

                                  The families of pairs drawn from the universes, each class presented, are presented together.

                                  Dependency graph
                                  structure EnvG {T : Type} [ValueType T] {K K' : Type} [CommSemiringWithMonus K] [CommSemiringWithMonus K'] [DecidableEq K'] (h : SemiringWithMonusHom K K') (𝒰₀ : AggTok T K → Prop) (𝒰₀' : AggTok T K' → Prop) {c : ℕ} (γ : Fin c → T) (E' : EvalEnv T K') (E : EvalEnv T K) (l : List (String × ℕ)) :

                                  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
                                    def ColPair {T : Type} [ValueType T] {K K' : Type} [CommSemiringWithMonus K] [CommSemiringWithMonus K'] [DecidableEq K'] (h : SemiringWithMonusHom K K') (𝒰₀ : AggTok T K → Prop) (𝒰₀' : AggTok T K' → Prop) (v' : GenValue T K') (v : GenValue T K) :

                                    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
                                      theorem AggQueryIn.evaluate_hom_univ {T : Type} [ValueType T] {K K' : Type} [CommSemiringWithMonus K] [DecidableEq K] [CommSemiringWithMonus K'] [DecidableEq K'] [HasAltLinearOrder K] [HasAltLinearOrder K'] (h : SemiringWithMonusHom K K') {𝒰₀ : AggTok T K → Prop} {𝒰₀' : AggTok T K' → Prop} {W : List (ℕ × ℕ)} (hU : HomUniv 𝒰₀ 𝒰₀' W) {c n : ℕ} {κ : Fin n → ColKind} {l : List (String × ℕ)} (q : AggQueryIn T c n κ l) (d : AnnotatedDatabase T K) (γ : Fin c → T) (E' : EvalEnv T K') (E : EvalEnv T K) :
                                      EvalEnv.HomSim h E' E γ → EnvG h 𝒰₀ 𝒰₀' γ E' E l → (∀ (x : AggTok T K), q.Builds d γ E x → 𝒰₀ x) → (∀ (x : AggTok T K'), q.Builds (h.mapAnnotatedDatabase d) γ E' x → 𝒰₀' x) → (∀ e ∈ q.labWidths, e ∈ W) → q.framesContainSelf → q.sourceCols → q.AnnSettlesAt d γ E → Multiset.Rel (fun (r' : GenRow T K' n) (r : GenRow T K n) => GenRow.Sim h r' r ∧ RowG h 𝒰₀ 𝒰₀' r' r) (q.evaluate (h.mapAnnotatedDatabase d) γ E') (q.evaluate d γ E)

                                      The joint row-wise simulation, over the universes of the evaluation.

                                      Dependency graph
                                      theorem AggQueryIn.evaluate_hom_rel {T : Type} [ValueType T] {K K' : Type} [CommSemiringWithMonus K] [DecidableEq K] [CommSemiringWithMonus K'] [DecidableEq K'] [HasAltLinearOrder K] [HasAltLinearOrder K'] (h : SemiringWithMonusHom K K') {c n : ℕ} {κ : Fin n → ColKind} (q : AggQueryIn T c n κ) (d : AnnotatedDatabase T K) (γ : Fin c → T) (hld : q.labelsDistinct) (hrr : q.readsRecorded) (hsc : q.sourceCols) (hfc : q.allFramesContainSelf) (hrec : q.AnnSettlesAt d γ { }) :

                                      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.

                                      Dependency graph