Documentation

Provenance.AggQueryGroupRewriting

Rewriting a bare grouping: aggregate results as output values #

The HAVING site rewriting of Provenance.AggQueryHavingRewriting covers the case where the aggregate tokens of a grouping are consumed by a comparison gate and never leave the site. This module covers the complementary – and, in SQL, far more common – case: a bare GROUP BY whose aggregate columns flow onward as ordinary output columns.

Rule (R5) is the classical counterpart. Carrying it over the classical syntax took a whole new value domain – data, annotation and K-tensor monomials, quotiented – together with its own evaluator. In the general framework no new value domain is needed: the rewritten world's evaluator already has aggregate tokens as ordinary column values, and AggQueryIn.GammaTok – ProvSQL's provsql_agg – already materializes exactly the token that the general evaluator's Gamma produces. What is needed is the correspondence at token level: the statement of AggQueryIn.rewriting_valid folds an annotated relation into composite rows through AnnotatedRelation.toComposite, which reads tokens through their deterministic collapse and therefore cannot express a token-bearing output.

GenRow.toCompositeRow supplies that embedding: data columns go through Sum.inl, token columns are transported by AggValue.toComposite (values embedded in the composite domain, occurrence annotations unchanged), and the row's finalized annotation is appended as the provenance column. On token-free rows it agrees with AnnotatedRelation.toComposite (GenRow.toCompositeRow_of_reg), so the statement below genuinely extends the compositional rewriting correctness rather than sitting beside it.

AggQueryIn.gammaRew_valid is then the (R5) analogue: for a classical subquery, the general evaluator's grouping – tokens and pending group-existence factor included – is computed by the rewritten token-building grouping over the classically rewritten subquery, with the group guard δ(⊕ U) landing in the provenance column.

Tokens in the composite domain #

def FamId.toComposite {T K : Type} :
FamId T → FamId (T ⊕ K)

