Documentation

Provenance.AggValue

Symbolic aggregate tokens #

AggValue T K is the symbolic aggregate token of the general HAVING semantics: an aggregate function together with the ≼-sorted occurrence payload of the originating group, projected to pairs (value of the aggregated term, occurrence annotation) – exactly the data of Having.havingGroup that the possible-world semantics of an aggregate comparison consumes. It is the one-level analogue of KTensor (deliberately un-quotiented, so the possible worlds of the group can be read off the token); there is no recursion: ProvSQL rejects aggregation, grouping and ordering over aggregate values, and likewise rejects deduplication and difference on token-carrying relations, so no linear order or decidable equality on tokens is required by any permitted downstream operator (SeqAggFunc being a function type, structural decidable equality would not be available anyway).

Readings of a token #

mapAnn pushes a function K → K' through the annotations of a token: value-only readings are unchanged (collapse_mapAnn) and specialize composes with the pushforward (specialize_mapAnn). This is the token layer of the hom-commutation metatheorem for the general evaluator.

Lifted column values #

A column of a token-carrying relation holds either a regular value or a token: T ⊕ AggValue T K. AggValue.mapAnnSum and AggValue.collapseSum extend the pushforward and the deterministic reading to such lifted values; the kind-indexed syntax of the general evaluator governs statically which columns hold which arm.

