Documentation

Provenance.AggQuery

Kind-indexed general queries and their annotated semantics #

The general (non-fused) HAVING semantics: aggregate values produced by a grouping operator γ^≼ are carried through further operators – projection, join, union, additional selections – as symbolic tokens (AggValue) in dedicated columns, and compared downstream, the possible worlds of such a comparison being those of the originating group.

Kind-indexed syntax #

Queries are indexed by a column-kind vector κ : Fin n → ColKind (regular vs aggregate-token), so that the scope conditions are enforced statically and no theorem carries a well-formedness hypothesis:

Factored annotations and the σ/predsem combination #

The row annotation of the general evaluator is kept in factored form GenAnn: a concrete part base : K together with pending, a multiset of group-existence factors – one entry per γ-group whose tokens have not yet been compared, recorded as the group's occurrence-annotation list l and worth δ(⊕ l). The effective annotation of a row is base ⊗ ⊗_{l ∈ pending} δ(⊕ l) (GenAnn.finalize).

This factoring implements the replace-the-δ-factor combination rule:

∧ ↦ ⊗, ∨ ↦ ⊕ and ¬ pushed down to the atoms by De Morgan duality with comparison-operator complementation, exactly as in HavingPred and in ProvSQL. A selection whose predicate contains no aggregate atom filters classically, matching Query.evaluateAnnotated.

Scalar aggregation (aggregation without grouping, whose empty input is a real possible world in ProvSQL) is out of scope: Gamma is the grouped operator only.

inductive ColKind :

The kind of a column: a regular value or an aggregate token.