Transport the identity of an aggregate value to the composite value domain: the key's and the parameters' values are embedded by Sum.inl. The terms applied to the value are dropped: the rewritten world's columns apply functions to the data arm (ProjColIn.aggTerm), not terms, so its values record none, and the rewriting is an equality of rows.

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

    Transport a symbolic aggregate token to the composite value domain: the aggregated values are embedded by Sum.inl, the aggregate function is lifted, and the occurrence annotations are unchanged.

    Equations
    Instances For
      Dependency graph
      def AggExprFun.liftComposite {T : Type} [ValueType T] {K : Type} {p : ℕ} (g : (Fin p → T) → T) :
      (Fin p → T ⊕ K) → T ⊕ K

      Lift the function of an aggregate expression to the composite domain, as SeqAggFunc.liftComposite lifts an aggregate: junk on the annotation arm, faithful on inl-embedded values.

      Equations
      Instances For
        Dependency graph
        theorem AggExpr.length_inl_occs {T K : Type} (a : AggExpr T K) :
        a.occs.length = (List.map (fun (o : (Fin a.arity → T) × K × (Fin a.arity → Bool) × (Fin a.arity → Bool)) => (fun (j : Fin a.arity) => Sum.inl (o.1 j), o.2)) a.occs).length

        Embedding the occurrence values leaves the family's length, hence the index type of a world, where it was.

        Dependency graph
        def AggExpr.toComposite {T : Type} [ValueType T] {K : Type} (a : AggExpr T K) :
        AggExpr (T ⊕ K) K

        Transport an aggregate expression to the composite domain: the occurrence values are embedded by Sum.inl, the leaf aggregates and the expression's own function are lifted, and the occurrence annotations and the leaf readings are unchanged.

        Equations
        • One or more equations did not get rendered due to their size.
        Instances For
          Dependency graph

          Hence the value in a world is the embedding of the value there.

          Dependency graph

          The expression a filtered aggregate of a group builds transports too: the clause of the rewritten world is the source's read on the embedded row, which Selection.castToAnnotatedTuple keeps, so the occurrences, their annotations and their clause flags all agree.

          Dependency graph
          def NestInner.toComposite {T : Type} [ValueType T] {K : Type} (j : ℕ) :
          NestInner T K j → NestInner (T ⊕ K) K j

          Transport an inner value to the composite value domain, storey by storey: an expression as AggExpr.toComposite does, a node with its outer aggregate lifted and its occurrences transported.

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

            Transport a nested value to the composite value domain: its inner values the same way, each family keeping its occurrences.

            Equations
            • One or more equations did not get rendered due to their size.
            Instances For
              Dependency graph
              def AggTok.toComposite {T : Type} [ValueType T] {K : Type} :
              AggTok T K → AggTok (T ⊕ K) K

              Transport a token to the composite value domain. A nested token transports its inner values the same way, and an expression its shared occurrences, its leaf aggregates and its own function.

              Equations
              Instances For
                Dependency graph
                def GenValue.toComposite {T : Type} [ValueType T] {K : Type} :
                GenValue T K → GenValue (T ⊕ K) K

                Transport a lifted column value to the composite domain.

                Equations
                Instances For
                  Dependency graph
                  def GenRow.toCompositeRow {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] {n : ℕ} (r : GenRow T K n) :
                  Tuple (GenValue (T ⊕ K) K) (n + 1)

                  The token-aware composite embedding of a general row: every column transported to the composite domain, with the row's finalized annotation appended as the provenance column.

                  Equations
                  Instances For
                    Dependency graph
                    theorem GenRow.toCompositeRow_of_reg {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] {n : ℕ} (r : GenRow T K n) (hr : ∀ (k : Fin n), (r.1 k).kindOf = ColKind.reg) :

                    On token-free rows the token-aware embedding is the embedding used by the classical and HAVING-site rewriting correctness statements: the inl-image of the composite encoding of the finalized annotated tuple.

                    Dependency graph

                    Coordinates of the token-aware embedding #

                    The rewritten bare grouping #

                    @[reducible, inline]
                    abbrev ColKind.gammaRewKinds (n₁ n₂ : ℕ) :
                    Fin (n₁ + n₂ + 1) → ColKind

                    The kind vector of a rewritten Gamma output: the group keys, the aggregate tokens, and the provenance column carrying the group guard.

                    Equations
                    Instances For
                      Dependency graph
                      theorem ColKind.gammaTok_rew_kinds_of {m n₁ n₂ : ℕ} {κ' : Fin (m + 1) → ColKind} (is : Tuple (Fin m) n₁) (hkey : ∀ (k : Fin n₁), κ' (Fin.castLE ⋯ (is k)) = reg) :
                      (Fin.append (Fin.append (fun (k : Fin n₁) => κ' (Fin.castLE ⋯ (is k))) fun (x : Fin n₂) => agg) fun (x : Fin 1) => prov) = gammaRewKinds n₁ n₂

                      The kind vector produced by the token-building grouping over a rewritten subquery is the rewritten Gamma kind vector, whatever rewritten schema the subquery carries: all that is asked of it is that the key columns be regular, which they are in a rewriting of an all-regular query.

                      Dependency graph
                      def AggQueryIn.gammaRewOf {T : Type} [ValueType T] {K : Type} {m n₁ n₂ : ℕ} {κ' : Fin (m + 1) → ColKind} (is : Tuple (Fin m) n₁) (ts : Tuple (Term T m) n₂) (fs : Tuple (SeqAggFunc T) n₂) (hkey : ∀ (k : Fin n₁), κ' (Fin.castLE ⋯ (is k)) = ColKind.reg) (hprov : κ' (Fin.last m) = ColKind.prov) (q' : AggQuery (T ⊕ K) (m + 1) κ') (keep : Fin n₂ → Option (Selection T m) := fun (x : Fin n₂) => none) (lab : ℕ := 0) (rd : Fin 0 → Bool := fun (x : Fin 0) => false) :
                      AggQuery (T ⊕ K) (n₁ + n₂ + 1) (ColKind.gammaRewKinds n₁ n₂)

                      The rewritten grouping over an arbitrary rewritten subquery: the same provsql_agg grouping as AggQueryIn.gammaRew, reading the occurrence annotations off the subquery's provenance column, but over any query of the rewritten world that computes the subquery's rows – not only the classical rewriting of a classical one. This is what makes the rule compositional: a GROUP BY whose input is itself a grouping (its aggregate column cashed by a projection, which is what the kind discipline asks) is rewritten by composing the two.

                      Equations
                      • One or more equations did not get rendered due to their size.
                      Instances For
                        Dependency graph
                        def AggQueryIn.gammaRew {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [HasAltLinearOrder K] {m n₁ n₂ : ℕ} (is : Tuple (Fin m) n₁) (ts : Tuple (Term T m) n₂) (fs : Tuple (SeqAggFunc T) n₂) (qg : AggQuery T m (ColKind.allReg m)) (hq : classical qg) (lab : ℕ := 0) (rd : Fin 0 → Bool := fun (x : Fin 0) => false) :
                        AggQuery (T ⊕ K) (n₁ + n₂ + 1) (ColKind.gammaRewKinds n₁ n₂)

                        The rewritten bare grouping: ProvSQL's provsql_agg grouping over the classically rewritten subquery, reading the occurrence annotations off the subquery's provenance column. The output carries the group keys, one aggregate token per (term, aggregate) pair, and the group-existence guard δ(⊕ U) in the provenance column.

                        It is AggQueryIn.gammaRewOf over the classical rewriting of the subquery; the general form takes any query of the rewritten world that computes the subquery's rows.

                        Equations
                        Instances For
                          Dependency graph

                          Correctness #

                          theorem AggQueryIn.gammaRewOf_valid {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {lab : ℕ} {rd : Fin 0 → Bool} {m n₁ n₂ : ℕ} {κ' : Fin (m + 1) → ColKind} (is : Tuple (Fin m) n₁) (ts : Tuple (Term T m) n₂) (fs : Tuple (SeqAggFunc T) n₂) (qg : AggQuery T m (ColKind.allReg m)) (hkey : ∀ (k : Fin n₁), κ' (Fin.castLE ⋯ (is k)) = ColKind.reg) (hprov : κ' (Fin.last m) = ColKind.prov) (q' : AggQuery (T ⊕ K) (m + 1) κ') (keep : Fin n₂ → Option (Selection T m)) (d : AnnotatedDatabase T K) (R : AnnotatedRelation T K m) (hR : Multiset.map GenRow.toAnnotated (evaluate qg d) = R) (har : Multiset.map (fun (u : Tuple (GenValue (T ⊕ K) K) (m + 1)) => (GenRow.plainTuple u, ((TermGIn.provIndex (Fin.last m) hprov).evalRew u).annPart)) (evaluateRew q' d.toComposite) = Multiset.map (fun (p : AnnotatedTuple T K m) => (p.toComposite, p.2)) R) :
                          Multiset.map GenRow.toCompositeRow ((Gamma is ts fs qg keep).evaluate d) = evaluateRew (gammaRewOf is ts fs hkey hprov q' keep lab rd) d.toComposite

                          Correctness of the bare-grouping rewriting, compositionally – the general framework's rule (R5) over any rewritten subquery: what is asked of the subquery is only that the rewritten world's query compute its rows, as the pairs of a plain tuple and the annotation its provenance column carries. The grouping itself is the same.

                          Dependency graph
                          theorem AggQueryIn.gammaRew_valid {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {lab : ℕ} {rd : Fin 0 → Bool} {m n₁ n₂ : ℕ} (is : Tuple (Fin m) n₁) (ts : Tuple (Term T m) n₂) (fs : Tuple (SeqAggFunc T) n₂) (qg : AggQuery T m (ColKind.allReg m)) (hq : classical qg) (d : AnnotatedDatabase T K) :

                          Correctness of the bare-grouping rewriting – the general framework's rule (R5): for a classical subquery, the general evaluator's grouping, embedded row-wise into the composite domain (tokens included, finalized annotation appended), is computed by the rewritten world's token-building grouping over the classically rewritten subquery.

                          Dependency graph

                          The gate reads a transported token unchanged #

                          The predicate provenance under the token transport: comparing a transported token against an embedded value is the original comparison. The token transport preserves lengths and annotations, lifts the aggregate faithfully on embedded values, and comparisons restrict along inl.

                          Dependency graph
                          Dependency graph

                          The same length, named by the transported expression's own family.

                          Dependency graph

                          Hence a transported world is a world exactly when it was one.

                          Dependency graph

                          Hence a comparison against an embedded constant.

                          Dependency graph