Documentation

Provenance.AggQueryClosure

The compositional closure of the rewriting rules #

ProvSQL rewrites whole queries in which classical blocks, GROUP BY … HAVING blocks and bare GROUP BY blocks occur as subqueries. The relation AggQueryIn.RewritesTo below closes the three base rewritings – the classical rules (AggQueryIn.rewritingOf), the HAVING site (AggQueryIn.havingPredRew, the aggregate-exposing shape ProvSQL actually emits, for an arbitrary Boolean combination of aggregate comparisons) and the bare grouping (AggQueryIn.gammaRew) – under the operators that may sit above them, and AggQueryIn.rewritesTo_valid extends the correctness to every query so obtained.

Token-bearing outputs #

The base rules do not share an output shape: a classical or HAVING block produces all-regular data columns, whereas a bare grouping produces aggregate-token columns. The relation is therefore indexed by the rewritten query's own kind vector, and correctness is stated at the token level, through GenRow.toCompositeRow. On all-regular outputs this specializes to the all-regular statement, AggQueryIn.rewritesTo_valid_reg.

The natural rewritten kind vector of a query of kinds κ is ColKind.rewKindsOf κ – the source kinds followed by the provenance column. Casting terms, predicates and projection columns into it is uniform: a column keeps its kind, so no all-regular hypothesis is needed anywhere (TermGIn.castRew and friends), unlike the composite casts of the classical rewriting. The gate TermGIn.cmpAgg, whose generic semantics is the junk value 𝟘, casts to that constant.

Scope #

Selection, projection and union close over arbitrary kinds – in particular over a bare grouping, which is the SELECT … FROM (GROUP BY …) shape. Deduplication closes over any subquery whose output is all-regular, which is what the kind discipline permits: the rewritten rule AggQueryIn.dedupRew is ProvSQL's ε (group by the data columns, ⊕-sum the provenance column), proven correct against an arbitrary rewritten subquery rather than only against rewriting's output.

Product closes over arbitrary kinds too. Reassembling a join needs a projection column whose kind is read off the operand's kind vector – ProjColIn.copy, which dispatches on that kind – and its faithfulness needs the operands' rows to conform; that comes for free from the subderivations, since their rows are embeddings of rows of the general evaluator, which conforms by AggQueryIn.evaluate_conform.

Difference closes as well (AggQueryIn.diffRew).

The grouping itself closes over an arbitrary rewritten subquery (AggQueryIn.RewritesTo.gammaOf, off AggQueryIn.gammaRewOf_valid): what the rule asks of its input is only that some query of the rewritten world compute its rows, not that it be classical. A clause rides into it unchanged (Selection.castToAnnotatedTuple reads the data columns, which the embedding keeps), so a filtered grouping is covered as well (AggQueryIn.rewritesTo_gamma_filter). This is what covers a GROUP BY whose input is itself a grouping – the kind discipline asking the inner aggregate column to be read out first, as SQL does with a SELECT key, count(*) AS c subquery – which AggQueryIn.rewritesTo_gamma_gamma exhibits and the classical gamma rule cannot reach. The selection with an aggregate atom closes over an arbitrary rewritten subquery too (AggQueryIn.RewritesTo.selAgg, off AggQueryIn.selAggRew_valid), so a HAVING need not sit on the grouping it reads: AggQueryIn.rewritesTo_having_over_gamma puts one over a grouping of a grouping. Both selection rules are stated where ProvSQL's gate algebra is the joint reading the evaluator computes (GenPredIn.gateExact). Its provenance column is the gate term times the row's own provenance column, with no entailment test – where the predicate entails the group's existence the evaluator drops the pending factor and the gate term absorbs the guard left in the column instead (GenPredIn.predsem_absorb_prod, exactly for the factors whose family the predicate compares, which is what the evaluator's supersede filter selects). The entailment test of the fused site (GenPredIn.siteProvTerm) is therefore an optimization – ProvSQL's having_entails_group_existence – and not what makes the rewriting correct; the fused rule stays because it is the shape ProvSQL emits.

So the closure is complete for the operators the kind discipline admits above a grouping, and for a grouping and a HAVING above anything the closure reaches. What is outside it is a difference above a grouping, which the kinds already forbid, and the operators this layer gives no rewriting rule: the windows, the apply, the two recursions and the alternatives. For the apply, the recursions and the alternatives there is a reason in the shape of the rewritten plan, recorded with AggQueryIn.classical. For the windows there is none: ProvSQL does rewrite them, and what is absent here is a specification of that rewriting, which this library does not give. So the window rules are out of scope rather than impossible.