Instances For
    Dependency graph
    @[instance_reducible]
    Equations
    Dependency graph

    The value-arm kind of a column kind: prov columns hold ordinary values (as ProvSQL's uuid columns do), so their conformance arm is reg.

    Equations
    Instances For
      Dependency graph
      @[reducible, inline]
      abbrev GenValue (T K : Type) :

      A lifted column value: a regular value or an aggregate token, the token being an ordinary one or a nested one (AggTok).

      Equations
      Instances For
        Dependency graph
        def GenValue.collapse {T K : Type} :
        GenValue T K → T

        The deterministic reading of a lifted value.

        Equations
        Instances For
          Dependency graph
          def GenValue.innerValue {T K : Type} :
          GenValue T K → AggExpr T K

          How a lifted value is read as an aggregate expression: an aggregate expression is itself – a term over several aggregate columns is one – an ordinary token is the expression of itself (AggExpr.ofValue, keeping the identities of its occurrences), and a regular value reads no occurrence and returns itself (NestedValue.constInner), so that aggregating a regular column nests nothing. A nested value is no expression and is read here through its collapse; a second-level aggregation reads it as a node instead (GenValue.innerAt).

          Equations
          Instances For
            Dependency graph
            def GenValue.innerLev {T K : Type} :
            GenValue T K → ℕ

            The storey a lifted value is read at by a second-level aggregation: one above a nested value's own, 0 for anything else.

            Equations
            Instances For
              Dependency graph
              def GenValue.innerAt {T K : Type} (x : GenValue T K) (D : ℕ) :
              NestInner T K D

              How a lifted value is read as the inner reading of a nested aggregation of storey D: a nested value of storey D - 1 is a node of that storey, read world by world with its own occurrences; anything else is what storey D - 1 reads, down to an aggregate expression at storey 0 (GenValue.innerValue). The aggregation takes D to be the largest storey its group's rows need, so every nested value is placed at its own storey and none is read through its collapse.

              Equations
              Instances For
                Dependency graph
                structure GenAnn (K : Type) :

                The factored annotation of a row of the general evaluator: the concrete part base, and one pending group-existence factor per γ-group whose tokens have not been compared yet, recorded as the group's occurrence-annotation list.

                • base : K

                  The concrete annotation accumulated so far.

                • pending : Multiset (List K)

                  The occurrence-annotation lists of the uncompared groups.

                Instances For
                  Dependency graph

                  The effective annotation: the concrete part times the pending group-existence factors δ(⊕ l).

                  Equations
                  Instances For
                    Dependency graph
                    @[reducible, inline]
                    abbrev GenRow (T K : Type) (n : ℕ) :

                    A row of the general evaluator.

                    Equations
                    Instances For
                      Dependency graph

                      Terms over regular columns #

                      inductive TermGIn (T : Type) (c : ℕ) {n : ℕ} (κ : Fin n → ColKind) :

                      A term over the regular columns of a kind-indexed tuple: the index constructor requires its column to be regular, so terms over token columns are unrepresentable.

                      Instances For
                        Dependency graph
                        @[reducible, inline]
                        abbrev TermG (T : Type) {n : ℕ} (κ : Fin n → ColKind) :

                        A term of a closed query: no outer column to read.

                        Equations
                        Instances For
                          Dependency graph
                          def TermGIn.eval {T : Type} [ValueType T] {K : Type} {n c : ℕ} {κ : Fin n → ColKind} (t : TermGIn T c κ) (u : Tuple (GenValue T K) n) (γ : Fin c → T := fun (x : Fin c) => 0) :
                          T

                          Evaluation of a term on a lifted tuple. On the regular columns the kind index guarantees a regular value; the token arm of collapseSum is never reached on kind-conformant tuples and merely keeps the function total.

                          Equations
                          Instances For
                            Dependency graph

                            Generalized selection predicates #

                            inductive GenPredIn (T : Type) (c : ℕ) {n : ℕ} (κ : Fin n → ColKind) :

                            A generalized selection predicate: regular comparisons between terms over regular columns, aggregate comparisons of one bare token column against a regular term (the constant-folded normal form), and Boolean structure.

                            • cmp {T : Type} {c n : ℕ} {κ : Fin n → ColKind} : CompOp → TermGIn T c κ → TermGIn T c κ → GenPredIn T c κ

                              Regular atom: comparison of two terms over regular columns.

                            • aggCmp {T : Type} {c n : ℕ} {κ : Fin n → ColKind} (k : Fin n) : κ k = ColKind.agg → CompOp → TermGIn T c κ → GenPredIn T c κ

                              Aggregate atom: the token in column k compared against a regular term (a per-group constant: query constant or group-key attribute).

                            • aggRange {T : Type} {c n : ℕ} {κ : Fin n → ColKind} (k : Fin n) : κ k = ColKind.agg → CompOp → TermGIn T c κ → CompOp → TermGIn T c κ → GenPredIn T c κ

                              A range atom: the token in column k compared against two regular terms at once, read as one atom and not as the conjunction of two. The difference is not in what it says on a row – the two agree classically – but in what it annotates: one ⊕-sum over the worlds where both comparisons hold, which is what a truncation's m < #(k+1) ≤ m+c asks for. A conjunction of two atoms instead multiplies two sums, and that is the same value only when the m-semiring is exclusive with an idempotent ⊗ (AggValue.predProvOf_mul_predProvOf_with).

                            • and {T : Type} {c n : ℕ} {κ : Fin n → ColKind} : GenPredIn T c κ → GenPredIn T c κ → GenPredIn T c κ
                            • or {T : Type} {c n : ℕ} {κ : Fin n → ColKind} : GenPredIn T c κ → GenPredIn T c κ → GenPredIn T c κ
                            • not {T : Type} {c n : ℕ} {κ : Fin n → ColKind} : GenPredIn T c κ → GenPredIn T c κ
                            Instances For
                              Dependency graph
                              @[reducible, inline]
                              abbrev GenPred (T : Type) {n : ℕ} (κ : Fin n → ColKind) :

                              A predicate of a closed query.

                              Equations
                              Instances For
                                Dependency graph

                                The worlds a predicate is read in #

                                A predicate reading aggregate values is read in every world of the families they read, one world per family: values of one family share their occurrences and are read in one world, values of different families in independent ones. A world of a joint reading carries the product of its present annotations, the sum of its absent ones – the monus is taken once, over all the families – and the value each compared column takes there.

                                def AggTok.flatExpr {T K : Type} :
                                AggTok T K → AggExpr T K

                                The value as an aggregate expression over its occurrence family: an ordinary token is the one-leaf expression, an expression is itself. A nested value is read through its own worlds and never here.

                                Equations
                                Instances For
                                  Dependency graph
                                  def flatOk {T K : Type} {n : ℕ} (u : Tuple (GenValue T K) n) (M : List (Fin n)) {m : ℕ} (W : Finset (Fin m)) :

                                  Whether a subfamily of a flat family is a world of every value of it the columns M hold.

                                  Equations
                                  Instances For
                                    Dependency graph
                                    noncomputable def nestOk {T : Type} [ValueType T] {K : Type} [DecidableEq K] {n : ℕ} (u : Tuple (GenValue T K) n) (M : List (Fin n)) {d : ℕ} (W : NestedValue.World T K d) :

                                    Whether a world of a nested family is a world of every nested value the columns M hold.

                                    Equations
                                    Instances For
                                      Dependency graph
                                      noncomputable def classWorlds {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] {n : ℕ} (u : Tuple (GenValue T K) n) (M : List (Fin n)) :
                                      AggTok T K → Multiset (K × K × (Fin n → Option T))

                                      The worlds of one family, read at the columns M of the row that hold its values: per world, the product of the present annotations, the sum of the absent ones, and the value of each of those columns. The family is listed by the first of them, x₀; a world is one every value of the family accepts – one meeting the group of each grouped value.

                                      Equations
                                      • One or more equations did not get rendered due to their size.
                                      Instances For
                                        Dependency graph
                                        def tokCols {T K : Type} {n : ℕ} (u : Tuple (GenValue T K) n) (cols : List (Fin n)) :
                                        List (Fin n × AggTok T K)

                                        The aggregate columns among cols, with their values.

                                        Equations
                                        Instances For
                                          Dependency graph
                                          def combineW {T K : Type} [CommSemiringWithMonus K] {n : ℕ} (w₁ w₂ : K × K × (Fin n → Option T)) :
                                          K × K × (Fin n → Option T)

                                          Two joint worlds read together: products multiply, absent sums add, and each column takes its value from the one that gives it one.

                                          Equations
                                          • combineW w₁ w₂ = (w₁.1 * w₂.1, w₁.2.1 + w₂.2.1, fun (k : Fin n) => (w₁.2.2 k).or (w₂.2.2 k))
                                          Instances For
                                            Dependency graph
                                            def AggTok.classKey {T K : Type} [CommSemiringWithMonus K] (x : AggTok T K) :
                                            (ℕ × List T × List (T ⊕ FamId T)) × List K × Option ((j : ℕ) × Multiset (NestInner T K j × K))

                                            What groups two values of a row into one family of a joint reading: the family they were stamped with, together with their occurrence annotations and kind. Tokens of one family produced by one evaluation carry the same occurrences, so in a query whose operators bear distinct labels this is the family; the occurrences' annotations (and, for a nested value, its occurrences themselves) are part of the key so that the reading is defined on every row, a family being read in the worlds of the occurrences its members actually carry.

                                            Equations
                                            Instances For
                                              Dependency graph
                                              @[instance_reducible]
                                              noncomputable instance instDecidableEqClassKey {T : Type} [ValueType T] {K : Type} [DecidableEq K] :
                                              DecidableEq ((ℕ × List T × List (T ⊕ FamId T)) × List K × Option ((j : ℕ) × Multiset (NestInner T K j × K)))

                                              Decidable equality of a family key, stated once: the type is past the size instance search explores, and the nested component, which carries inner expressions, is compared classically – so that two keys with no nested component still compare in the kernel.

                                              Equations
                                              Dependency graph
                                              noncomputable def jointWorlds {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] {n : ℕ} (u : Tuple (GenValue T K) n) (cols : List (Fin n)) :
                                              Multiset (K × K × (Fin n → Option T))

                                              The joint worlds of the columns cols of a row: one world of each family they hold.

                                              Equations
                                              • One or more equations did not get rendered due to their size.
                                              Instances For
                                                Dependency graph
                                                def GenPredIn.hasAggAtom {T : Type} {c n : ℕ} {κ : Fin n → ColKind} :
                                                GenPredIn T c κ → Bool

                                                Does the predicate contain an aggregate atom? Selections without one filter classically.

                                                Equations
                                                Instances For
                                                  Dependency graph
                                                  def GenPredIn.eval3 {T : Type} [ValueType T] {K : Type} {c n : ℕ} {κ : Fin n → ColKind} (φ : GenPredIn T c κ) (u : Tuple (GenValue T K) n) (γ : Fin c → T := fun (x : Fin c) => 0) :

                                                  Classical (per-tuple) truth of a predicate, reading a compared token through its deterministic collapse. Used by the evaluator only on aggregate-atom-free predicates, where tokens are never consulted.

                                                  Equations
                                                  Instances For
                                                    Dependency graph
                                                    def GenPredIn.holds {T : Type} [ValueType T] {K : Type} {c n : ℕ} {κ : Fin n → ColKind} (φ : GenPredIn T c κ) (u : Tuple (GenValue T K) n) (γ : Fin c → T := fun (x : Fin c) => 0) :

                                                    The rows a selection keeps: those on which the predicate is true. A row on which it is unknown is kept by neither the predicate nor its negation.

                                                    Equations
                                                    Instances For
                                                      Dependency graph
                                                      def GenPredIn.decHolds {T : Type} [ValueType T] {K : Type} {c n : ℕ} {κ : Fin n → ColKind} (φ : GenPredIn T c κ) (u : Tuple (GenValue T K) n) (γ : Fin c → T := fun (x : Fin c) => 0) :
                                                      Decidable (φ.holds u γ)

                                                      Structural decidability of holds.

                                                      Equations
                                                      Instances For
                                                        Dependency graph
                                                        @[instance_reducible]
                                                        instance GenPredIn.instDecidableHolds {T : Type} [ValueType T] {K : Type} {c n : ℕ} {κ : Fin n → ColKind} (φ : GenPredIn T c κ) (γ : Fin c → T) (u : Tuple (GenValue T K) n) :
                                                        Decidable (φ.holds u γ)
                                                        Equations
                                                        Dependency graph
                                                        noncomputable def GenPredIn.predsem {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] {c n : ℕ} {κ : Fin n → ColKind} (φ : GenPredIn T c κ) (neg : Bool) (u : Tuple (GenValue T K) n) (γ : Fin c → T := fun (x : Fin c) => 0) :
                                                        K

                                                        Predicate provenance of a generalized predicate on a row, with ¬ pushed down to the atoms by De Morgan duality (the neg flag): a regular atom contributes its characteristic value χ, an aggregate atom the predicate provenance predProv of the comparison over its token's group, ∧ ↦ ⊗ and ∨ ↦ ⊕ (swapped under neg), and negated atoms complement their comparison operator, as in ProvSQL.

                                                        These rules are a short cut, and what they are a short cut for is the joint evaluation of the predicate's Boolean function in every world: the ⊕, over the worlds of the union of the families the predicate reads, of the world's annotation times the function's truth there, which is AggExpr.predProv. That is the semantics, for ProvSQL as for the library; computing it structurally is what an m-semiring with the right properties permits, and the properties are the content of the theorems. On one atom the two always agree (AggExpr.predProv_ofValue). On a conjunction the product is a decomposition of the joint reading under complementedness, exclusivity and an idempotent ⊗ (Having.sum_mul_sum_of_overlap, and complemented alone where the families are disjoint). On a disjunction there is no such theorem: the ⊕ fires in worlds where one group is empty, which are no worlds of the predicate, and 𝔹 and ℕ both witness the difference (bool_or_ne_joint, nat_or_ne_joint), so there the sum has to be computed rather than short cut. A range is the same point for ∧ on one family, which is why aggRange is an atom of its own rather than two atoms conjoined.

                                                        Equations
                                                        Instances For
                                                          Dependency graph
                                                          def GenPredIn.comparedCols {T : Type} {c n : ℕ} {κ : Fin n → ColKind} :
                                                          GenPredIn T c κ → Finset (Fin n)

                                                          The token columns compared by the predicate's aggregate atoms.

                                                          Equations
                                                          Instances For
                                                            Dependency graph
                                                            def GenPredIn.eval3W {T : Type} [ValueType T] {K : Type} {c n : ℕ} {κ : Fin n → ColKind} (φ : GenPredIn T c κ) (v : Fin n → Option T) (u : Tuple (GenValue T K) n) (γ : Fin c → T) :

                                                            The predicate's truth when each compared column takes the value v gives it.

                                                            Equations
                                                            Instances For
                                                              Dependency graph
                                                              noncomputable def GenPredIn.predsemJ {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] {c n : ℕ} {κ : Fin n → ColKind} (φ : GenPredIn T c κ) (neg : Bool) (u : Tuple (GenValue T K) n) (γ : Fin c → T) :
                                                              K

                                                              The joint predicate provenance: over the joint worlds of the families the predicate reads, the world's annotation times the truth of the predicate there (its falsity under neg).

                                                              Equations
                                                              • One or more equations did not get rendered due to their size.
                                                              Instances For
                                                                Dependency graph
                                                                def GenPredIn.entailsExistence {T : Type} {c n : ℕ} {κ : Fin n → ColKind} :
                                                                GenPredIn T c κ → Bool → Bool

                                                                Does the predicate provenance entail the compared groups' existence (under the polarity neg of the enclosing negations)? An aggregate atom does – its predicate provenance ranges over non-empty worlds only – while a regular atom's χ does not. A conjunction (∧ positively, ∨ under negation) entails as soon as one factor does; a disjunction only if every disjunct does. Mirrors ProvSQL's having_entails_group_existence: the supersede of the group-existence factor is licensed only when this holds, since e.g., agg-atom ∨ regular-atom can fire in worlds where the group is empty.

                                                                Equations
                                                                Instances For
                                                                  Dependency graph

                                                                  Projection columns #

                                                                  def TermIn.unary {T : Type} [ValueType T] (t : TermIn T 1 0) :
                                                                  T → T

                                                                  The function a term over one variable computes. A column that reads an aggregate column reads it through a term, and the aggregate expression it builds applies the function the term computes: this is that function.

                                                                  Equations
                                                                  Instances For
                                                                    Dependency graph
                                                                    def TermIn.atCol {T : Type} {c k : ℕ} {κ : Fin k → ColKind} (i : Fin k) (h : κ i = ColKind.reg) :
                                                                    TermIn T 1 0 → TermGIn T c κ

                                                                    A unary term reading a column: the same term with the column in place of its variable. It is how a term over an aggregate column re-types – read on the column as a regular one – and TermIn.evalPlain_atCol says the two compute the same value.

                                                                    Equations
                                                                    Instances For
                                                                      Dependency graph
                                                                      inductive ProjColIn (T : Type) (c : ℕ) {n : ℕ} (κ : Fin n → ColKind) :

                                                                      One output column of a generalized projection: a regular term over the regular input columns, or a verbatim copy of a token column (no arithmetic over tokens: the normal form).

                                                                      • term {T : Type} {c n : ℕ} {κ : Fin n → ColKind} : TermGIn T c κ → ProjColIn T c κ
                                                                      • token {T : Type} {c n : ℕ} {κ : Fin n → ColKind} (k : Fin n) : κ k = ColKind.agg → ProjColIn T c κ
                                                                      • aggTerm {T : Type} {c n : ℕ} {κ : Fin n → ColKind} (k : Fin n) : κ k = ColKind.agg → (T → T) → ProjColIn T c κ

                                                                        A term over one aggregate column: the column the term names, read through gf. It is again an aggregate column – the unary aggregate expression gf(a) of Provenance.AggExpr, which AggValue.postcomp represents – and it is what SQL's count(*) + 1 and the ranks produce. Only the value of gf in each world is used, so any deterministic function of SQL can be one.

                                                                      • aggTermOf {T : Type} {c n : ℕ} {κ : Fin n → ColKind} (k : Fin n) : κ k = ColKind.agg → TermIn T 1 0 → ProjColIn T c κ

                                                                        A term over one aggregate column, which is the shape the source language has: the column the term names, read through a term of the language, TermIn.unary being the function it computes. This is the aggregate expression g(a) with g the function the term computes; aggTerm, which takes any function, is wider. Being a term, it re-types like any other column: the same term reads a regular column.

                                                                      • provTerm {T : Type} {c n : ℕ} {κ : Fin n → ColKind} : TermGIn T c κ → ProjColIn T c κ
                                                                      Instances For
                                                                        Dependency graph
                                                                        def ProjColIn.sourceCol {T : Type} {n c : ℕ} {κ : Fin n → ColKind} :
                                                                        ProjColIn T c κ → Bool

                                                                        Whether a column is one the source language writes. Every column is, except the one carrying an arbitrary function of an aggregate column: that one belongs to the rewritten world, where the cast of a column has to act on the data arm of a composite value and leave the annotation arm alone. AggQueryIn.usesOnly asks for it, as it asks a query to be free of the other operators of that world.

                                                                        Equations
                                                                        Instances For
                                                                          Dependency graph
                                                                          @[reducible, inline]
                                                                          abbrev ProjCol (T : Type) {n : ℕ} (κ : Fin n → ColKind) :

                                                                          A projection column of a closed query.

                                                                          Equations
                                                                          Instances For
                                                                            Dependency graph
                                                                            def ProjColIn.kind {T : Type} {n c : ℕ} {κ : Fin n → ColKind} :
                                                                            ProjColIn T c κ → ColKind

                                                                            The kind of the output column.

                                                                            Equations
                                                                            Instances For
                                                                              Dependency graph
                                                                              def AggTok.postcompTerm {T : Type} [ValueType T] {K : Type} (t : TermIn T 1 0) (x : AggTok T K) :
                                                                              AggTok T K

                                                                              A term applied to an aggregate value: the value post-composed, its identity recording the term (FamId.addTerm), so that two terms of one column are two different parameters.

                                                                              Equations
                                                                              Instances For
                                                                                Dependency graph
                                                                                def ProjColIn.eval {T : Type} [ValueType T] {K : Type} {n c : ℕ} {κ : Fin n → ColKind} (p : ProjColIn T c κ) (u : Tuple (GenValue T K) n) (γ : Fin c → T := fun (x : Fin c) => 0) :

                                                                                Evaluation of a projection column on a lifted tuple.

                                                                                Equations
                                                                                Instances For
                                                                                  Dependency graph

                                                                                  An ORDER BY inside an aggregation #

                                                                                  SQL writes one inside the aggregate – array_agg(x ORDER BY y), string_agg, the ordered-set aggregates – and a symmetric aggregate does not need it: count and sum read the same value whichever order their group comes in. GroupOrder.unord says there is no clause, and then the group is read in the domain's canonical order, which is what every aggregation of this library did before the clause existed.

                                                                                  inductive GroupOrder (T : Type) (m : ℕ) :

                                                                                  The order an aggregate reads its group in. A clause's ties are broken by the row, as a window's are (OrderSpec.readLe), so the sequence is a function of the group and not of any listing of it.

                                                                                  Instances For
                                                                                    Dependency graph
                                                                                    def Relation.groupSeqOrd {T : Type} [ValueType T] {m n₁ : ℕ} (is : Tuple (Fin m) n₁) (ord : GroupOrder T m) (r : Relation T m) (g : Tuple T n₁) :
                                                                                    List (Tuple T m)

                                                                                    The rows of a group in the order its aggregate reads them.

                                                                                    Equations
                                                                                    Instances For
                                                                                      Dependency graph
                                                                                      def Relation.groupSeqOptOrd {T : Type} [ValueType T] {m n₁ : ℕ} (is : Tuple (Fin m) n₁) (ord : GroupOrder T m) (r : Relation T m) (g : Tuple T n₁) (keep : Option (Selection T m)) :
                                                                                      List (Tuple T m)

                                                                                      The same, cut by a FILTER clause where the aggregate carries one: the clause cuts what the aggregate reads, and the order is the aggregate's own.

                                                                                      Equations
                                                                                      Instances For
                                                                                        Dependency graph
                                                                                        def Having.havingGroupOrd {T : Type} [ValueType T] {K : Type} [HasAltLinearOrder K] {m n₁ : ℕ} (is : Tuple (Fin m) n₁) (ord : GroupOrder T m) (r : AnnotatedRelation T K m) (g : Tuple T n₁) :

                                                                                        The annotated group in the order its aggregate reads it: the occurrence sequence a token is built over. The clause reads the data columns, so it moves no annotation between occurrences carrying different rows.

                                                                                        Equations
                                                                                        Instances For
                                                                                          Dependency graph

                                                                                          Kind-indexed queries #

                                                                                          def ColKind.allReg (n : ℕ) :
                                                                                          Fin n → ColKind

                                                                                          The all-regular kind vector.

                                                                                          Equations
                                                                                          Instances For
                                                                                            Dependency graph
                                                                                            def TermIn.regOnly {T : Type} {c n : ℕ} (κ : Fin n → ColKind) :
                                                                                            TermIn T c n → Bool

                                                                                            A term reads regular columns only. An aggregate column holds a token, and a plain term reading one would read it through its deterministic collapse – the value SQL prints for it, but not what it reads in a given world. A window asks this of its aggregate term (WinReadsReg); the way to read an aggregate column as a value is AggQueryIn.Explode, which turns it into a regular one.

                                                                                            Equations
                                                                                            Instances For
                                                                                              Dependency graph
                                                                                              def WinReadsReg {T : Type} {c n m p : ℕ} (κ : Fin n → ColKind) (P : Tuple (Fin n) m) (O : Tuple (Fin n) p) (t : TermIn T c n) :

                                                                                              What a window may read of its input: its PARTITION BY, its ORDER BY and its aggregate term read regular columns only. An aggregate column of the input – that of an earlier window of the same SELECT, say – is carried through unchanged and read by nothing, the determinized peer order included (ColKind.readTuple). That is what makes the column read in a world what the plain window reads of that world: an aggregate column can order two occurrences one way in one world and the other way in the next, so a window that read one would not commute with the possible worlds. Ordering or partitioning by an aggregate reads it as a key, through AggQueryIn.Explode.

                                                                                              Equations
                                                                                              Instances For
                                                                                                Dependency graph
                                                                                                theorem winReadsReg_allReg {T : Type} {c n m p : ℕ} (P : Tuple (Fin n) m) (O : Tuple (Fin n) p) (t : TermIn T c n) :

                                                                                                An all-regular input satisfies it with nothing to check.

                                                                                                Dependency graph

                                                                                                A multi-frame window (AggQueryIn.WinExpr) asks no such condition, because its input is all-regular: its column is indexed by occurrence rather than determined by the row, and an occurrence of the relation a window reads does not determine the row it came from – two rows differing only in an aggregate column read alike – so carrying an aggregate column through one would need a canonical listing of general rows, which is an order on AggTok.

                                                                                                def SelOK {T : Type} (l : List (String × ℕ)) {c n : ℕ} {κ : Fin n → ColKind} (φ : GenPredIn T c κ) :

                                                                                                What a selection on a recursive term asks of its predicate: no aggregate atom. On a closed query – no hole – it asks nothing, and trivial discharges it, which is what lets a closed selection be written without a proof.

                                                                                                Equations
                                                                                                Instances For
                                                                                                  Dependency graph
                                                                                                  theorem SelOK.of_noAggAtom {T : Type} {l : List (String × ℕ)} {c n : ℕ} {κ : Fin n → ColKind} {φ : GenPredIn T c κ} (h : φ.hasAggAtom = false) :
                                                                                                  SelOK l φ

                                                                                                  A predicate with no aggregate atom is fine on any term.

                                                                                                  Dependency graph
                                                                                                  theorem SelOK.of_eq {T : Type} {l : List (String × ℕ)} {c n c' n' : ℕ} {κ : Fin n → ColKind} {κ' : Fin n' → ColKind} {φ : GenPredIn T c κ} {φ' : GenPredIn T c' κ'} (h : φ'.hasAggAtom = φ.hasAggAtom) (hφ : SelOK l φ) :
                                                                                                  SelOK l φ'

                                                                                                  The condition is read off the predicate's atoms only.

                                                                                                  Dependency graph
                                                                                                  theorem SelOK.and {T : Type} {l : List (String × ℕ)} {c n : ℕ} {κ : Fin n → ColKind} {φ ψ : GenPredIn T c κ} (hφ : SelOK l φ) (hψ : SelOK l ψ) :
                                                                                                  SelOK l (φ.and ψ)

                                                                                                  A conjunction of two admissible predicates is admissible.

                                                                                                  Dependency graph
                                                                                                  inductive AggQueryIn (T : Type) (c n : ℕ) :
                                                                                                  (Fin n → ColKind) → (l : optParam (List (String × ℕ)) []) → Type

                                                                                                  Kind-indexed general queries. The index discipline enforces the scope conditions: Gamma aggregates an all-regular input, Dedup and Diff require all-regular kinds, and the projection/selection grammars never compute over tokens.

                                                                                                  • Rel {T : Type} {c : ℕ} (n : ℕ) : String → AggQueryIn T c n (ColKind.allReg n)

                                                                                                    Base relation (all-regular).

                                                                                                  • Hole {T : Type} {c : ℕ} (n : ℕ) (s : String) (κ : Fin n → ColKind := ColKind.allReg n) : AggQueryIn T c n κ [(s, n)]

                                                                                                    The recursive reference: the relation name s of arity n bound by the enclosing recursion, which is the one hole a recursive term holds. The last index of the syntax lists a term's holes, so a closed query has none, a recursion's term has exactly this one, and the operators a hole may sit under are those whose typing passes the index through: a projection, a selection with no aggregate atom, either side of a product, the left side of an apply, either side of a union, the alternatives and a retagging. Everything else is closed. This restriction on a recursive term is in the type rather than beside it.

                                                                                                  • Param {T : Type} {c m : ℕ} (pv : Fin m → T ⊕ Fin c) (ρ : Fin m → ColKind) : AggQueryIn T c m ρ

                                                                                                    Parameters, as a relation: one row annotated 𝟙, column k being the parameter pv k of the context – or the constant it names – with kind ρ k. In the right side of an apply the context starts with the row of its left side, and an aggregate column of that row is here an aggregate value, with its occurrences, read as any aggregate column is: a token column of a projection, an aggregate atom of a selection, a nested aggregation's term. That is how the semantics reads an aggregate parameter, world by world; a term's outer k reads a parameter as a plain value, and only a non-aggregate one (AggQueryIn.wellKinded). The parameters are addressed by position, like outer, so the leaf substitutes as a term does.

                                                                                                  • Empty {T : Type} {c : ℕ} : AggQueryIn T c 0 (ColKind.allReg 0)

                                                                                                    The empty relation of arity 0, empty on every instance. It is the one leaf that belongs to the query and not to the instance, which is what makes it the base of everything a query can build from nowhere: the unit relation is the scalar aggregation of it with no aggregate (Derived.unit, one empty tuple annotated 𝟙, which is PostgreSQL's SELECT;), and SQL's VALUES is a union of projections of that onto constants (Derived.values). A constant relation therefore needs no leaf of its own, and this one needs no side condition: non-emptiness is a condition of the derived notation, not of the syntax.

                                                                                                    Keeping it at arity 0 is what leaves GammaScalar alone in its class: every other operator is empty on an empty instance, and the scalar aggregation is the one that emits a row regardless.

                                                                                                  • Proj {T : Type} {c n m : ℕ} {κ : Fin n → ColKind} {l : List (String × ℕ)} (ps : Tuple (ProjColIn T c κ) m) : AggQueryIn T c n κ l → AggQueryIn T c m (fun (j : Fin m) => (ps j).kind) l

                                                                                                    Generalized projection.

                                                                                                  • Sel {T : Type} {c n : ℕ} {κ : Fin n → ColKind} {l : List (String × ℕ)} (φ : GenPredIn T c κ) : AggQueryIn T c n κ l → (hφ : autoParam (SelOK l φ) _auto_1) → AggQueryIn T c n κ l

                                                                                                    Generalized selection. On a recursive term – one with a hole – the predicate carries no aggregate atom, which the trailing proof says; on a closed query it says nothing, and the tactic finds it.

                                                                                                  • Prod {T : Type} {c n₁ n₂ : ℕ} {κ₁ : Fin n₁ → ColKind} {κ₂ : Fin n₂ → ColKind} {l₁ l₂ : List (String × ℕ)} : AggQueryIn T c n₁ κ₁ l₁ → AggQueryIn T c n₂ κ₂ l₂ → AggQueryIn T c (n₁ + n₂) (Fin.append κ₁ κ₂) (l₁ ++ l₂)

                                                                                                    Cartesian product (join).

                                                                                                  • Apply {T : Type} {c n₁ n₂ : ℕ} {κ₁ : Fin n₁ → ColKind} {κ₂ : Fin n₂ → ColKind} {l : List (String × ℕ)} : AggQueryIn T c n₁ κ₁ l → AggQueryIn T (n₁ + c) n₂ κ₂ → AggQueryIn T c (n₁ + n₂) (Fin.append κ₁ κ₂) l

                                                                                                    Apply – SQL's LATERAL, the operator of Galindo-Legaria & Joshi: a product whose right side is read once per row of the left and may read that row's columns. The right side's context is the left side's columns followed by the ambient outer ones, so in a closed apply the right side reads exactly the left arity. Its output pairs each row u of the left with each row of the right read at u, and multiplies their annotations.

                                                                                                    It is not derivable from the cross product once annotations are there: the product reads its right side once, the apply once per row of the left, and it is the apply that a correlated subquery needs.

                                                                                                    The left side may carry aggregate columns, so that a product of two token-carrying relations is an apply too. The right side reads such a column world by world: the left row's values, tokens included, are the context of the environment the evaluator carries (EvalEnv), and the leaf AggQueryIn.Param reads them into columns of the same kinds. A term reads a parameter as a plain value only where it is not aggregate (AggQueryIn.wellKinded).

                                                                                                  • Sum {T : Type} {c n : ℕ} {κ : Fin n → ColKind} {l₁ l₂ : List (String × ℕ)} : AggQueryIn T c n κ l₁ → AggQueryIn T c n κ l₂ → AggQueryIn T c n κ (l₁ ++ l₂)

                                                                                                    Union (all).

                                                                                                  • Dedup {T : Type} {c n : ℕ} : AggQueryIn T c n (ColKind.allReg n) → AggQueryIn T c n (ColKind.allReg n)

                                                                                                    Duplicate elimination – all-regular only.

                                                                                                  • Diff {T : Type} {c n : ℕ} : AggQueryIn T c n (ColKind.allReg n) → AggQueryIn T c n (ColKind.allReg n) → AggQueryIn T c n (ColKind.allReg n)

                                                                                                    Difference – all-regular only.

                                                                                                  • Mu {T : Type} {c n : ℕ} {κ : Fin n → ColKind} (s : String) : AggQueryIn T c n κ → AggQueryIn T c n κ [(s, n)] → AggQueryIn T c n κ

                                                                                                    Recursion with duplicate-preserving rounds: SQL's WITH RECURSIVE … UNION ALL. The relation name s of arity n is bound to the previous round inside q₁, so the rounds are M₀ = ⟦q₀⟧ and M_{i+1} = ⟦q₁⟧_{d[s ↦ Mᵢ]}, and the query is their multiset sum.

                                                                                                    The operator is partial: it means the sum of the rounds up to the first empty one, and means nothing where no round is empty (MuSettles). The evaluator is total and says ⨄_{i<n} Mᵢ for that n where there is one, junk elsewhere, which is why every result about a recursion carries AggQueryIn.recSettles; a bounded computation witnesses the value through AggQueryIn.evaluate_Mu_of_empty. The round count is not part of the query: a recursion that stops at a count rather than at its own rounds is not this operator.

                                                                                                    The rows a round carries may hold aggregate columns, with their aggregate values: the annotated evaluator binds the round in an environment of general rows (EvalEnv), not in the database. The recursive term reads them as the restriction on it allows – carried by a projection, as a token or under a term (aggTermOf), but never compared, its selections reading regular columns only (SelOK).

                                                                                                  • MuSet {T : Type} {c n : ℕ} (s : String) : AggQueryIn T c n (ColKind.allReg n) → AggQueryIn T c n (ColKind.allReg n) [(s, n)] → AggQueryIn T c n (ColKind.allReg n)

                                                                                                    Recursion up to duplicates: SQL's WITH RECURSIVE … UNION. The least fixpoint the semantics says it is: X₀ empty, X_{j+1} = ⟦ε(q₀ ⊎ q₁)⟧_{d[s ↦ X_j]} with annotations, and the query is X_j for the first j with X_{j+1} = X_j.

                                                                                                    Partial, like Mu: it means nothing where the rounds never settle (MuSetSettles), the evaluator says junk there, and results carry AggQueryIn.recSettles; AggQueryIn.evaluate_MuSet_of_fix turns a round that repeats into the value. It settles whenever no tuple has a derivation through itself, and in an absorptive semiring with such derivations too.

                                                                                                  • Explode {T : Type} {c n : ℕ} {κ : Fin n → ColKind} {l : List (String × ℕ)} (k : Fin n) : κ k = ColKind.agg → AggQueryIn T c n κ l → AggQueryIn T c n (Function.update κ k ColKind.reg) l

                                                                                                    Exploding an aggregate column: reading it as a key. Every operator here that compares keys – Dedup, Diff, the grouping and partition indices – takes regular columns, so a query that groups on a count or deduplicates on an aggregate is written by first reading the column as a key: the occurrence is replaced by its alternatives, one per value the column takes, each carrying [a ≐ v], and the column becomes regular (GenRow.alternativesAt). This is ProvSQL's rewrite_explode_agg_value (one row per value the aggregate takes over the possible worlds), the reading of an aggregate column as a key, as against the reading as a value, which the aggregate atoms and terms have world by world and which needs no operator. Over a plain relation an aggregate value is a value and this is the identity – it is a typing device there, charged to no class by usesOnly; in the annotated semantics it is an operator of its own, out of the language the annotated classification is about (noExplode).

                                                                                                  • Gamma {T : Type} {c m n₁ n₂ lab : ℕ} {rd : Fin c → Bool} (is : Tuple (Fin m) n₁) (ts : Tuple (TermIn T c m) n₂) (fs : Tuple (SeqAggFunc T) n₂) : AggQueryIn T c m (ColKind.allReg m) → (keep : optParam (Fin n₂ → Option (Selection T m)) fun (x : Fin n₂) => none) → (ord : optParam (GroupOrder T m) GroupOrder.unord) → AggQueryIn T c (n₁ + n₂) (Fin.append (fun (x : Fin n₁) => ColKind.reg) fun (x : Fin n₂) => ColKind.agg)

                                                                                                    The decomposed grouping operator γ^≼: group the (all-regular) input by the key columns is; one output row per group, carrying the key followed by one aggregate token per (term, aggregate) pair.

                                                                                                    Each pair may carry a FILTER clause, keep j, which cuts what that aggregate reads of its group – and nothing else. A filtered aggregate's column is therefore an aggregate expression over the whole group (AggExpr.ofGroupWhen): the worlds are the group's non-empty subfamilies, as with no clause, every occurrence carrying its annotation to them, and the leaf reads f [] in a world holding only rejected rows – the row SQL emits for a group all of whose rows the clause rejects. none is the aggregate with no clause, and the clause that keeps everything reads exactly as none does. The clause reads the group's input row and no outer column, as SQL's does.

                                                                                                    It reads regular columns only, and not by convention: SQL forbids an aggregate inside the FILTER of an aggregate, so a clause is a predicate of the plain value domain and not an atom over a token. Two consequences the metatheory lives off. Its truth at an occurrence is the same in every world, which is why no result here carries a hypothesis about what a clause reads – the worlds it cuts are the occurrence's own. And it is preserved by any transport that keeps the data columns, which is why the rewriting can carry a clause unchanged (Selection.castToAnnotatedTuple) with nothing to prove about it.

                                                                                                    Its ord is the ORDER BY inside the aggregates, which SQL writes as array_agg(x ORDER BY y): the group is read in that clause's order rather than in the domain's canonical one, and GroupOrder.unord – the default – says there is no clause. A symmetric aggregate reads the same value either way; it is for array_agg, string_agg and the order-dependent picks that the clause is the aggregate's own. The group's occurrence sequence, its existence factor and the rewritten world's reading all follow it (Having.havingGroupOrd, Relation.groupSeqOrd).

                                                                                                  • GammaScalar {T : Type} {c m n₂ lab : ℕ} {rd : Fin c → Bool} (ts : Tuple (TermIn T c m) n₂) (fs : Tuple (SeqAggFunc T) n₂) : AggQueryIn T c m (ColKind.allReg m) → (ord : optParam (GroupOrder T m) GroupOrder.unord) → AggQueryIn T c n₂ fun (x : Fin n₂) => ColKind.agg

                                                                                                    Aggregation without grouping: one output row whatever the input, its aggregates reading the whole of it.

                                                                                                    It is not Gamma with no keys. SQL forms a single group here that exists even over no row, so the row is annotated 𝟙 and carries no group-existence factor, and its tokens have the empty world among their worlds (AggValue.ofScalarGroup): an aggregate over an empty input has a value, and a comparison against it has to be given one.

                                                                                                  • GammaNest {T : Type} {c m n₁ : ℕ} {κ : Fin m → ColKind} {lab : ℕ} {rd : Fin c → Bool} (is : Tuple (Fin m) n₁) (his : ∀ (k : Fin n₁), κ (is k) ≠ ColKind.agg) (p : ProjColIn T c κ) (f : Multiset T → T) : AggQueryIn T c m κ → AggQueryIn T c (n₁ + 1) (Fin.append (fun (k : Fin n₁) => κ (is k)) fun (x : Fin 1) => ColKind.agg)

                                                                                                    Second-level aggregation (an aggregate column read as a value): group by the key columns is, none of which may be an aggregate column, and aggregate the projection column p over each group under f. Because p may read an aggregate column, the token this builds is nested: its occurrences are the group's rows, and what each carries is the aggregate value read there rather than a value (AggTok.nest).

                                                                                                    Its occurrences are a bag. They carry tokens, which ≼ does not order – that order is an order on plain tuples – so there is no sequence for an order-dependent f to read, and the outer aggregate is a function of the bag. An order-dependent outer aggregate has no reading of this kind and needs none: it goes through Explode, after which the column read is regular and the aggregation is an ordinary Gamma.

                                                                                                    Where p reads a regular column the nesting degenerates – each occurrence carries an inner value that reads nothing (GenValue.innerValue) – and the token is Gamma's own, read over the bag instead of over the ≼-sorted sequence.

                                                                                                    One output token and not n₂ of them: two nested values over one group read it as two families, which is the joint reading AggExpr gives an expression and not a product of two tokens.

                                                                                                  • ProvSum {T : Type} {c m n₁ : ℕ} {κ : Fin m → ColKind} (is : Tuple (Fin m) n₁) (his : ∀ (k : Fin n₁), κ (is k) ≠ ColKind.agg) (t : TermGIn T c κ) : AggQueryIn T c m κ → AggQueryIn T c (n₁ + 1) (Fin.append (fun (k : Fin n₁) => κ (is k)) fun (x : Fin 1) => ColKind.prov)

                                                                                                    Provenance aggregation: group by the key columns is (none of which may be a token column) and ⊕-sum the term t over each group into a single prov output column – the abstract counterpart of ProvSQL's ⊕-gate creation in rewritten plans.

                                                                                                  • Retag {T : Type} {c n : ℕ} {κ κ' : Fin n → ColKind} {l : List (String × ℕ)} (h : ∀ (k : Fin n), (κ k).base = (κ' k).base) : AggQueryIn T c n κ l → AggQueryIn T c n κ' l

                                                                                                    Retag value columns between the value-armed kinds (reg and prov): semantically the identity, it declares which value columns carry provenance – the typing act of casting a value column to ProvSQL's uuid type. Token columns cannot be retagged.

                                                                                                  • GammaTok {T : Type} {c m n₁ n₂ : ℕ} {κ : Fin m → ColKind} {lab : ℕ} {rd : Fin c → Bool} (is : Tuple (Fin m) n₁) (his : ∀ (k : Fin n₁), κ (is k) ≠ ColKind.agg) (ts : Tuple (TermIn T c m) n₂) (fs : Tuple (SeqAggFunc T) n₂) (a : TermGIn T c κ) : AggQueryIn T c m κ → (keep : optParam (Fin n₂ → Option (Selection T m)) fun (x : Fin n₂) => none) → AggQueryIn T c (n₁ + n₂ + 1) (Fin.append (Fin.append (fun (k : Fin n₁) => κ (is k)) fun (x : Fin n₂) => ColKind.agg) fun (x : Fin 1) => ColKind.prov)

                                                                                                    Token-building grouping (ProvSQL's provsql_agg): group by the key columns is, output the keys, one aggregate token per (term, aggregate) pair whose occurrence annotations are the values of the explicit annotation term a (in rewritten plans: the provenance column of the subquery), and a trailing prov column carrying the group-existence guard. Its faithful semantics lives in the rewritten world's evaluator; the generic evaluators give it total modeling semantics, and the world-faithfulness exclusions (noProvSum) rule it out of source queries.

                                                                                                    Its keep is the same clause as AggQueryIn.Gamma's, read the same way: it cuts what an aggregate reads and leaves the family and the guard whole, so a filtered aggregate's column is an aggregate expression (AggExpr.ofGroupWhen) and not an ordinary token. The rewriting carries the source's clause into it unchanged (Selection.castToAnnotatedTuple), a clause asking the rewriting for no rule of its own.

                                                                                                    A clause over the rewritten schema could also compare the provenance column, which the transport never produces and which the semantics permits in one form only: as an evaluation of the annotation in 𝔹 whose result does not enter an annotation, the way the displayed-value aggregate reads the rows whose token holds under hTop. Anything else would be evaluating an annotation while building one.

                                                                                                  • Win {T : Type} {c n m p : ℕ} {κ : Fin n → ColKind} {lab : ℕ} {rd : Fin c → Bool} (P : Tuple (Fin n) m) (O : Tuple (Fin n) p) (o : OrderSpec p) (w : ValueFrame T p) {hsql : ValueFrame.IsSQL o w} (t : TermIn T c n) (f : SeqAggFunc T) : AggQueryIn T c n κ → WinReadsReg κ P O t → (dist : optParam Bool false) → (keep : optParam (Option (Selection T n)) none) → AggQueryIn T c (n + 1) (Fin.snoc κ ColKind.agg)

                                                                                                    The window operator. Every occurrence of the input keeps its row and its annotation and gains one column: the aggregate of t under f over that occurrence's frame, given by the partition columns P, the order columns O, the ORDER BY clause o and a frame w determined by values. The clause does two things SQL asks of it and the domain's order cannot: it bounds a RANGE or GROUPS frame, and it fixes the order the frame is read in, which is what an aggregate that is not symmetric depends on.

                                                                                                    The frame is one of SQL's under the clause o (hsql, ValueFrame.IsSQL): a frame clause reads its bounds in the window's own ORDER BY, and the wider language of FrameCond, which may compare order columns each under a clause of its own, names frames no frame clause gives.

                                                                                                    It removes no row, merges none and changes no annotation, so it creates no group and produces no group-existence factor. Which occurrence a row is matters – two occurrences carrying the same row may have different frames, which is what EXCLUDE CURRENT ROW asks for – and the convention in which a row reads its token is decided per row, by whether the row is in its own frame (ValueFrame.token).

                                                                                                    dist says whether the aggregate reads the frame's distinct values: one occurrence per class of equal values, carrying the ⊕ of the class's members and read in the order the domain gives their values (AggValue.mergeByValue), which no reading of the unmerged token recovers, so the operator has to carry it. Over plain relations it is SeqAggFunc.distinct, and the order being a function of the values is what makes the reading world by world sound with no condition on the aggregate (AggValue.specialize_mergeByValue). It defaults to false, so a window written without it means what it meant.

                                                                                                    Its input need not be all-regular, which is what a second window of one SELECT needs: rank() OVER (…), avg(x) OVER (…) is two windows, the second over a relation that already holds the first one's aggregate column. Such a column is carried through unchanged and read by nothing – WinReadsReg asks the partition, the order and the term to read regular columns, and ColKind.readTuple keeps an aggregate column out of the determinized peer order as well. Both halves are needed: an aggregate column can order two peers one way in one world and the other way in the next, so a window reading one would not commute with the possible worlds. Ordering or partitioning by an aggregate reads it as a key, through AggQueryIn.Explode.

                                                                                                  • WinExpr {T : Type} {c n m p q lab : ℕ} {rd : Fin c → Bool} (P : Tuple (Fin n) m) (O : Tuple (Fin n) p) (o : OrderSpec p) (ws : Fin q → ValueFrame T p) {hsql : ∀ (l : Fin q), ValueFrame.IsSQL o (ws l)} (ts : Fin q → TermIn T c n) (fs : Fin q → SeqAggFunc T) (g : (Fin q → T) → T) : AggQueryIn T c n (ColKind.allReg n) → (keeps : optParam (Fin q → Option (Selection T n)) fun (x : Fin q) => none) → AggQueryIn T c (n + 1) (Fin.snoc (ColKind.allReg n) ColKind.agg)

                                                                                                    A window over several frames of one partition, whose column is an aggregate expression and not an aggregate: leaf l aggregates ts l with fs l over the frame ws l, and g combines the leaves' values. SQL's distribution functions are this operator – (r-1)/(N-1) for percent_rank, c/N for cume_dist, the bucket arithmetic for ntile – each reading two frames of one partition.

                                                                                                    It reads the union of its frames as one family and records per leaf which of those occurrences that leaf reads (ValueFrame.exprOf). The two families are nested – w_≺ inside the partition – so a reading that cannot tell which occurrences the two share invents worlds: a rank of three beside a count of one. Everything is indexed by occurrence, so an EXCLUDE CURRENT ROW frame is as exact here as a single-frame window's. Each frame is one of SQL's under the clause o (hsql), as a single-frame window's is.

                                                                                                    Why this is an operator and not a projection, here. It is a primitive of this syntax and not of the semantics. An aggregate value read as ⟨f, t, U⟩, carrying the occurrence sequence itself, makes a projection forming a term over two window columns denote the right aggregate expression over U₁ ∪ U₂ already, with nothing to reconstruct. AggValue keeps a value per occurrence instead of U (the term is applied when the token is built), so two finished columns can no longer be related, and the sharing has to be recorded where it is still known. AggExpr.occs does record it – the value each leaf reads at each occurrence – but only for a leaf set fixed when the family is built, which is what an operator has and a projection does not.

                                                                                                    Like Win it removes no row, merges none and changes no annotation, so it creates no group and leaves nothing pending. It is the one operator of the syntax that builds a non-tok column, which is why AggQueryIn.evaluate_ordinaryTokens is conditional on noWinExpr.

                                                                                                    Its input is all-regular, where Win's need not be, and that is a limit of the representation rather than of the semantics. A window over one frame carries an aggregate column of its input through unchanged, because its token is a function of the relation and of the row alone (ValueFrame.tokenOf) and needs no indexing; here the column is a function of the occurrence, which is what keeps EXCLUDE CURRENT ROW exact, and an occurrence is a position in a listing of the rows. A listing of a bag has to be independent of the listing it is computed from, so it is taken in the domain's order (OccFam.ofSorted) – and rows holding aggregate values have no order to be listed by, a token carrying functions. A family indexed by occurrences as primitive objects, in the manner of NestedValue.World, would carry such a column with nothing further to prove: nothing here fails world by world, the reading a window takes of its input being the same in every world either way (ColKind.readTuple).

                                                                                                  Instances For
                                                                                                    Dependency graph
                                                                                                    @[reducible, inline]
                                                                                                    abbrev AggQuery (T : Type) (n : ℕ) (κ : Fin n → ColKind) :

                                                                                                    A closed query: one that reads no outer column.

                                                                                                    Equations
                                                                                                    Instances For
                                                                                                      Dependency graph
                                                                                                      def AggQueryIn.castKind {T : Type} {c n : ℕ} {κ κ' : Fin n → ColKind} {l : List (String × ℕ)} (h : κ = κ') :
                                                                                                      AggQueryIn T c n κ l → AggQueryIn T c n κ' l

                                                                                                      Transport a query along an equality of kind vectors (kind vectors arising from projections are rarely definitionally all-regular).

                                                                                                      Equations
                                                                                                      Instances For
                                                                                                        Dependency graph

                                                                                                        The general evaluator #

                                                                                                        def GenRow.plainTuple {T K : Type} {n : ℕ} (u : Tuple (GenValue T K) n) :
                                                                                                        Tuple T n

                                                                                                        The regular-value reading of a lifted tuple (token columns collapse; on the all-regular rows fed to Dedup, Diff and Gamma no token occurs).

                                                                                                        Equations
                                                                                                        Instances For
                                                                                                          Dependency graph
                                                                                                          def GenRow.toAnnotated {T K : Type} [CommSemiringWithMonus K] {n : ℕ} (r : GenRow T K n) :

                                                                                                          Finalize a general row into an annotated tuple: collapse the tuple to its regular reading and cash the pending group factors.

                                                                                                          Equations
                                                                                                          Instances For
                                                                                                            Dependency graph
                                                                                                            def ColKind.readTuple {T : Type} [ValueType T] {n : ℕ} (κ : Fin n → ColKind) (u : Tuple T n) :
                                                                                                            Tuple T n

                                                                                                            What a window reads of a plain row: its regular columns, and a constant where the kinds put an aggregate column. Nothing of an aggregate column is read – not even to break a tie in the ORDER BY, which is why the determinized peer order is the same in every world (WinReadsReg says why that is what a window must do). On all-regular columns it is the row itself.

                                                                                                            Equations
                                                                                                            Instances For
                                                                                                              Dependency graph
                                                                                                              def GenRow.readTuple {T : Type} [ValueType T] {K : Type} {n : ℕ} (κ : Fin n → ColKind) (u : Tuple (GenValue T K) n) :
                                                                                                              Tuple T n

                                                                                                              What a window reads of a general row: ColKind.readTuple of its columns, which is their collapse wherever a regular column sits.

                                                                                                              Equations
                                                                                                              Instances For
                                                                                                                Dependency graph
                                                                                                                def GenRow.readAnnotated {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] {n : ℕ} (κ : Fin n → ColKind) (r : GenRow T K n) :

                                                                                                                The occurrence a window's input relation gives a row of its input: what the window reads of the row, carrying the row's annotation.

                                                                                                                Equations
                                                                                                                Instances For
                                                                                                                  Dependency graph
                                                                                                                  def List.copyNums {α : Type} (eq : α → α → Bool) :
                                                                                                                  List α → List α → List ℕ

                                                                                                                  The copy number of each element of a list: how many equal elements come before it, seen holding those already passed.

                                                                                                                  Equations
                                                                                                                  Instances For
                                                                                                                    Dependency graph
                                                                                                                    def ValueFrame.frameOids {T : Type} [ValueType T] {K : Type} [HasAltLinearOrder K] {n m p : ℕ} (lab : ℕ) (ck : List (T ⊕ FamId T)) (P : Tuple (Fin n) m) (O : Tuple (Fin n) p) (o : OrderSpec p) (w : ValueFrame T p) (X : AnnotatedRelation T K n) (x : AnnotatedTuple T K n) :

                                                                                                                    The identities of a window's occurrences: an occurrence of the frame of the row is numbered by the position, in the listing of its partition, of the first row equal to it, plus its copy number among the equal rows of the frame. So the frames of one partition give one occurrence one identity, and a frame holding a row holds the identity of its first copy. Two equal rows get one frame: under EXCLUDE CURRENT ROW the semantics gives each the frame without itself, which a frame computed from the row alone cannot.

                                                                                                                    Equations
                                                                                                                    • One or more equations did not get rendered due to their size.
                                                                                                                    Instances For
                                                                                                                      Dependency graph
                                                                                                                      def ValueFrame.windowGenRow {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [HasAltLinearOrder K] {c n m p : ℕ} (lab : ℕ) (ck : List (T ⊕ FamId T)) (κ : Fin n → ColKind) (P : Tuple (Fin n) m) (O : Tuple (Fin n) p) (o : OrderSpec p) (w : ValueFrame T p) (t : TermIn T c n) (f : SeqAggFunc T) (keep : Option (Selection T n)) (X : AnnotatedRelation T K n) (x : GenRow T K n) (γ : Fin c → T := fun (x : Fin c) => 0) (dist : Bool := false) :
                                                                                                                      GenRow T K (n + 1)

                                                                                                                      The row a window gives a row of its input: the row itself, one column longer, carrying the token the relation gives it – or, under a FILTER clause, the aggregate expression over the whole frame whose leaf reads what the clause keeps.

                                                                                                                      Its own columns go through untouched, aggregate columns included: a window reads regular columns and rewrites none of them. So do its annotation and its pending factors, a window creating no group.

                                                                                                                      Equations
                                                                                                                      • One or more equations did not get rendered due to their size.
                                                                                                                      Instances For
                                                                                                                        Dependency graph
                                                                                                                        def ValueFrame.exprOids {T : Type} [ValueType T] {K : Type} [HasAltLinearOrder K] {n m p q : ℕ} (lab : ℕ) (ck : List (T ⊕ FamId T)) (P : Tuple (Fin n) m) (O : Tuple (Fin n) p) (o : OrderSpec p) (ws : Fin q → ValueFrame T p) (r : OccFam (AnnotatedTuple T K n)) (i : Fin r.size) :

                                                                                                                        The identities of a multi-frame window's occurrences: an occurrence the expression of the row i reads is numbered by its index in the sorted input, which is how the expression indexes it. So the expressions of every row give one occurrence one identity.

                                                                                                                        Equations
                                                                                                                        Instances For
                                                                                                                          Dependency graph
                                                                                                                          def GenRow.ofAnnotated {T K : Type} {n : ℕ} (p : AnnotatedTuple T K n) :
                                                                                                                          GenRow T K n

                                                                                                                          Embed an annotated tuple as a general row (all-regular, nothing pending).

                                                                                                                          Equations
                                                                                                                          Instances For
                                                                                                                            Dependency graph
                                                                                                                            noncomputable def GenRow.alternativesAt {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] {n : ℕ} (r : GenRow T K n) (i : Fin n) :

                                                                                                                            The alternatives of an occurrence at one aggregate column: one row per value the column's aggregate value takes, the column made regular and the annotation multiplied by [a ≐ v] (AggValue.altProv). A column already regular has the occurrence itself as its only alternative. This is how an operator that compares keys reads an aggregate column.

                                                                                                                            Equations
                                                                                                                            • One or more equations did not get rendered due to their size.
                                                                                                                            Instances For
                                                                                                                              Dependency graph
                                                                                                                              def tokenLists {T K : Type} [CommSemiringWithMonus K] {n : ℕ} (u : Tuple (GenValue T K) n) :

                                                                                                                              The multiset of occurrence-annotation lists of the token columns of a tuple (used by projection to detect dropped groups).

                                                                                                                              Equations
                                                                                                                              Instances For
                                                                                                                                Dependency graph
                                                                                                                                def TermGIn.evalPlain {T : Type} [ValueType T] {n c : ℕ} {κ : Fin n → ColKind} (t : TermGIn T c κ) (u : Tuple T n) (γ : Fin c → T := fun (x : Fin c) => 0) :
                                                                                                                                T
                                                                                                                                Equations
                                                                                                                                Instances For
                                                                                                                                  Dependency graph
                                                                                                                                  def TermIn.toGen {T : Type} {c n : ℕ} :
                                                                                                                                  TermIn T c n → TermGIn T c (ColKind.allReg n)

                                                                                                                                  A term over regular columns read as a general term: the same term, the kind index witnessing that every column it reads is regular. It is what a projection needs to carry a term of the aggregation grammar, whose input is all-regular.

                                                                                                                                  Equations
                                                                                                                                  Instances For
                                                                                                                                    Dependency graph

                                                                                                                                    The gate-free fragment #

                                                                                                                                    The indicator gate TermGIn.chiGate is the one term constructor whose faithful reading needs the rewritten world: it produces a provenance value out of a comparison between regular values, which the generic evaluators – having no annotation to return – can only approximate by the junk constant. The cmpAgg gate escapes the same fate only because its kind constraint keeps it off the columns the plain semantics sees. The predicates below cut out the fragment where no indicator gate occurs, on which the rewritten world's evaluator is the plain semantics (AggQueryIn.evaluateRew_plain).

                                                                                                                                    def TermGIn.chiFree {n : ℕ} {T' : Type} {c : ℕ} {κ : Fin n → ColKind} :
                                                                                                                                    TermGIn T' c κ → Prop

                                                                                                                                    No indicator gate in a term.

                                                                                                                                    Equations
                                                                                                                                    Instances For
                                                                                                                                      Dependency graph
                                                                                                                                      def GenPredIn.chiFree {n : ℕ} {T' : Type} {c : ℕ} {κ : Fin n → ColKind} :
                                                                                                                                      GenPredIn T' c κ → Prop

                                                                                                                                      No indicator gate in a predicate.

                                                                                                                                      Equations
                                                                                                                                      Instances For
                                                                                                                                        Dependency graph
                                                                                                                                        def ProjColIn.chiFree {n : ℕ} {T' : Type} {c : ℕ} {κ : Fin n → ColKind} :
                                                                                                                                        ProjColIn T' c κ → Prop

                                                                                                                                        No indicator gate in a projection column.

                                                                                                                                        Equations
                                                                                                                                        Instances For
                                                                                                                                          Dependency graph

                                                                                                                                          The rounds of a recursion #

                                                                                                                                          Both recursions iterate a step on relations; neither needs the query syntax, so both are plain recursions on the round number with their own lemmas. muSum collects the rounds of Mu – their multiset sum – and muIter runs the fixpoint iteration of MuSet.

                                                                                                                                          What the semantics calls “some round is empty” is in force here as the hypothesis step 0 = 0: the sum ⨄_{i≥0} Mᵢ over all rounds is a relation only because an empty round is a fixpoint of the round function, which is what SQL's requirement that the recursive reference occur in the body buys. Nothing in this syntax enforces that, so it is asked for where it is used.

                                                                                                                                          def muSum {α : Type} (step : Multiset α → Multiset α) :
                                                                                                                                          ℕ → Multiset α → Multiset α

                                                                                                                                          The multiset sum of the first b + 1 iterates of step from M.

                                                                                                                                          Equations
                                                                                                                                          Instances For
                                                                                                                                            Dependency graph
                                                                                                                                            def muIter {α : Type} (step : Multiset α → Multiset α) :
                                                                                                                                            ℕ → Multiset α

                                                                                                                                            The b-th iterate of step from the empty relation.

                                                                                                                                            Equations
                                                                                                                                            Instances For
                                                                                                                                              Dependency graph

                                                                                                                                              What the recursions mean: the rounds settling #

                                                                                                                                              muSum and muIter run a given number of rounds, which is a tool and not the semantics: a recursion means the value its rounds settle at, and means nothing where they do not settle. MuSetSettles and MuSettles say when there is such a value, muFix and muSumFix are it, and the two transfer lemmas below are how a bounded computation witnesses it – reach a round that repeats, or an empty one, and the semantics is that value.

                                                                                                                                              def MuSetSettles {α : Type} (step : Multiset α → Multiset α) :

                                                                                                                                              A set recursion settles when some round equals the next. The rounds are then constant from there on, so the value is well defined.

                                                                                                                                              Equations
                                                                                                                                              Instances For
                                                                                                                                                Dependency graph
                                                                                                                                                def MuSettles {α : Type} (step : Multiset α → Multiset α) (M : Multiset α) :

                                                                                                                                                A duplicate-preserving recursion settles when some round past the first is empty, which is where SQL's own iteration stops.

                                                                                                                                                Equations
                                                                                                                                                Instances For
                                                                                                                                                  Dependency graph
                                                                                                                                                  noncomputable def muFixIdx {α : Type} (step : Multiset α → Multiset α) :

                                                                                                                                                  The first round at which a set recursion repeats; 0 where it never does (Nat.sInf_empty), which is junk and is what makes the total function below say nothing where the semantics says nothing.

                                                                                                                                                  Equations
                                                                                                                                                  Instances For
                                                                                                                                                    Dependency graph
                                                                                                                                                    noncomputable def muRounds {α : Type} (step : Multiset α → Multiset α) (M : Multiset α) :

                                                                                                                                                    The number of rounds a duplicate-preserving recursion sums: up to the first empty one, 0 where there is none.

                                                                                                                                                    Equations
                                                                                                                                                    Instances For
                                                                                                                                                      Dependency graph
                                                                                                                                                      noncomputable def muFix {α : Type} (step : Multiset α → Multiset α) :

                                                                                                                                                      The value a set recursion settles at – X_j for the first j with X_{j+1} = X_j. Junk (∅) where the rounds never settle, which no statement about it may read: a result about a set recursion carries MuSetSettles as a hypothesis.

                                                                                                                                                      Equations
                                                                                                                                                      Instances For
                                                                                                                                                        Dependency graph
                                                                                                                                                        noncomputable def muSumFix {α : Type} (step : Multiset α → Multiset α) (M : Multiset α) :

                                                                                                                                                        The value a duplicate-preserving recursion settles at – the sum of the rounds up to the first empty one. Junk where no round is empty.

                                                                                                                                                        Equations
                                                                                                                                                        Instances For
                                                                                                                                                          Dependency graph
                                                                                                                                                          theorem muFix_map {α β : Type} {h : Multiset α → Multiset β} (h0 : h 0 = 0) {step : Multiset α → Multiset α} {stepP : Multiset β → Multiset β} (hstep : ∀ (X : Multiset α), h (step X) = stepP (h X)) (hs : MuSetSettles step) :
                                                                                                                                                          h (muFix step) = muFix stepP

                                                                                                                                                          A map commutes with the value a set recursion settles at, where it settles: the images of the rounds are the rounds of the image, so a fixpoint maps to a fixpoint, and the image settles no later. This is what replaces muIter_map once the round count is not part of the query.

                                                                                                                                                          Dependency graph
                                                                                                                                                          theorem muSumFix_map {α β : Type} {h : Multiset α → Multiset β} (h0 : h 0 = 0) (hadd : ∀ (x y : Multiset α), h (x + y) = h x + h y) {step : Multiset α → Multiset α} {stepP : Multiset β → Multiset β} (hstep : ∀ (X : Multiset α), h (step X) = stepP (h X)) (hz : step 0 = 0) {M : Multiset α} (hm : MuSettles step M) :
                                                                                                                                                          h (muSumFix step M) = muSumFix stepP (h M)

                                                                                                                                                          A map commutes with the value a duplicate-preserving recursion settles at, where it settles and an empty round stays empty.

                                                                                                                                                          Dependency graph
                                                                                                                                                          theorem muSumFix_congr {α : Type} {step step' : Multiset α → Multiset α} (h : ∀ (X : Multiset α), step X = step' X) {M M' : Multiset α} (hM : M = M') :
                                                                                                                                                          muSumFix step M = muSumFix step' M'

                                                                                                                                                          Steps that agree have the same settling value, for a duplicate-preserving recursion.

                                                                                                                                                          Dependency graph
                                                                                                                                                          theorem muFix_congr {α : Type} {step step' : Multiset α → Multiset α} (h : ∀ (X : Multiset α), step X = step' X) :
                                                                                                                                                          muFix step = muFix step'

                                                                                                                                                          Steps that agree have the same fixpoint, for a duplicate-eliminating recursion.

                                                                                                                                                          Dependency graph

                                                                                                                                                          Duplicate elimination on an annotated relation: one slot per tuple, annotated by the ⊕ of its copies – what Dedup computes, named for the rounds of MuSet.

                                                                                                                                                          Equations
                                                                                                                                                          Instances For
                                                                                                                                                            Dependency graph
                                                                                                                                                            def GenValue.kindOf {T K : Type} :

                                                                                                                                                            The kind of a lifted value.

                                                                                                                                                            Equations
                                                                                                                                                            Instances For
                                                                                                                                                              Dependency graph
                                                                                                                                                              def GenRow.Conforms {T K : Type} {n : ℕ} (κ : Fin n → ColKind) (u : Tuple (GenValue T K) n) :

                                                                                                                                                              A row has the kinds κ: a regular value where κ says regular or provenance, a token where it says aggregate.

                                                                                                                                                              Equations
                                                                                                                                                              Instances For
                                                                                                                                                                Dependency graph
                                                                                                                                                                @[instance_reducible]
                                                                                                                                                                instance instDecidableConforms {T K : Type} {n : ℕ} (κ : Fin n → ColKind) (u : Tuple (GenValue T K) n) :
                                                                                                                                                                Equations
                                                                                                                                                                Dependency graph
                                                                                                                                                                structure EvalEnv (T K : Type) :

                                                                                                                                                                What the annotated evaluator reads besides the database and the plain context: the rounds a recursion binds to its name, as general rows – a round may carry aggregate columns, which a database cannot hold – and the context with its aggregate values, which an apply extends with the row of its left side and the leaf AggQueryIn.Param reads. A closed query reads neither.

                                                                                                                                                                Instances For
                                                                                                                                                                  Dependency graph
                                                                                                                                                                  def EvalEnv.assignHole {T K : Type} (E : EvalEnv T K) (s : String) {n : ℕ} (X : Multiset (GenRow T K n)) :

                                                                                                                                                                  Binding a recursive name to a round.

                                                                                                                                                                  Equations
                                                                                                                                                                  Instances For
                                                                                                                                                                    Dependency graph
                                                                                                                                                                    def EvalEnv.ctxAt {T K : Type} (E : EvalEnv T K) (c : ℕ) (γ : Fin c → T) :
                                                                                                                                                                    Tuple (GenValue T K) c

                                                                                                                                                                    The context of arity c, aggregate values included: the one the environment holds when it has that arity, and the plain context read as regular values otherwise – which is what a context with no aggregate value is.

                                                                                                                                                                    Equations
                                                                                                                                                                    Instances For
                                                                                                                                                                      Dependency graph
                                                                                                                                                                      def EvalEnv.withCtx {T K : Type} (E : EvalEnv T K) {c : ℕ} (u : Tuple (GenValue T K) c) :

                                                                                                                                                                      Setting the context.

                                                                                                                                                                      Equations
                                                                                                                                                                      Instances For
                                                                                                                                                                        Dependency graph
                                                                                                                                                                        def EvalEnv.paramRows {T K : Type} [CommSemiringWithMonus K] (E : EvalEnv T K) {c m : ℕ} (γ : Fin c → T) (pv : Fin m → T ⊕ Fin c) (ρ : Fin m → ColKind) :

                                                                                                                                                                        What the leaf AggQueryIn.Param pv ρ reads: the row whose column k is the parameter or constant pv k, when it has the kinds ρ, annotated 𝟙.

                                                                                                                                                                        Equations
                                                                                                                                                                        • One or more equations did not get rendered due to their size.
                                                                                                                                                                        Instances For
                                                                                                                                                                          Dependency graph
                                                                                                                                                                          def EvalEnv.RowsSat {T K : Type} (Q : GenValue T K → Prop) (E : EvalEnv T K) :

                                                                                                                                                                          Every value the environment holds has the property Q: in the rows of every round it binds and in its context.

                                                                                                                                                                          Equations
                                                                                                                                                                          Instances For
                                                                                                                                                                            Dependency graph

                                                                                                                                                                            The parameters an operator reads #

                                                                                                                                                                            An occurrence belongs to the operator that produces it and to the values of the apply parameters that operator reads: an operator evaluated on the same inputs produces the same occurrences, and one reading different parameter values produces different ones. So the family an aggregating operator stamps on its values records those values, and these functions say which parameters (outer columns) a term, a predicate or a whole subquery reads.

                                                                                                                                                                            def TermIn.readsOuter {T : Type} {c n : ℕ} (k : Fin c) :
                                                                                                                                                                            TermIn T c n → Bool

                                                                                                                                                                            Does the term read the outer column k?

                                                                                                                                                                            Equations
                                                                                                                                                                            Instances For
                                                                                                                                                                              Dependency graph
                                                                                                                                                                              Dependency graph
                                                                                                                                                                              def GenPredIn.readsOuter {T : Type} {c n : ℕ} {κ : Fin n → ColKind} (k : Fin c) :
                                                                                                                                                                              GenPredIn T c κ → Bool

                                                                                                                                                                              Does the predicate read the outer column k?

                                                                                                                                                                              Equations
                                                                                                                                                                              Instances For
                                                                                                                                                                                Dependency graph
                                                                                                                                                                                def ProjColIn.readsOuter {T : Type} {c n : ℕ} {κ : Fin n → ColKind} (k : Fin c) :
                                                                                                                                                                                ProjColIn T c κ → Bool

                                                                                                                                                                                Does the projection column read the outer column k?

                                                                                                                                                                                Equations
                                                                                                                                                                                Instances For
                                                                                                                                                                                  Dependency graph
                                                                                                                                                                                  def AggQueryIn.readsOuter {T : Type} {c n : ℕ} {κ : Fin n → ColKind} {l : List (String × ℕ)} :
                                                                                                                                                                                  AggQueryIn T c n κ l → Fin c → Bool

                                                                                                                                                                                  Does the query read the outer column k? An apply's right side reads its own parameters after the left row's columns, and an aggregating operator reads the parameters it records, its stamps holding their values.

                                                                                                                                                                                  Equations
                                                                                                                                                                                  Instances For
                                                                                                                                                                                    Dependency graph
                                                                                                                                                                                    def ctxKey {c : ℕ} {α : Type} (r : Fin c → Bool) (γ : Fin c → α) :
                                                                                                                                                                                    List α

                                                                                                                                                                                    The values of the parameters an operator reads, in the order of the context: what a family records besides the operator's label and the key of the group.

                                                                                                                                                                                    Equations
                                                                                                                                                                                    Instances For
                                                                                                                                                                                      Dependency graph
                                                                                                                                                                                      def GenValue.paramId {T K : Type} :
                                                                                                                                                                                      GenValue T K → T ⊕ FamId T

                                                                                                                                                                                      How a family records a parameter: a regular one by its value, an aggregate one by its identity – the aggregate value itself, not the value it takes in a world.

                                                                                                                                                                                      Equations
                                                                                                                                                                                      Instances For
                                                                                                                                                                                        Dependency graph
                                                                                                                                                                                        def EvalEnv.paramKey {T K : Type} (E : EvalEnv T K) {c : ℕ} (r : Fin c → Bool) (γ : Fin c → T) :
                                                                                                                                                                                        List (T ⊕ FamId T)

                                                                                                                                                                                        The parameters of the context E that the read set r records.

                                                                                                                                                                                        Equations
                                                                                                                                                                                        Instances For
                                                                                                                                                                                          Dependency graph
                                                                                                                                                                                          def nestOfVals {T K : Type} (f : Multiset T → T) (φ : FamId T) (V : Multiset (GenValue T K × K)) :

                                                                                                                                                                                          The nested value of a bag of lifted values, each with its annotation: one occurrence per element, carrying what the value reads at the storey the bag needs – one above the deepest nested value it holds (GenValue.innerAt).

                                                                                                                                                                                          Equations
                                                                                                                                                                                          • One or more equations did not get rendered due to their size.
                                                                                                                                                                                          Instances For
                                                                                                                                                                                            Dependency graph
                                                                                                                                                                                            def nestOfGroup {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] {c m : ℕ} {κ : Fin m → ColKind} (p : ProjColIn T c κ) (γ : Fin c → T) (f : Multiset T → T) (φ : FamId T) (grp : Multiset (GenRow T K m)) :

                                                                                                                                                                                            The nested value a second-level aggregation builds over a group: one occurrence per row, carrying what the column reads there, and the row's annotation.

                                                                                                                                                                                            Equations
                                                                                                                                                                                            Instances For
                                                                                                                                                                                              Dependency graph
                                                                                                                                                                                              noncomputable def AggQueryIn.evaluate {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {c n : ℕ} {κ : Fin n → ColKind} {l : List (String × ℕ)} (q : AggQueryIn T c n κ l) (d : AnnotatedDatabase T K) (γ : Fin c → T := fun (x : Fin c) => 0) (E : EvalEnv T K := { }) :

                                                                                                                                                                                              The general annotated evaluator. All operators preserve the factored-annotation discipline described in the module docstring.

                                                                                                                                                                                              Equations
                                                                                                                                                                                              Instances For
                                                                                                                                                                                                Dependency graph
                                                                                                                                                                                                noncomputable def AggQueryIn.evaluateAnnotated {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {c n : ℕ} {κ : Fin n → ColKind} {l : List (String × ℕ)} (q : AggQueryIn T c n κ l) (d : AnnotatedDatabase T K) (γ : Fin c → T := fun (x : Fin c) => 0) (E : EvalEnv T K := { }) :

                                                                                                                                                                                                The final annotated relation computed by a general query: evaluate, then finalize every row.

                                                                                                                                                                                                Equations
                                                                                                                                                                                                Instances For
                                                                                                                                                                                                  Dependency graph

                                                                                                                                                                                                  What the recursions compute, and when the bound drops out #

                                                                                                                                                                                                  noncomputable def AggQueryIn.muStep {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {c n : ℕ} {κ : Fin n → ColKind} (s : String) (q₁ : AggQueryIn T c n κ [(s, n)]) (d : AnnotatedDatabase T K) (γ : Fin c → T := fun (x : Fin c) => 0) (E : EvalEnv T K := { }) :
                                                                                                                                                                                                  Multiset (GenRow T K n) → Multiset (GenRow T K n)

                                                                                                                                                                                                  The round function of Mu: the body read with the name bound to the previous round. A round is a bag of general rows, aggregate columns included.

                                                                                                                                                                                                  Equations
                                                                                                                                                                                                  Instances For
                                                                                                                                                                                                    Dependency graph
                                                                                                                                                                                                    noncomputable def AggQueryIn.muSetStep {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {c n : ℕ} (s : String) (q₀ : AggQueryIn T c n (ColKind.allReg n)) (q₁ : AggQueryIn T c n (ColKind.allReg n) [(s, n)]) (d : AnnotatedDatabase T K) (γ : Fin c → T := fun (x : Fin c) => 0) (E : EvalEnv T K := { }) :

                                                                                                                                                                                                    The round function of MuSet: ε(q₀ ⊎ q₁) read with the name bound to the previous round.

                                                                                                                                                                                                    Equations
                                                                                                                                                                                                    Instances For
                                                                                                                                                                                                      Dependency graph
                                                                                                                                                                                                      def ValueFrame.windowRow {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [HasAltLinearOrder K] {c n m p : ℕ} (P : Tuple (Fin n) m) (O : Tuple (Fin n) p) (o : OrderSpec p) (w : ValueFrame T p) (t : TermIn T c n) (f : SeqAggFunc T) (X : AnnotatedRelation T K n) (x : AnnotatedTuple T K n) (γ : Fin c → T := fun (x : Fin c) => 0) (dist : Bool := false) :
                                                                                                                                                                                                      GenRow T K (n + 1)

                                                                                                                                                                                                      The row a window gives a row of its input relation: the row itself, one column longer, with the token the relation gives it, its annotation kept and nothing pending – a window creates no group.

                                                                                                                                                                                                      Equations
                                                                                                                                                                                                      • One or more equations did not get rendered due to their size.
                                                                                                                                                                                                      Instances For
                                                                                                                                                                                                        Dependency graph
                                                                                                                                                                                                        theorem AggQueryIn.evaluate_Win_eq {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {lab c n m p : ℕ} {rd : Fin c → Bool} {κ : Fin n → ColKind} (P : Tuple (Fin n) m) (O : Tuple (Fin n) p) (o : OrderSpec p) (w : ValueFrame T p) {hsql : ValueFrame.IsSQL o w} (t : TermIn T c n) (f : SeqAggFunc T) (dist : Bool) (q : AggQueryIn T c n κ) (hrr : WinReadsReg κ P O t) (d : AnnotatedDatabase T K) {γ : Fin c → T} {E : EvalEnv T K} :
                                                                                                                                                                                                        (Win P O o w t f q hrr dist).evaluate d γ E = Multiset.map (fun (x : GenRow T K n) => ValueFrame.windowGenRow lab (E.paramKey rd γ) κ P O o w t f none (Multiset.map (GenRow.readAnnotated κ) (q.evaluate d γ E)) x γ dist) (q.evaluate d γ E)

                                                                                                                                                                                                        The Win case of the evaluator, read off the relation. The output is the input relation mapped row by row, each row gaining the token its relation gives it. This is the form every theorem about the operator uses; that it is legitimate – that an occurrence's token is determined by the relation even though its frame is not determined by its row – is ValueFrame.tokenOf.

                                                                                                                                                                                                        Dependency graph

                                                                                                                                                                                                        The plain evaluator #

                                                                                                                                                                                                        The classical (per-instance) semantics of a general query: aggregate columns hold the computed aggregate values, and every selection filters classically – including aggregate comparisons, evaluated on the computed values. This is the semantics the data-part adequacy connects to the annotated evaluator through AggValue.collapse (the annotated side keeps classically-failing rows with annotation 𝟘, exactly as ProvSQL emits them, so adequacy is stated on the query stripped of its aggregate selections and differences, stripAgg).

                                                                                                                                                                                                        def GenPredIn.evalPlain3 {T : Type} [ValueType T] {n : ℕ} {κ : Fin n → ColKind} {c : ℕ} (φ : GenPredIn T c κ) (u : Tuple T n) (γ : Fin c → T := fun (x : Fin c) => 0) :

                                                                                                                                                                                                        Classical truth of a predicate on a regular tuple: aggregate atoms compare the computed aggregate value of their column.

                                                                                                                                                                                                        Equations
                                                                                                                                                                                                        Instances For
                                                                                                                                                                                                          Dependency graph
                                                                                                                                                                                                          def GenPredIn.holdsPlain {T : Type} [ValueType T] {n : ℕ} {κ : Fin n → ColKind} {c : ℕ} (φ : GenPredIn T c κ) (u : Tuple T n) (γ : Fin c → T := fun (x : Fin c) => 0) :

                                                                                                                                                                                                          The rows a selection keeps classically: those on which the predicate is true.

                                                                                                                                                                                                          Equations
                                                                                                                                                                                                          Instances For
                                                                                                                                                                                                            Dependency graph
                                                                                                                                                                                                            def GenPredIn.decHoldsPlain {T : Type} [ValueType T] {n : ℕ} {κ : Fin n → ColKind} {c : ℕ} (φ : GenPredIn T c κ) (u : Tuple T n) (γ : Fin c → T := fun (x : Fin c) => 0) :

                                                                                                                                                                                                            Structural decidability of holdsPlain.

                                                                                                                                                                                                            Equations
                                                                                                                                                                                                            Instances For
                                                                                                                                                                                                              Dependency graph
                                                                                                                                                                                                              @[instance_reducible]
                                                                                                                                                                                                              instance GenPredIn.instDecidableHoldsPlain {T : Type} [ValueType T] {n : ℕ} {κ : Fin n → ColKind} {c : ℕ} (φ : GenPredIn T c κ) (γ : Fin c → T) (u : Tuple T n) :
                                                                                                                                                                                                              Equations
                                                                                                                                                                                                              Dependency graph
                                                                                                                                                                                                              def ProjColIn.evalPlain {T : Type} [ValueType T] {n c : ℕ} {κ : Fin n → ColKind} (p : ProjColIn T c κ) (u : Tuple T n) (γ : Fin c → T := fun (x : Fin c) => 0) :
                                                                                                                                                                                                              T

                                                                                                                                                                                                              Plain evaluation of a projection column.

                                                                                                                                                                                                              Equations
                                                                                                                                                                                                              Instances For
                                                                                                                                                                                                                Dependency graph
                                                                                                                                                                                                                def ValueFrame.windowValue {T : Type} [ValueType T] {c n m p : ℕ} (P : Tuple (Fin n) m) (O : Tuple (Fin n) p) (o : OrderSpec p) (w : ValueFrame T p) (t : TermIn T c n) (f : SeqAggFunc T) (R : Relation T n) (u : Tuple T n) (γ : Fin c → T := fun (x : Fin c) => 0) :
                                                                                                                                                                                                                T

                                                                                                                                                                                                                The value a window's added column takes on a row of a plain relation: the aggregate of the term over that row's frame, read off the relation.

                                                                                                                                                                                                                Equations
                                                                                                                                                                                                                Instances For
                                                                                                                                                                                                                  Dependency graph
                                                                                                                                                                                                                  def ValueFrame.windowValueWhen {T : Type} [ValueType T] {c n m p : ℕ} (P : Tuple (Fin n) m) (O : Tuple (Fin n) p) (o : OrderSpec p) (w : ValueFrame T p) (t : TermIn T c n) (f : SeqAggFunc T) (keep : Tuple T n → Bool) (R : Relation T n) (u : Tuple T n) (γ : Fin c → T := fun (x : Fin c) => 0) :
                                                                                                                                                                                                                  T

                                                                                                                                                                                                                  The value a window's added column takes under a FILTER clause: the aggregate over the rows of the frame the clause keeps.

                                                                                                                                                                                                                  Equations
                                                                                                                                                                                                                  Instances For
                                                                                                                                                                                                                    Dependency graph
                                                                                                                                                                                                                    def ValueFrame.windowValueOpt {T : Type} [ValueType T] {c n m p : ℕ} (P : Tuple (Fin n) m) (O : Tuple (Fin n) p) (o : OrderSpec p) (w : ValueFrame T p) (t : TermIn T c n) (f : SeqAggFunc T) (keep : Option (Selection T n)) (R : Relation T n) (u : Tuple T n) (γ : Fin c → T := fun (x : Fin c) => 0) :
                                                                                                                                                                                                                    T

                                                                                                                                                                                                                    The value one leaf of a multi-frame window takes: the aggregate over its frame, over the part its own FILTER clause keeps where it carries one.

                                                                                                                                                                                                                    Equations
                                                                                                                                                                                                                    Instances For
                                                                                                                                                                                                                      Dependency graph
                                                                                                                                                                                                                      noncomputable def AggQueryIn.evaluatePlain {T : Type} [ValueType T] {c n : ℕ} {κ : Fin n → ColKind} {l : List (String × ℕ)} :
                                                                                                                                                                                                                      AggQueryIn T c n κ l → Database T → (γ : optParam (Fin c → T) fun (x : Fin c) => 0) → Relation T n

                                                                                                                                                                                                                      The plain evaluator: standard multiset semantics, with Gamma computing the aggregate of each group's full occurrence sequence (in the canonical ≼ order of Relation.groupSeq) and every selection filtering classically. Diff is the all-or-nothing difference of Query.evaluate.

                                                                                                                                                                                                                      Equations
                                                                                                                                                                                                                      Instances For
                                                                                                                                                                                                                        Dependency graph
                                                                                                                                                                                                                        theorem ValueFrame.windowValue_of_perm {T : Type} [ValueType T] {c n m p : ℕ} (P : Tuple (Fin n) m) (O : Tuple (Fin n) p) (o : OrderSpec p) (w : ValueFrame T p) (t : TermIn T c n) {f : SeqAggFunc T} (hf : f.Symmetric) (R : Relation T n) (u : Tuple T n) (L : List (Tuple T n)) {γ : Fin c → T} (hL : ↑L = frameOf id P O w R u) :
                                                                                                                                                                                                                        f (List.map (fun (x : Tuple T n) => t.eval x γ) L) = windowValue P O o w t f R u γ

                                                                                                                                                                                                                        Where the aggregate is symmetric the sequence a frame is read in does not matter: any listing of the frame gives the value the window gives, so the canonical order the library sorts by is as good as the order an ORDER BY asks for. It is for an aggregate that is not symmetric – PICKFIRST – that the two have to be the same order.

                                                                                                                                                                                                                        Dependency graph
                                                                                                                                                                                                                        theorem AggQueryIn.evaluatePlain_Win_eq {T : Type} [ValueType T] {lab c n m p : ℕ} {rd : Fin c → Bool} {κ : Fin n → ColKind} (P : Tuple (Fin n) m) (O : Tuple (Fin n) p) (o : OrderSpec p) (w : ValueFrame T p) {hsql : ValueFrame.IsSQL o w} (t : TermIn T c n) (f : SeqAggFunc T) (dist : Bool) (q : AggQueryIn T c n κ) (hrr : WinReadsReg κ P O t) (d : Database T) {γ : Fin c → T} :
                                                                                                                                                                                                                        (Win P O o w t f q hrr dist).evaluatePlain d γ = Multiset.map (fun (u : Tuple T n) => Fin.snoc u (ValueFrame.windowValue P O o w t (if dist = true then f.distinct else f) (Multiset.map (ColKind.readTuple κ) (q.evaluatePlain d γ)) (ColKind.readTuple κ u) γ)) (q.evaluatePlain d γ)

                                                                                                                                                                                                                        The Win case of the plain evaluator, read off the relation.

                                                                                                                                                                                                                        Dependency graph
                                                                                                                                                                                                                        def ValueFrame.windowRowWhen {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [HasAltLinearOrder K] {c n m p : ℕ} (P : Tuple (Fin n) m) (O : Tuple (Fin n) p) (o : OrderSpec p) (w : ValueFrame T p) (t : TermIn T c n) (f : SeqAggFunc T) (keep : Tuple T n → Bool) (X : AnnotatedRelation T K n) (x : AnnotatedTuple T K n) (γ : Fin c → T := fun (x : Fin c) => 0) (dist : Bool := false) :
                                                                                                                                                                                                                        GenRow T K (n + 1)

                                                                                                                                                                                                                        The row a window gives a row of its input relation under a FILTER clause: as ValueFrame.windowRow, with the clause's column – an aggregate expression over the whole frame, the clause cutting what its leaf reads (ValueFrame.exprWhenOf).

                                                                                                                                                                                                                        Equations
                                                                                                                                                                                                                        • One or more equations did not get rendered due to their size.
                                                                                                                                                                                                                        Instances For
                                                                                                                                                                                                                          Dependency graph
                                                                                                                                                                                                                          def AggQueryIn.stripAgg {T : Type} {c n : ℕ} {κ : Fin n → ColKind} {l : List (String × ℕ)} :
                                                                                                                                                                                                                          AggQueryIn T c n κ l → AggQueryIn T c n κ l

                                                                                                                                                                                                                          Strip a general query of the constructs whose annotated data part keeps rows the classical semantics removes: differences (annotated Diff never removes tuple slots) and selections containing an aggregate atom (the annotated evaluator keeps classically-failing rows annotated 𝟘, as ProvSQL emits them). The data-part adequacy of evaluateAnnotated is stated against the plain evaluation of the stripped query, mirroring Query.stripDiff in Provenance.QueryAdequacy.

                                                                                                                                                                                                                          Equations
                                                                                                                                                                                                                          Instances For
                                                                                                                                                                                                                            Dependency graph
                                                                                                                                                                                                                            def AggQueryIn.noProvSum {T : Type} {c n : ℕ} {κ : Fin n → ColKind} {l : List (String × ℕ)} :
                                                                                                                                                                                                                            AggQueryIn T c n κ l → Prop

                                                                                                                                                                                                                            No plan-level provenance aggregation. The possible-world metatheorems (random-world commutation, PQE) are about source queries; ProvSum is a rewriting-target operator whose deterministic group sum is not world-faithful – exactly as the classical Agg was excluded from the annotated evaluators.

                                                                                                                                                                                                                            Equations
                                                                                                                                                                                                                            Instances For
                                                                                                                                                                                                                              Dependency graph

                                                                                                                                                                                                                              Terms reading the context only where it is plain #

                                                                                                                                                                                                                              A term reads a parameter as a plain value through outer k; that is the right reading only of a parameter that is not aggregate, an aggregate one being read, world by world, through the leaf AggQueryIn.Param. outerOk ok says every outer k of a term has ok k, and the readings agree on contexts agreeing there.

                                                                                                                                                                                                                              def TermIn.outerOk {T : Type} {c n : ℕ} (ok : Fin c → Prop) :
                                                                                                                                                                                                                              TermIn T c n → Prop

                                                                                                                                                                                                                              Every outer column the term reads satisfies ok.

                                                                                                                                                                                                                              Equations
                                                                                                                                                                                                                              Instances For
                                                                                                                                                                                                                                Dependency graph
                                                                                                                                                                                                                                def TermGIn.outerOk {T : Type} {c n : ℕ} {κ : Fin n → ColKind} (ok : Fin c → Prop) :
                                                                                                                                                                                                                                TermGIn T c κ → Prop
                                                                                                                                                                                                                                Equations
                                                                                                                                                                                                                                Instances For
                                                                                                                                                                                                                                  Dependency graph
                                                                                                                                                                                                                                  def GenPredIn.outerOk {T : Type} {c n : ℕ} {κ : Fin n → ColKind} (ok : Fin c → Prop) :
                                                                                                                                                                                                                                  GenPredIn T c κ → Prop
                                                                                                                                                                                                                                  Equations
                                                                                                                                                                                                                                  Instances For
                                                                                                                                                                                                                                    Dependency graph
                                                                                                                                                                                                                                    Dependency graph

                                                                                                                                                                                                                                    The kinds of the rounds each recursive name is bound to.

                                                                                                                                                                                                                                    Equations
                                                                                                                                                                                                                                    Instances For
                                                                                                                                                                                                                                      Dependency graph

                                                                                                                                                                                                                                      No name bound: every round regular.

                                                                                                                                                                                                                                      Equations
                                                                                                                                                                                                                                      Instances For
                                                                                                                                                                                                                                        Dependency graph
                                                                                                                                                                                                                                        def HoleKinds.assign (HK : HoleKinds) (s : String) {n : ℕ} (κ : Fin n → ColKind) :

                                                                                                                                                                                                                                        Binding a recursive name to rounds of kinds κ.

                                                                                                                                                                                                                                        Equations
                                                                                                                                                                                                                                        Instances For
                                                                                                                                                                                                                                          Dependency graph
                                                                                                                                                                                                                                          def AggQueryIn.wellKinded {T : Type} {c n : ℕ} {κ : Fin n → ColKind} {l : List (String × ℕ)} :
                                                                                                                                                                                                                                          AggQueryIn T c n κ l → (Fin c → ColKind) → HoleKinds → Prop

                                                                                                                                                                                                                                          The query is well-kinded in a context of kinds ρc, its recursive names bound to rounds of kinds HK: a hole has the kinds of the rounds of its name, a parameter leaf the kinds of the parameters it reads (a constant being regular), and so, inside, at every apply and every recursion. This is what the kind-indexed syntax cannot say by itself, the context and the rounds being read through the evaluation's environment.

                                                                                                                                                                                                                                          Equations
                                                                                                                                                                                                                                          Instances For
                                                                                                                                                                                                                                            Dependency graph
                                                                                                                                                                                                                                            def EvalEnv.Kinded {T K : Type} (E : EvalEnv T K) {c : ℕ} (γ : Fin c → T) (ρc : Fin c → ColKind) (HK : HoleKinds) :

                                                                                                                                                                                                                                            The environment agrees with the kinds: its context, at the arity c, has the kinds ρc and the plain values γ, and every round it binds to a name has the kinds HK gives that name.

                                                                                                                                                                                                                                            Equations
                                                                                                                                                                                                                                            Instances For
                                                                                                                                                                                                                                              Dependency graph
                                                                                                                                                                                                                                              def AggQueryIn.noExplode {T' : Type} {c n : ℕ} {κ : Fin n → ColKind} {l : List (String × ℕ)} :
                                                                                                                                                                                                                                              AggQueryIn T' c n κ l → Prop

                                                                                                                                                                                                                                              No aggregate column read as a key. Reading one produces a row per value the column takes in some world, so the data part of the annotated evaluation is not the data part of any one world, and the annotation-forgetting adequacy of evaluateAnnotated_toPlain does not hold for it – unlike the readings that are world readings, the Boolean support and the random world, which Explode respects.

                                                                                                                                                                                                                                              Equations
                                                                                                                                                                                                                                              Instances For
                                                                                                                                                                                                                                                Dependency graph

                                                                                                                                                                                                                                                Join conditions on key columns #

                                                                                                                                                                                                                                                def keyJoinCond {T' : Type} [Zero T'] {n m : ℕ} {κ : Fin m → ColKind} (posL posR : Fin n → Fin m) (hL : ∀ (k : Fin n), κ (posL k) = ColKind.reg) (hR : ∀ (k : Fin n), κ (posR k) = ColKind.reg) :
                                                                                                                                                                                                                                                GenPred T' κ

                                                                                                                                                                                                                                                The conjunction of key equalities between two blocks of regular columns (the join condition of the Diff rewriting).

                                                                                                                                                                                                                                                The atoms are SQL's IS NOT DISTINCT FROM, not =: a key join keys on values, two nulls being the same key, where NULL = NULL is unknown and would drop the row.

                                                                                                                                                                                                                                                Equations
                                                                                                                                                                                                                                                • One or more equations did not get rendered due to their size.
                                                                                                                                                                                                                                                Instances For
                                                                                                                                                                                                                                                  Dependency graph
                                                                                                                                                                                                                                                  theorem AggQueryIn.evaluate_castKind {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {c n : ℕ} {κ κ' : Fin n → ColKind} {l : List (String × ℕ)} (h : κ = κ') (q : AggQueryIn T c n κ l) (d : AnnotatedDatabase T K) {γ : Fin c → T} {E : EvalEnv T K} :
                                                                                                                                                                                                                                                  (castKind h q).evaluate d γ E = q.evaluate d γ E

                                                                                                                                                                                                                                                  Kind transport is transparent to evaluation (row types do not mention the kind vector).

                                                                                                                                                                                                                                                  Dependency graph
                                                                                                                                                                                                                                                  @[reducible, inline]
                                                                                                                                                                                                                                                  abbrev ColKind.gammaKinds (n₁ n₂ : ℕ) :
                                                                                                                                                                                                                                                  Fin (n₁ + n₂) → ColKind

                                                                                                                                                                                                                                                  The kind vector of a Gamma output: key columns then token columns.

                                                                                                                                                                                                                                                  Equations
                                                                                                                                                                                                                                                  Instances For
                                                                                                                                                                                                                                                    Dependency graph

                                                                                                                                                                                                                                                    Kind conformance #

                                                                                                                                                                                                                                                    Rows produced by the general evaluator conform to the query's kind vector: regular columns hold regular values, token columns hold tokens. This is an invariant lemma, not a hypothesis: the kind-indexed syntax makes it hold by construction, and downstream theorems (the random-world commutation in particular) invoke it instead of assuming wellformedness.

                                                                                                                                                                                                                                                    def GenRow.OrdinaryTokens {T K : Type} {n : ℕ} (u : Tuple (GenValue T K) n) :

                                                                                                                                                                                                                                                    Every aggregate column of a tuple holds an ordinary token – neither a nested value nor an expression over several of them. On a row the evaluator produces it is a theorem for a query with no multi-frame window, no second-level aggregation and no FILTER clause (AggQueryIn.evaluate_ordinaryTokens).

                                                                                                                                                                                                                                                    Equations
                                                                                                                                                                                                                                                    Instances For
                                                                                                                                                                                                                                                      Dependency graph
                                                                                                                                                                                                                                                      def GenRow.NoNested {T K : Type} {n : ℕ} (u : Tuple (GenValue T K) n) :

                                                                                                                                                                                                                                                      No column of a tuple holds a nested token. Weaker than GenRow.OrdinaryTokens, which also excludes an aggregate expression. On a row the evaluator produces it is a theorem for a query with no second-level aggregation (AggQueryIn.evaluate_noNested).

                                                                                                                                                                                                                                                      Equations
                                                                                                                                                                                                                                                      Instances For
                                                                                                                                                                                                                                                        Dependency graph
                                                                                                                                                                                                                                                        def AggQueryIn.noFilter {T : Type} {c n : ℕ} {κ : Fin n → ColKind} {l : List (String × ℕ)} :
                                                                                                                                                                                                                                                        AggQueryIn T c n κ l → Prop

                                                                                                                                                                                                                                                        No FILTER clause. A grouping may cut the occurrence sequence one of its aggregates reads (AggQueryIn.Gamma's keep, and AggQueryIn.GammaTok's in the rewritten world), a window the part of its frame it reads (AggQueryIn.Win's keep), and a multi-frame window the part of each leaf's frame (AggQueryIn.WinExpr's keeps).

                                                                                                                                                                                                                                                        What asks this is AggQueryIn.evaluate_ordinaryTokens, and for the reason that fence exists: a filtered aggregate of a grouping or of a frame builds an aggregate expression and not an ordinary token, the clause cutting what the expression reads and not its family. Nothing else asks it. In particular the rewritten world's evaluator reads a clause like the plain one does – both through Relation.groupSeqOpt and ValueFrame.windowValueOpt – so AggQueryIn.evaluateRew_plain covers a filtered grouping and a filtered window, as the evaluators, the hom commutation, the possible-world reading and the data-part adequacy already did.

                                                                                                                                                                                                                                                        Equations
                                                                                                                                                                                                                                                        Instances For
                                                                                                                                                                                                                                                          Dependency graph
                                                                                                                                                                                                                                                          def AggQueryIn.noGammaNest {T : Type} {c n : ℕ} {κ : Fin n → ColKind} {l : List (String × ℕ)} :
                                                                                                                                                                                                                                                          AggQueryIn T c n κ l → Prop

                                                                                                                                                                                                                                                          No second-level aggregation. GammaNest is the one operator of the syntax that builds a nested token, and what this excludes is the two syntactic token fences it is the counterexample to (AggQueryIn.evaluate_noNested, AggQueryIn.evaluate_ordinaryTokens). Everything else covers it, at every storey: the evaluators and the kind conformance ask nothing, the data-part adequacy, the guardedness and the rewritten world's plain reading are proved, and so are the random world, the PQE results and the hom commutation.

                                                                                                                                                                                                                                                          What the hom reads of a nested value. A nested world's weight is not a function of the four readings its occurrences' inner values carry: NestedValue.World.ann is presentProd ⊗ (𝟙 ⊖ absentSum) with the monus taken once, over the value's own occurrences, each expression family and each inner node together, while a reading bundles a monus per world. So GenValue.Equiv relates a nested column by its collapse, convention and aggregate only, and the hom carries the rest structurally: two nested values built from related listings are related occurrence by occurrence (NestInner.Rel), and their worlds then correspond one by one, with the kept product and the absent sum pushed through the hom (NestedValue.WCorr, wcorr_of_rel).

                                                                                                                                                                                                                                                          Equations
                                                                                                                                                                                                                                                          Instances For
                                                                                                                                                                                                                                                            Dependency graph
                                                                                                                                                                                                                                                            def AggQueryIn.recSettles {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {c n : ℕ} {κ : Fin n → ColKind} {l : List (String × ℕ)} :
                                                                                                                                                                                                                                                            AggQueryIn T c n κ l → Prop

                                                                                                                                                                                                                                                            Every recursion of the query settles. A recursion means the value its rounds settle at and means nothing elsewhere, so a result that evaluates one asks this: at a MuSet, that the iteration repeats a round (MuSetSettles); at a Mu, that some round is empty (MuSettles) and that an empty round stays empty, which is what SQL's requirement that the recursive reference occur in the body buys.

                                                                                                                                                                                                                                                            It is asked at every database, because a nested recursion is evaluated at the databases its enclosing rounds produce. A query with no recursion satisfies it with no content, every clause but the two recursions asking only what its subqueries ask.

                                                                                                                                                                                                                                                            Equations
                                                                                                                                                                                                                                                            Instances For
                                                                                                                                                                                                                                                              Dependency graph
                                                                                                                                                                                                                                                              def AggQueryIn.readsRecorded {T : Type} {c n : ℕ} {κ : Fin n → ColKind} {l : List (String × ℕ)} :
                                                                                                                                                                                                                                                              AggQueryIn T c n κ l → Prop

                                                                                                                                                                                                                                                              Every aggregating operator records the parameters it reads: its read set rd holds every outer column its subtree reads – the operator's readsOuter, which counts rd itself, is rd. Then the identity of occurrences is that an operator evaluated on the same inputs produces the same occurrences, and this is a condition on the queries a result is about. A recorded set may hold more than the subtree reads: the passes keep each operator's recorded set while rewriting below it, so their outputs record what their sources read.

                                                                                                                                                                                                                                                              Equations
                                                                                                                                                                                                                                                              Instances For
                                                                                                                                                                                                                                                                Dependency graph
                                                                                                                                                                                                                                                                def AggQueryIn.noWinExpr {T : Type} {c n : ℕ} {κ : Fin n → ColKind} {l : List (String × ℕ)} :
                                                                                                                                                                                                                                                                AggQueryIn T c n κ l → Prop

                                                                                                                                                                                                                                                                No multi-frame window. WinExpr is the one operator of the syntax that builds an aggregate column holding an expression rather than an ordinary token, so the results proved only for ordinary tokens exclude it with this – as the possible-world results exclude ProvSum with noProvSum.

                                                                                                                                                                                                                                                                A result that reads an expression column through the four readings AggExpr provides needs no such fence; the hom commutation asks instead that the frames be read off the tuples (AggQueryIn.framesContainSelf).

                                                                                                                                                                                                                                                                Equations
                                                                                                                                                                                                                                                                Instances For
                                                                                                                                                                                                                                                                  Dependency graph
                                                                                                                                                                                                                                                                  def AggQueryIn.framesContainSelf {T : Type} [ValueType T] {c n : ℕ} {κ : Fin n → ColKind} {l : List (String × ℕ)} :
                                                                                                                                                                                                                                                                  AggQueryIn T c n κ l → Prop

                                                                                                                                                                                                                                                                  Every multi-frame window frames by the tuple. A window expression lists its shared family by occurrence index, and a change of annotation semiring re-sorts that index inside blocks of equal rows, so a reading of the family that told two equal rows apart would not survive the change. ValueFrame.ContainsSelf is what stops it telling them apart: the frame contains its current row exactly when it contains its peers, so membership is a test on the tuples (ValueFrame.mem_of_containsSelf).

                                                                                                                                                                                                                                                                  RANGE, the whole partition and the rows strictly before all satisfy it; EXCLUDE CURRENT ROW and EXCLUDE TIES are exactly the frames that do not (ValueFrame.not_containsSelf_excludeCurrent), and they are the ones a multi-frame window needs the occurrences for. Nothing is asked of a single-frame Win, whose token is read off the relation.

                                                                                                                                                                                                                                                                  Equations
                                                                                                                                                                                                                                                                  Instances For
                                                                                                                                                                                                                                                                    Dependency graph
                                                                                                                                                                                                                                                                    theorem AggQueryIn.evaluate_ordinaryTokens {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {c n : ℕ} {κ : Fin n → ColKind} {l : List (String × ℕ)} (q : AggQueryIn T c n κ l) :
                                                                                                                                                                                                                                                                    q.noWinExpr → q.noGammaNest → q.noFilter → ∀ (d : AnnotatedDatabase T K) {γ : Fin c → T} (E : EvalEnv T K), EvalEnv.RowsSat (fun (v : GenValue T K) => ∀ (a : AggTok T K), v = Sum.inr a → a.isTok = true) E → ∀ r ∈ q.evaluate d γ E, GenRow.OrdinaryTokens r.1

                                                                                                                                                                                                                                                                    Only WinExpr and GammaNest build anything but an ordinary token. Every aggregate column of every row a query without them produces holds an ordinary token: the grouping and the window build their tokens with AggTok.tok, a projection copies or post-composes one – and AggTok.postcomp keeps the kind – and everything else carries rows through or rebuilds them from annotated tuples. A multi-frame window builds an expression and second-level aggregation a nested value, which is why both are excluded here.

                                                                                                                                                                                                                                                                    This is what lets a result proved only for an ordinary token keep its statement about rows: it gets “every token here is ordinary” from this lemma, with the two operators excluded on the query.

                                                                                                                                                                                                                                                                    Dependency graph
                                                                                                                                                                                                                                                                    theorem AggQueryIn.evaluate_noNested {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {c n : ℕ} {κ : Fin n → ColKind} {l : List (String × ℕ)} (q : AggQueryIn T c n κ l) (hn : q.noGammaNest) (d : AnnotatedDatabase T K) {γ : Fin c → T} (E : EvalEnv T K) (hE : EvalEnv.RowsSat (fun (v : GenValue T K) => ∀ (a : AggTok T K), v = Sum.inr a → a.isNested = false) E) (r : GenRow T K n) (hr : r ∈ q.evaluate d γ E) :

                                                                                                                                                                                                                                                                    The form for an environment holding no nested value at all.

                                                                                                                                                                                                                                                                    Dependency graph
                                                                                                                                                                                                                                                                    theorem AggQueryIn.evaluate_conform {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {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} (r : GenRow T K n) :
                                                                                                                                                                                                                                                                    r ∈ q.evaluate d γ E → ∀ (k : Fin n), (r.1 k).kindOf = (κ k).base

                                                                                                                                                                                                                                                                    Kind conformance of the general evaluator.

                                                                                                                                                                                                                                                                    Dependency graph