def instDecidableEqTermIn.decEq {T✝ : Sort u_1} {c✝ n✝ : ℕ} [DecidableEq T✝] (x✝ x✝¹ : TermIn T✝ c✝ n✝) :
Decidable (x✝ = x✝¹)
Equations
Instances For
    Dependency graph
    @[instance_reducible]
    instance instDecidableEqTermIn {T✝ : Sort u_1} {c✝ n✝ : ℕ} [DecidableEq T✝] :
    DecidableEq (TermIn T✝ c✝ n✝)
    Equations
    Dependency graph
    inductive FamId (T : Type) :

    The identity of an aggregate value. Its family is the label of the operator that produced it, a key telling its groups (or rows) apart, and the apply parameters the operator reads – an operator evaluated on the same inputs producing the same occurrences. A regular parameter is recorded by its value; an aggregate parameter by its own identity, the aggregate value itself and not the value it takes in a world. The identity adds the column of the operator that produced the value and the terms applied to it since (ProjColIn.aggTermOf): two columns of one family, or one column under two terms, are two different parameters.

    Instances For
      Dependency graph
      def FamId.decEq {T : Type} [DecidableEq T] (a b : FamId T) :
      Decidable (a = b)

      Decidable equality, by structural recursion so that the kernel reduces it.

      Equations
      • One or more equations did not get rendered due to their size.
      Instances For
        Dependency graph
        def FamId.decEqParams {T : Type} [DecidableEq T] (a b : List (T ⊕ FamId T)) :
        Decidable (a = b)

        Decidable equality of parameter lists.

        Equations
        Instances For
          Dependency graph
          @[instance_reducible]
          Equations
          Dependency graph
          @[instance_reducible]

          Decidable equality of a family, stated once: the nested instance is past the size instance search explores.

          Equations
          Dependency graph
          def FamId.none {T : Type} :

          The identity carried where none is recorded.

          Equations
          Instances For
            Dependency graph
            def FamId.family {T : Type} :
            FamId T → ℕ × List T × List (T ⊕ FamId T)

            The family: what tells the occurrences apart – the producing operator, its key and the parameters it reads, without the column or the terms applied since. Two values of one family are read in one world.

            Equations
            Instances For
              Dependency graph
              def FamId.addTerm {T : Type} (t : TermIn T 1 0) :
              FamId T → FamId T

              The identity of a value after a term is applied to it.

              Equations
              Instances For
                Dependency graph
                structure OccId (T : Type) :

                The identity of an occurrence an aggregate value reads: the operator that aggregated it (its label), the values of the apply parameters that operator reads, its group's key (or its partition's, for a window), and its position in the group's (or partition's) listing. So the aggregates of one group, and the frames of one partition, share the occurrences they hold in common, an aggregation evaluated again on the same input gives the same occurrences, and one evaluated for other parameter values gives others – which is the identity the semantics gives occurrences. Two copies of a row are two positions, so two occurrences.

                • lab : ℕ

                  The aggregating operator's label.

                • params : List (T ⊕ FamId T)

                  The values of the parameters it reads.

                • key : List T

                  The key of its group or partition.

                • pos : ℕ

                  The position in the group's or partition's listing.

                Instances For
                  Dependency graph
                  def OccId.listing {T : Type} (lab : ℕ) (params : List (T ⊕ FamId T)) (key : List T) (len : ℕ) :

                  The identities of a group's or a partition's listing, position by position.

                  Equations
                  Instances For
                    Dependency graph
                    structure AggValue (T K : Type) :

                    A symbolic aggregate token: an aggregate function together with the (≼-sorted) occurrence payload of the originating group – for each occurrence, the value of the aggregated term paired with the occurrence annotation.

                    • agg : SeqAggFunc T

                      The sequence aggregate applied by every reading of the token.

                    • occs : List (T × K)

                      The occurrence payload: values of the aggregated term paired with the occurrence annotations, in the group's ≼-order.

                    • scalar : Bool

                      Whether the empty world is one of this token's worlds.

                      A token whose row exists only because its group does is never read where the group is empty, and the reading skips that world. A token whose row exists on its own – an aggregation with no grouping, whose single row survives an empty input, or a window frame that may exclude the row it is computed for – is read there too, and the aggregate then sees the empty sequence. The flag travels with the token because a comparison may be far from the operator that built it, past projections and joins, and cannot otherwise tell which reading applies.

                    • fam : FamId T

                      Which occurrence family the token reads: the label of the operator that computed it and the key of its group (or the row a window computed it for). Two aggregate values of one row share their occurrences exactly when they carry the same family, which is what a predicate reading both has to know to read them in one world. No reading of the token itself looks at it.

                    • oids : List (OccId T)

                      The identities of its occurrences, one per element of occs, where the operator that built the token records them (a grouping and a window with no FILTER clause and no DISTINCT); empty otherwise. No reading of the token looks at them: they say which occurrences two aggregate values share, which is what the equivalence of GenRow.zeqRen compares.

                    Instances For
                      Dependency graph
                      def AggValue.ofGroup {T K : Type} {m : ℕ} [ValueType T] {c : ℕ} (f : SeqAggFunc T) (t : TermIn T c m) (U : List (AnnotatedTuple T K m)) (γ : Fin c → T := fun (x : Fin c) => 0) :

                      The token of a group with occurrence sequence U, aggregating the term t with f: the projection of the group payload.

                      Equations
                      Instances For
                        Dependency graph
                        def AggValue.anns {T K : Type} (a : AggValue T K) :
                        Fin a.occs.length → K

                        The occurrence annotations of a token, as a function on positions.

                        Equations
                        Instances For
                          Dependency graph
                          def AggValue.valOn {T K : Type} (a : AggValue T K) (W : Finset (Fin a.occs.length)) :
                          T

                          The aggregate value of the token in the possible world W of its group: the aggregate of the values of the kept occurrences, in order.

                          Equations
                          Instances For
                            Dependency graph
                            def AggValue.collapse {T K : Type} (a : AggValue T K) :
                            T

                            The deterministic reading: the aggregate of the whole occurrence sequence.

                            Equations
                            Instances For
                              Dependency graph

                              Merging the occurrences of equal value #

                              A DISTINCT window aggregate reads one occurrence per class of equal values in its frame, annotated by the ⊕ of the class's members. That is a transformation of the occurrence payload, and it has to be decided where the token is built: no reading of a token recovers it, the deterministic reading having already collapsed the sequence.

                              The classes are read in the order the domain gives their values, which is what makes the reading a function of the values and not of the input sequence: deduplication leaves one value per class and not a sequence, so nothing else could fix the order, and an order-dependent aggregate would otherwise read one the query does not determine. SQL draws the line in the same place, rejecting an ORDER BY inside a DISTINCT aggregate unless it appears in the argument list.

                              It is also what makes the reading world by world sound with no condition on the aggregate: the domain's order restricted to the classes a world holds is that world's own order, an order being stable under passing to a subsequence. The operator that carries the flag is not here yet.

                              def AggValue.classSum {T K : Type} [ValueType T] [AddCommMonoid K] (l : List (T × K)) (v : T) :
                              K

                              The ⊕ of the annotations of the occurrences of one value: the annotation its class carries once the occurrences of equal value are merged.

                              Equations
                              Instances For
                                Dependency graph
                                def AggValue.mergeOccs {T K : Type} [ValueType T] [AddCommMonoid K] (l : List (T × K)) :
                                List (T × K)

                                An occurrence payload read over its distinct values: one occurrence per class of equal values, carrying the ⊕ of the class's annotations, the classes read in the order the domain gives their values. This is what a DISTINCT window aggregate reads, and the order being a function of the values is what makes it a reading rather than a choice – so nothing is asked of the aggregate, and in particular not symmetry.

                                Equations
                                Instances For
                                  Dependency graph

                                  The same on a token: the payload merged, the aggregate and the convention its own.

                                  Equations
                                  Instances For
                                    Dependency graph
                                    def AggValue.specialize {T K : Type} (a : AggValue T K) (ν : K → Bool) :
                                    T

                                    The world-faithful reading under a valuation ν of the annotations: restrict to the occurrences whose annotation ν realizes, and aggregate those in order.

                                    Equations
                                    Instances For
                                      Dependency graph
                                      def AggValue.mapAnn {T K K' : Type} (h : K → K') (a : AggValue T K) :

                                      Pushforward of h : K → K' through the annotations of a token; the values are untouched.

                                      Equations
                                      Instances For
                                        Dependency graph
                                        def AggValue.predProv {T K : Type} [ValueType T] [CommSemiringWithMonus K] [DecidableEq K] (a : AggValue T K) (op : CompOp) (c : T) :
                                        K

                                        Predicate provenance of an atomic comparison against a token: the ⊕-sum, over the non-empty possible worlds of the token's group, of the world annotation times the characteristic value of the comparison between the world's aggregate value and the regular value c. Non-empty worlds only: the predicate provenance already enforces group existence, exactly as in the fused semantics Having.havingProv.

                                        Equations
                                        Instances For
                                          Dependency graph
                                          def AggValue.predProvScalar {T K : Type} [ValueType T] [CommSemiringWithMonus K] [DecidableEq K] (a : AggValue T K) (op : CompOp) (c : T) :
                                          K

                                          Predicate provenance in the scalar convention: the same ⊕-sum as predProv, but over all worlds of the occurrence payload, the empty one included, where the aggregate reads the empty sequence (valOn_empty).

                                          The two conventions answer to two situations. Where a row exists only because its group does – a GROUP BY key – the comparison is never read in a world without occurrences, and predProv is the reading. Where the row exists on its own and the aggregate may range over nothing – an aggregation with no grouping, whose single row survives an empty input, or a frame that may exclude the row it is computed for – the empty world is a world, and the comparison must be given a value there. predProvScalar is that reading; the two differ by exactly the empty world's term (predProvScalar_eq_predProv_add).

                                          Equations
                                          Instances For
                                            Dependency graph
                                            def AggValue.ofScalarGroup {T K : Type} {m : ℕ} [ValueType T] {c : ℕ} (f : SeqAggFunc T) (t : TermIn T c m) (U : List (AnnotatedTuple T K m)) (γ : Fin c → T := fun (x : Fin c) => 0) :

                                            The token of a group, read in the scalar convention: the same payload, with the empty world among its worlds. This is what an aggregation with no grouping produces, and what a window frame that may exclude its current row produces.

                                            Equations
                                            • One or more equations did not get rendered due to their size.
                                            Instances For
                                              Dependency graph
                                              def AggValue.predProvOf {T K : Type} [ValueType T] [CommSemiringWithMonus K] [DecidableEq K] (a : AggValue T K) (op : CompOp) (c : T) :
                                              K

                                              Predicate provenance in the token's own convention. A comparison reads a token by the flag it carries, so that an operator settles the convention once, where the token is built, and every comparison downstream follows it.

                                              Equations
                                              Instances For
                                                Dependency graph

                                                Two atoms on one token #

                                                A selection whose predicate conjoins two comparisons of the same token – a truncation's m < #(k+1) ≤ m+c, a HAVING such as count(*) > 2 AND count(*) < 5 – multiplies the two atoms' provenances, each summed over the worlds of the token separately. That is not in general the sum over the worlds where both comparisons hold, and the definitions below name the joint reading so that the difference can be stated.

                                                def AggValue.predProvAnd {T K : Type} [ValueType T] [CommSemiringWithMonus K] [DecidableEq K] (a : AggValue T K) (op₁ : CompOp) (c₁ : T) (op₂ : CompOp) (c₂ : T) :
                                                K

                                                The predicate provenance of two aggregate atoms on one token, read jointly: the ⊕-sum over the worlds in which both comparisons hold.

                                                Equations
                                                Instances For
                                                  Dependency graph
                                                  def AggValue.predProvScalarAnd {T K : Type} [ValueType T] [CommSemiringWithMonus K] [DecidableEq K] (a : AggValue T K) (op₁ : CompOp) (c₁ : T) (op₂ : CompOp) (c₂ : T) :
                                                  K

                                                  The scalar-convention counterpart of predProvAnd: the same joint sum, over all worlds of the token, the empty one included. This is the reading a window's token needs, its frame being allowed to exclude the row it is computed for.

                                                  Equations
                                                  Instances For
                                                    Dependency graph
                                                    def AggValue.predProvOfAnd {T K : Type} [ValueType T] [CommSemiringWithMonus K] [DecidableEq K] (a : AggValue T K) (op₁ : CompOp) (c₁ : T) (op₂ : CompOp) (c₂ : T) :
                                                    K

                                                    The joint reading in the token's own convention.

                                                    Equations
                                                    Instances For
                                                      Dependency graph
                                                      theorem AggValue.predProvOf_mul_predProvOf {T K : Type} [ValueType T] [CommSemiringWithMonus K] [DecidableEq K] (hexcl : exclusive K) (hidem : mulIdempotent K) (a : AggValue T K) (op₁ : CompOp) (c₁ : T) (op₂ : CompOp) (c₂ : T) :
                                                      a.predProvOf op₁ c₁ * a.predProvOf op₂ c₂ = a.predProvOfAnd op₁ c₁ op₂ c₂

                                                      A range test on one token reads jointly exactly under these two properties. A selection whose predicate conjoins two comparisons of the same token – a truncation's m < #(k+1) ≤ m+c, a HAVING such as count(*) > 2 AND count(*) < 5 – multiplies the two provenances, each summed over the worlds separately. That is the joint sum over the worlds where both hold when the m-semiring is exclusive and its multiplication is idempotent, and not otherwise.

                                                      Dependency graph

                                                      A test in place of a comparison #

                                                      An atom that carries a three-valued test on the token's value rather than a comparison against a term reads the same way – one sum over the worlds, weighted by whether the test holds there – and a range is then one atom. The ∧ rule becomes a decomposition of that sum, which is what the hypotheses above are for.

                                                      def AggValue.predProvWith {T K : Type} [ValueType T] [CommSemiringWithMonus K] [DecidableEq K] (a : AggValue T K) (P : T → Kleene) :
                                                      K

                                                      The predicate provenance of an arbitrary three-valued test on the token's value: the ⊕-sum, over the worlds of the group, of the world's annotation weighted by whether the test holds there. predProv is the case of a comparison against a term, and a range is the case of the conjunction of two – one atom, and not a product of two.

                                                      Equations
                                                      Instances For
                                                        Dependency graph

                                                        The scalar-convention counterpart: the same sum over all worlds, the empty one included.

                                                        Equations
                                                        Instances For
                                                          Dependency graph
                                                          def AggValue.predProvOfWith {T K : Type} [ValueType T] [CommSemiringWithMonus K] [DecidableEq K] (a : AggValue T K) (P : T → Kleene) :
                                                          K

                                                          The test read in the token's own convention.

                                                          Equations
                                                          Instances For
                                                            Dependency graph

                                                            Reindexing bridges #

                                                            The occurrence payload of ofGroup is a List.map image of the group sequence, so worlds over the token and worlds over the group live over propositionally – not definitionally – equal position types. The bridges below transport seqOf, worldAnn and the two readings along the length-preserving equivalence finCongr.

                                                            theorem AggValue.predProvScalar_count_ne_zero {T K : Type} [ValueType T] [CommSemiringWithMonus K] [DecidableEq K] (h_abs : absorptive K) (a : AggValue T K) (hc : a.agg.Counts) (hnn : ∀ o ∈ a.occs, ValueType.isNull o.1 = false) :

                                                            COUNT(κ) ≥ 1 is the ⊕-sum of the occurrence annotations. Where the counted values are never null, every non-empty world counts at least one and the empty world counts none, so the comparison holds in exactly the non-empty worlds – an upward-closed family, which Having.sum_ann_meet collapses. Absorptivity is what that collapse needs; distributivity of ⊗ over ⊖ is not used.

                                                            Dependency graph

                                                            ofGroup bridges to the fused semantics #

                                                            theorem AggValue.predProv_ofGroup {T K : Type} {m : ℕ} [ValueType T] [CommSemiringWithMonus K] [DecidableEq K] (f : SeqAggFunc T) (t : Term T m) (U : List (AnnotatedTuple T K m)) (op : CompOp) (c : T) :
                                                            (ofGroup f t U).predProv op c = Having.havingProv U t f op c

                                                            Regression bridge, token side. The predicate provenance of a comparison against the token of a group is the fused semantics' predicate provenance of the same comparison on that group.

                                                            Dependency graph

                                                            Pushforward lemmas #

                                                            Lifted column values #

                                                            def AggValue.mapAnnSumVal {T K K' : Type} (h : K → K') :
                                                            T ⊕ AggValue T K → T ⊕ AggValue T K'

                                                            Pushforward of h : K → K' on a lifted column value: data is untouched, a token maps its annotations.

                                                            Equations
                                                            Instances For
                                                              Dependency graph
                                                              def AggValue.collapseSumVal {T K : Type} :
                                                              T ⊕ AggValue T K → T

                                                              Deterministic reading of a lifted column value: data is itself, a token collapses.

                                                              Equations
                                                              Instances For
                                                                Dependency graph

                                                                Reading an aggregate value as a key: its worlds and its values #

                                                                An operator comparing keys reads an aggregate column in each world, so what it needs of the column is the set of values it takes and, for each, the provenance of taking it.

                                                                def AggValue.worlds {T K : Type} (a : AggValue T K) :

                                                                The worlds of an aggregate value: every subfamily when it is read in the scalar convention, the non-empty ones when it is grouped.

                                                                Equations
                                                                Instances For
                                                                  Dependency graph
                                                                  def AggValue.vals {T K : Type} [ValueType T] (a : AggValue T K) :

                                                                  Val(a): the values the aggregate value takes over its worlds.

                                                                  Equations
                                                                  Instances For
                                                                    Dependency graph
                                                                    def AggValue.valsOf {T : Type} [ValueType T] (f : SeqAggFunc T) (sc : Bool) (L : List T) :

                                                                    The same set, read off the aggregate, the convention and the list of values alone – which is what makes it insensitive to anything that moves occurrences without moving their values.

                                                                    Equations
                                                                    Instances For
                                                                      Dependency graph

                                                                      The values a token takes depend on its occurrences only through their values.

                                                                      Dependency graph
                                                                      theorem AggValue.vals_mapAnn {T K : Type} [ValueType T] {K'' : Type} (h : K → K'') (a : AggValue T K) :
                                                                      (mapAnn h a).vals = a.vals

                                                                      Pushing the annotations forward changes no value the token takes.

                                                                      Dependency graph
                                                                      def AggValue.altProv {T K : Type} [ValueType T] [CommSemiringWithMonus K] [DecidableEq K] (a : AggValue T K) (v : T) :
                                                                      K

                                                                      [a ≐ v]: the predicate provenance of the atom comparing the aggregate value with v, under SQL's null-safe equality – so the case v = NULL is the atom a IS NULL and asks for no separate clause.

                                                                      Equations
                                                                      Instances For
                                                                        Dependency graph
                                                                        theorem AggValue.sum_altProv {T K : Type} [ValueType T] [CommSemiringWithMonus K] [DecidableEq K] (a : AggValue T K) :
                                                                        ∑ v ∈ a.vals, a.altProv v = ∑ W ∈ a.worlds, Having.worldAnn a.anns W

                                                                        The alternatives exhaust the worlds: their shares add up to what the aggregate value's worlds carry, so reading a key through them loses nothing and invents nothing.

                                                                        Dependency graph
                                                                        theorem AggValue.altProv_mul_eq_zero {T K : Type} [ValueType T] [CommSemiringWithMonus K] [DecidableEq K] (hexcl : exclusive K) (a : AggValue T K) {v v' : T} (h : v ≠ v') :
                                                                        a.altProv v * a.altProv v' = 0

                                                                        Distinct alternatives of one occurrence exclude each other, where K is exclusive: distinct values come from distinct worlds, and two distinct worlds' annotations multiply to 𝟘. In 𝔹[X] this is the statement that exactly one alternative of a present occurrence holds under each valuation; over ℕ[X], where exclusivity fails, an operator that combines two alternatives of one occurrence – a window over a partition holding both – counts worlds that do not exist.

                                                                        Dependency graph