The rewritten kind vector #

@[reducible, inline]
abbrev ColKind.rewKindsOf {n : ℕ} (κ : Fin n → ColKind) :
Fin (n + 1) → ColKind

The rewritten kind vector of a query of kinds κ: the source kinds, followed by the provenance column.

Equations
Instances For
    Dependency graph
    @[simp]
    theorem ColKind.rewKindsOf_castAdd {n : ℕ} (κ : Fin n → ColKind) (k : Fin n) :
    rewKindsOf κ (Fin.castAdd 1 k) = κ k
    Dependency graph
    @[simp]
    theorem ColKind.rewKindsOf_last {n : ℕ} (κ : Fin n → ColKind) :
    Dependency graph
    theorem ColKind.rewKindsOf_base_of_reg {n : ℕ} {κ : Fin n → ColKind} (hκ : ∀ (k : Fin n), κ k = reg) (k : Fin (n + 1)) :

    On all-regular kinds the uniform rewritten kind vector agrees pointwise with the classical rewriting's ColKind.rewKinds.

    Dependency graph

    Uniform casts into the rewritten world #

    def TermGIn.castRew {T : Type} [ValueType T] {K : Type} {n : ℕ} {κ : Fin n → ColKind} :
    TermG T κ → TermG (T ⊕ K) (ColKind.rewKindsOf κ)

    A term over the source kinds, read on the rewritten schema: every column keeps its kind and its position, so no all-regular hypothesis is needed. The gate, whose generic semantics is the junk value 𝟘, casts to that constant.

    Equations
    Instances For
      Dependency graph
      def GenPredIn.castRew {T : Type} [ValueType T] {K : Type} {n : ℕ} {κ : Fin n → ColKind} :

      An aggregate-atom-free predicate is unnecessary here: the cast is total, aggregate atoms comparing a token's deterministic reading.

      Equations
      Instances For
        Dependency graph
        Dependency graph
        @[simp]
        theorem ProjColIn.castRew_kind {T : Type} [ValueType T] {K : Type} {n : ℕ} {κ : Fin n → ColKind} (p : ProjCol T κ) :
        Dependency graph

        The casts evaluate faithfully #

        theorem ColKind.rewKindsOf_of_lt {n : ℕ} (κ : Fin n → ColKind) {j : Fin (n + 1)} (h : ↑j < n) :
        rewKindsOf κ j = κ ⟨↑j, h⟩

        A data column of a rewritten kind vector, positionally.

        Dependency graph

        Copying a column of unknown kind #

        def ProjColIn.copy {T' : Type} {N : ℕ} {κ' : Fin N → ColKind} (i : Fin N) :
        ProjCol T' κ'

        Copy the i-th column verbatim, whatever its kind: a regular or provenance column is read as a value term, a token column is a verbatim token copy. This is the projection column a join reassembly needs, since the operand's kind vector is not statically known there.

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

          Kind conformance of the token-aware embedding: a row conforming to κ embeds to one conforming to ColKind.rewKindsOf κ.

          Dependency graph

          HAVING predicates as gate terms #

          The HAVING site rewriting of Provenance.AggQueryHavingRewriting takes one aggregate comparison. An arbitrary Boolean combination of atoms is just as expressible: the predicate provenance predsem is ∧ ↦ ⊗, ∨ ↦ ⊕ and ¬ pushed to the atoms by De Morgan duality with operator complementation, and the rewritten world's terms have mul, add and the two gates – provsql_having for an aggregate atom, the indicator gate for a regular one. GenPredIn.gateTerm is that translation; it is faithful for an arbitrary predicate (GenPredIn.gateTerm_evalRew), the gates being the primitives the correctness is relative to.

          Regular atoms do change the fate of the group guard. An aggregate atom's predicate provenance ranges over non-empty worlds only, so it supersedes the guard; a regular atom's χ does not entail the group's existence (GenPredIn.entailsExistence), and mixing one in can leave the whole predicate non-entailing – count(*) > 5 ∨ city = 'Paris' fires in worlds where the group is empty. The site rewriting therefore keeps the guard as a factor in that case (GenPredIn.siteProvTerm), reproducing what the general evaluator does with the pending group factor.

          def GenPredIn.rangeFree {T : Type} {n : ℕ} {κ : Fin n → ColKind} :
          GenPred T κ → Bool

          No range atom. A range compares one token against two terms at once, and there is no gate for that: provsql_having carries a single comparison. The site rewriting is therefore stated on range-free predicates, and a range emitted as the product of two gates denotes the product of the two atoms' provenances, which is the range's own ⊕-sum only where AggValue.predProvOf_mul_predProvOf applies.

          What the emitted term denotes and what an evaluator computes from it are two questions, and ProvSQL answers the second one outside the circuit, as its implementation shows. Its gate is gate_cmp, two wires and one operator, with no range form, and the rewriter turns ∧ into provenance_times and ∨ into provenance_plus over one gate per atom – which is exactly the algebra of GenPredIn.gateTerm. Evaluation then recognizes a times or plus whose children are conditions over one contributor family, rebuilds their Boolean tree, enumerates that family's worlds once (bounded, a couple of dozen contributors) and keeps a world iff the whole predicate holds there; a conjunction bounding one count(*) from both sides has the closed form S_C ⊖ S_{D+1}, which is this library's Having.G_eq_S_monus_S, where that lemma's hypotheses hold. The plain product is accepted as the answer only in a semiring where product is the joint reading (exclusive with idempotent product); where joint resolution does not apply the system falls back to the product and warns that it is not the provenance of the combination.

          So the fence is faithful to the circuit, which is what gateTerm translates into, and the joint reading – what the evaluator computes, GenPredIn.predsemJ – lives in the evaluation pass. The rewriting's correctness is therefore stated where the two agree (GenPredIn.gateExact). Lifting that means modeling the pass – a Boolean combination of cmpAgg atoms over one token's family, read in one world, which is what AggValue.predProvOfAnd and Provenance.JointFamily already are semantically – and not adding a gate.

          Equations
          Instances For
            Dependency graph
            def GenPredIn.gateExact {T : Type} {n : ℕ} {κ : Fin n → ColKind} :
            GenPred T κ → Bool

            Where the gate algebra is the joint reading: one aggregate comparison, under a conjunction of comparisons. ProvSQL's circuit reads a predicate structurally – a conjunction as a product of gates, a disjunction as a sum – while a selection reads the columns of one family in one world (GenPredIn.predsemJ). The two agree on this fragment (GenPredIn.predsemJ_eq_predsem) and not beyond it: a disjunction of two comparisons that both hold is read 𝟙 ⊕ 𝟙 by the gates and 𝟙 in the world.

            Equations
            Instances For
              Dependency graph
              theorem GenPredIn.predsemJ_eq_predsem {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] {n : ℕ} {κ : Fin n → ColKind} (u : Tuple (GenValue T K) n) (γ : Fin 0 → T) (φ : GenPred T κ) :
              gateExact φ = true → predsemJ φ false u γ = predsem φ false u γ

              On the fragment the gate algebra is the joint reading.

              Dependency graph
              def GenPredIn.aggOnly {T : Type} {n : ℕ} {κ : Fin n → ColKind} :
              GenPred T κ → Bool

              A predicate all of whose atoms are aggregate comparisons.

              Equations
              Instances For
                Dependency graph
                theorem GenPredIn.aggOnly_entailsExistence {T : Type} {n : ℕ} {κ : Fin n → ColKind} (φ : GenPred T κ) :
                aggOnly φ = true → ∀ (neg : Bool), entailsExistence φ neg = true

                An aggregate-only predicate entails its groups' existence, whatever the polarity: every atom does, and both connectives preserve that.

                Dependency graph
                def GenPredIn.gateTerm {T : Type} [ValueType T] {K : Type} {n : ℕ} {κ : Fin n → ColKind} :
                GenPred T κ → Bool → TermG (T ⊕ K) (ColKind.rewKindsOf κ)

                The predicate provenance as a rewritten term: the predsem algebra – aggregate atoms to provsql_having gates, regular atoms to indicator gates, ∧ ↦ ⊗, ∨ ↦ ⊕, ¬ pushed down with operator complementation.

                Equations
                Instances For
                  Dependency graph
                  theorem GenPredIn.gateTerm_evalRew {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {n : ℕ} {κ : Fin n → ColKind} (φ : GenPred T κ) :
                  rangeFree φ = true → ∀ (neg : Bool) (r : GenRow T K n), GenRow.NoNested r.1 → TermGIn.evalRew (gateTerm φ neg) r.toCompositeRow = Sum.inr (predsem φ neg r.1)

                  The gate term computes the predicate provenance, for an arbitrary predicate: relative to the two gate primitives, which is exactly the sense in which ProvSQL's own rewriting is correct.

                  What the row is asked is that no aggregate column hold a nested token (GenRow.NoNested): the provsql_having gate reads the transported column, and the transport is faithful for an ordinary token (AggValue.predProvOf_toComposite) and for an expression – a window's, or a filtered aggregate's – by AggExpr.predProv_toComposite. A nested token's transport has no such lemma yet.

                  Dependency graph

                  The general HAVING site #

                  def GenPredIn.siteProvTerm {T : Type} [ValueType T] {K : Type} {n₁ n₂ : ℕ} (φ : GenPred T (ColKind.gammaKinds n₁ n₂)) :
                  TermG (T ⊕ K) (ColKind.gammaRewKinds n₁ n₂)

                  The provenance column of a rewritten HAVING site: the predicate's gate term, times the group-existence guard δ(⊕ U) – which the rewritten grouping has left in the provenance column – unless the predicate already entails the group's existence, in which case the gate term supersedes it. This is ProvSQL's having_entails_group_existence test: the supersede of the δ gate is licensed exactly when every world the predicate accepts has the group non-empty.

                  Equations
                  Instances For
                    Dependency graph
                    def AggQueryIn.havingPredCols {T : Type} [ValueType T] {K : Type} {n₁ n₂ : ℕ} (φ : GenPred T (ColKind.gammaKinds n₁ n₂)) :
                    Tuple (ProjCol (T ⊕ K) (ColKind.gammaRewKinds n₁ n₂)) (n₁ + n₂ + 1)

                    The output columns of a general HAVING site: the group keys and the aggregate tokens copied verbatim, and the predicate's provenance term in the provenance column.

                    Equations
                    Instances For
                      Dependency graph
                      theorem AggQueryIn.havingPredCols_kind {T : Type} [ValueType T] {K : Type} {n₁ n₂ : ℕ} (φ : GenPred T (ColKind.gammaKinds n₁ n₂)) (j : Fin (n₁ + n₂ + 1)) :

                      The site's output columns have exactly the rewritten Gamma kinds.

                      Dependency graph
                      def AggQueryIn.havingPredRew {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₂) (φ : GenPred T (ColKind.gammaKinds n₁ 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 HAVING site, for an arbitrary predicate: the token-building grouping of AggQueryIn.gammaRew, with a projection keeping the group keys and the aggregate tokens and replacing the group-existence guard by the predicate's provenance term – the gate term alone when the predicate entails the group's existence, the gate term times the guard otherwise.

                      Equations
                      Instances For
                        Dependency graph

                        Duplicate elimination in the rewritten world #

                        The rewritten duplicate elimination: ProvSQL's ε rule – group by the data columns and ⊕-sum the provenance column – applied to an arbitrary rewritten subquery, as AggQueryIn.rewriting does for the classical fragment.

                        Equations
                        Instances For
                          Dependency graph

                          Correctness of the rewritten duplicate elimination, for an arbitrary rewritten subquery.

                          Dependency graph

                          Products of token-bearing blocks #

                          def AggQueryIn.prodRewCols {T K : Type} {n₁ n₂ : ℕ} (κ₁ : Fin n₁ → ColKind) (κ₂ : Fin n₂ → ColKind) :
                          Tuple (ProjCol (T ⊕ K) (Fin.append (ColKind.rewKindsOf κ₁) (ColKind.rewKindsOf κ₂))) (n₁ + n₂ + 1)

                          The reassembly columns of a rewritten product: the two operands' data columns copied verbatim (whatever their kinds), and the product of the two provenance columns.

                          Equations
                          • One or more equations did not get rendered due to their size.
                          Instances For
                            Dependency graph
                            theorem AggQueryIn.prodRewCols_kind {T K : Type} {n₁ n₂ : ℕ} (κ₁ : Fin n₁ → ColKind) (κ₂ : Fin n₂ → ColKind) (j : Fin (n₁ + n₂ + 1)) :
                            ProjColIn.kind (prodRewCols κ₁ κ₂ j) = ColKind.rewKindsOf (Fin.append κ₁ κ₂) j

                            The reassembly columns have the rewritten kinds of the product.

                            Dependency graph
                            def AggQueryIn.prodRew {T K : Type} {n₁ n₂ : ℕ} {κ₁ : Fin n₁ → ColKind} {κ₂ : Fin n₂ → ColKind} (q₁' : AggQuery (T ⊕ K) (n₁ + 1) (ColKind.rewKindsOf κ₁)) (q₂' : AggQuery (T ⊕ K) (n₂ + 1) (ColKind.rewKindsOf κ₂)) :
                            AggQuery (T ⊕ K) (n₁ + n₂ + 1) (ColKind.rewKindsOf (Fin.append κ₁ κ₂))

                            The rewritten product, over operands of arbitrary kinds: the two rewritten blocks joined, the data columns reassembled by kind-preserving copies, and the provenance columns multiplied.

                            Equations
                            Instances For
                              Dependency graph
                              theorem AggQueryIn.prodRew_valid {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {n₁ n₂ : ℕ} {κ₁ : Fin n₁ → ColKind} {κ₂ : Fin n₂ → ColKind} {q₁ : AggQuery T n₁ κ₁} {q₂ : AggQuery T n₂ κ₂} {q₁' : AggQuery (T ⊕ K) (n₁ + 1) (ColKind.rewKindsOf κ₁)} {q₂' : AggQuery (T ⊕ K) (n₂ + 1) (ColKind.rewKindsOf κ₂)} (d : AnnotatedDatabase T K) (ih₁ : Multiset.map GenRow.toCompositeRow (evaluate q₁ d) = evaluateRew q₁' d.toComposite) (ih₂ : Multiset.map GenRow.toCompositeRow (evaluate q₂ d) = evaluateRew q₂' d.toComposite) :

                              Correctness of the rewritten product, for arbitrary operand kinds: conformance of the operands' rows makes the kind-dispatched column copies faithful.

                              Dependency graph

                              Difference in the rewritten world #

                              The general evaluator keeps every row of the left operand, rewriting its annotation to α ⊖ Σβ – the monus against the ⊕-sum of the matching rows on the right. ProvSQL's rewriting encodes that missing left outer join as a union of two branches: rows whose data part is absent from the right operand keep their annotation, rows whose data part is present are joined against the per-key sums and subtract them. The rewritten world's TermGIn.sub supplies the monus directly, so both branches are plain projections of joins, and the two semijoin identities of Provenance.QueryRewriting reduce them to filters of the left operand.

                              The data columns of a rewritten block, as an all-regular query: the provenance column dropped.

                              Equations
                              Instances For
                                Dependency graph

                                The output columns of the unmatched branch: the left block copied verbatim, provenance column included.

                                Equations
                                Instances For
                                  Dependency graph

                                  The output columns of the matched branch: the left block's data columns, and the monus of the two provenance columns.

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

                                    The unmatched branch: left rows whose data part is among the surviving keys, keeping their annotation.

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

                                      The matched branch: left rows joined against the per-key ⊕-sums, subtracting them.

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

                                        The rewritten difference.

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

                                          The classical rewriting at the uniform kind vector #

                                          def AggQueryIn.rewritingOf {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [HasAltLinearOrder K] {n : ℕ} {κ : Fin n → ColKind} (q : AggQuery T n κ) (hq : classical q) :
                                          AggQuery (T ⊕ K) (n + 1) (ColKind.rewKindsOf κ)

                                          The classical rewriting, retagged to ColKind.rewKindsOf κ. AggQueryIn.rewriting targets ColKind.rewKinds n – the per-index if k < n form – which is only pointwise equal to the uniform Fin.append κ prov the congruences below consume. Retagging once here (semantically the identity) lets a congruence sit directly above the classical base rule instead of threading an explicit retag step.

                                          Equations
                                          Instances For
                                            Dependency graph

                                            The general selection with an aggregate atom #

                                            def GenPredIn.selProvTerm {T : Type} [ValueType T] {K : Type} {n : ℕ} {κ : Fin n → ColKind} (φ : GenPred T κ) :

                                            The provenance column of a rewritten selection whose predicate compares an aggregate column, over an arbitrary rewritten subquery: the predicate's gate term times the row's own provenance column.

                                            No entailment test is needed here, unlike at the fused site (GenPredIn.siteProvTerm): where the predicate entails the group's existence the evaluator drops the pending factor, and the gate term absorbs the δ-guard it left in the provenance column instead (GenPredIn.predsem_absorb_prod). So multiplying by the column is right in both cases, and the test is only the optimization ProvSQL performs.

                                            Equations
                                            Instances For
                                              Dependency graph
                                              def AggQueryIn.selAggCols {T : Type} [ValueType T] {K : Type} {n : ℕ} {κ : Fin n → ColKind} (φ : GenPred T κ) :
                                              Tuple (ProjCol (T ⊕ K) (ColKind.rewKindsOf κ)) (n + 1)

                                              The output columns of a rewritten selection: every data column copied verbatim, whatever its kind, and the predicate's provenance term in the provenance column.

                                              Equations
                                              Instances For
                                                Dependency graph
                                                theorem AggQueryIn.selAggCols_kind {T : Type} [ValueType T] {K : Type} {n : ℕ} {κ : Fin n → ColKind} (φ : GenPred T κ) (j : Fin (n + 1)) :

                                                They have the rewritten kinds of the source.

                                                Dependency graph
                                                def AggQueryIn.selAggRew {T : Type} [ValueType T] {K : Type} {n : ℕ} {κ : Fin n → ColKind} (φ : GenPred T κ) (q' : AggQuery (T ⊕ K) (n + 1) (ColKind.rewKindsOf κ)) :
                                                AggQuery (T ⊕ K) (n + 1) (ColKind.rewKindsOf κ)

                                                The rewritten selection with an aggregate atom, over an arbitrary rewritten subquery: keep every data column and replace the provenance column by the predicate's provenance term.

                                                Equations
                                                Instances For
                                                  Dependency graph

                                                  Correctness of the general selection rewriting, relative to the gate primitives: for a predicate on which the gate algebra is the joint reading (GenPredIn.gateExact), over any rewritten subquery that computes the input's rows. The data columns are copied, and in the provenance column the gate term multiplies the row's finalized annotation, which is the evaluator's own update by GenAnn.finalize_sel – the superseded pending factors being exactly the ones the gate term absorbs.

                                                  Dependency graph
                                                  theorem AggQueryIn.provRel_of_toCompositeRow {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {m : ℕ} {κ' : Fin (m + 1) → ColKind} {κ : Fin m → ColKind} (hprov : κ' (Fin.last m) = ColKind.prov) (qg : AggQuery T m κ) (q' : AggQuery (T ⊕ K) (m + 1) κ') (d : AnnotatedDatabase T K) (hrel : Multiset.map GenRow.toCompositeRow (evaluate qg d) = evaluateRew q' d.toComposite) :

                                                  The grouping's hypothesis, off a rewriting of its input: a rewritten query that computes the subquery's rows computes, in particular, the pairs the token-building grouping reads.

                                                  Dependency graph

                                                  The closure #

                                                  inductive AggQueryIn.RewritesTo {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [HasAltLinearOrder K] {n : ℕ} {κ : Fin n → ColKind} {κ' : Fin (n + 1) → ColKind} :
                                                  AggQuery T n κ → AggQuery (T ⊕ K) (n + 1) κ' → Prop

                                                  The compositional closure of the rewriting rules: the three base rewritings – classical blocks, fused HAVING sites and bare groupings – composed under union, selection, projection, deduplication, product and difference, with the kind-retagging of AggQueryIn.Retag available to adapt a subderivation's output kinds. The HAVING-site rule havingPred keeps the group keys and the aggregate tokens as output columns and admits any predicate with an aggregate atom.

                                                  Instances For
                                                    Dependency graph
                                                    theorem AggQueryIn.rewritesTo_gamma_filter {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus 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₂) (keep : Fin n₂ → Option (Selection T m)) (qg : AggQuery T m (ColKind.allReg m)) (hq : classical qg) :
                                                    ∃ (q' : AggQuery (T ⊕ K) (n₁ + n₂ + 1) (ColKind.gammaRewKinds n₁ n₂)), (Gamma is ts fs qg keep).RewritesTo q'

                                                    A filtered grouping is in the closure. count(*) FILTER (WHERE p) over a classical subquery rewrites like any other grouping: the clause rides into the rewritten plan unchanged (Selection.castToAnnotatedTuple), its aggregate's column becoming an expression over the whole group on both sides (AggExpr.ofGroupWhen_toComposite).

                                                    Dependency graph
                                                    theorem AggQueryIn.rewritesTo_gamma_gamma {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [HasAltLinearOrder K] {lab1 lab2 m m₂ n₁ n₂ p₁ p₂ : ℕ} (is : Tuple (Fin m) n₁) (ts : Tuple (Term T m) n₂) (fs : Tuple (SeqAggFunc T) n₂) (os : Tuple (TermG T (ColKind.gammaKinds n₁ n₂)) m₂) (is' : Tuple (Fin m₂) p₁) (ts' : Tuple (Term T m₂) p₂) (fs' : Tuple (SeqAggFunc T) p₂) (qg : AggQuery T m (ColKind.allReg m)) (hq : classical qg) :
                                                    ∃ (q' : AggQuery (T ⊕ K) (p₁ + p₂ + 1) (ColKind.gammaRewKinds p₁ p₂)), (Gamma is' ts' fs' (Proj (fun (j : Fin m₂) => ProjColIn.term (os j)) (Gamma is ts fs qg))).RewritesTo q'

                                                    A grouping over a grouping is in the closure. The kind discipline asks the inner aggregate column to be read out first – here by a projection of terms, which is what SELECT key, count(*) AS c followed by a grouping of c does in SQL – and the two grouping rules then compose through AggQueryIn.RewritesTo.gammaOf, which the classical gamma rule alone cannot do: its subquery has to be classical, and a grouping is not.

                                                    Dependency graph
                                                    theorem AggQueryIn.rewritesTo_having_over_gamma {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [HasAltLinearOrder K] {lab1 lab2 m m₂ n₁ n₂ p₁ p₂ : ℕ} (is : Tuple (Fin m) n₁) (ts : Tuple (Term T m) n₂) (fs : Tuple (SeqAggFunc T) n₂) (os : Tuple (TermG T (ColKind.gammaKinds n₁ n₂)) m₂) (is' : Tuple (Fin m₂) p₁) (ts' : Tuple (Term T m₂) p₂) (fs' : Tuple (SeqAggFunc T) p₂) (φ : GenPred T (ColKind.gammaKinds p₁ p₂)) (hφ : GenPredIn.hasAggAtom φ = true) (hrf : GenPredIn.gateExact φ = true) (qg : AggQuery T m (ColKind.allReg m)) (hq : classical qg) :
                                                    ∃ (q' : AggQuery (T ⊕ K) (p₁ + p₂ + 1) (ColKind.rewKindsOf (ColKind.gammaKinds p₁ p₂))), (Sel φ (Gamma is' ts' fs' (Proj (fun (j : Fin m₂) => ProjColIn.term (os j)) (Gamma is ts fs qg))) ⋯).RewritesTo q'

                                                    A HAVING over a grouping of a grouping is in the closure. Two rules the closure did not have before reach it: the grouping over an arbitrary rewriting (gammaOf) and the selection with an aggregate atom over an arbitrary rewriting (selAgg). The fused site rule cannot – its input has to be classical – and the aggregate-free sel rule cannot either, the predicate comparing a token.

                                                    Dependency graph
                                                    theorem AggQueryIn.rewritesTo_valid {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {n : ℕ} {κ : Fin n → ColKind} {κ' : Fin (n + 1) → ColKind} {q : AggQuery T n κ} {q' : AggQuery (T ⊕ K) (n + 1) κ'} (h : RewritesTo q q') (d : AnnotatedDatabase T K) :

                                                    Whole-query correctness of the compositional rewriting: along the closure, the general evaluator's rows, embedded token-aware into the composite domain, are exactly the rewritten world's evaluation.

                                                    Dependency graph
                                                    theorem AggQueryIn.rewritesTo_valid_reg {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {n : ℕ} {κ : Fin n → ColKind} {κ' : Fin (n + 1) → ColKind} {q : AggQuery T n κ} {q' : AggQuery (T ⊕ K) (n + 1) κ'} (h : RewritesTo q q') (hκ : ∀ (k : Fin n), κ k = ColKind.reg) (d : AnnotatedDatabase T K) :
                                                    Multiset.map (fun (t : Tuple (T ⊕ K) (n + 1)) (k : Fin (n + 1)) => Sum.inl (t k)) (evaluateAnnotated q d).toComposite = evaluateRew q' d.toComposite

                                                    On an all-regular source the correctness specializes to the shape of the classical and HAVING-site statements: the annotated semantics, folded into composite tuples and embedded by inl.

                                                    Dependency graph