Documentation

Provenance.AggQueryHavingRewriting

The rewritten world's evaluator: tokens as ordinary column values #

ProvSQL evaluates rewritten plans over a value universe that contains, next to the regular values and the provenance identifiers, the aggregate tokens produced by its provsql_agg gate; the provsql_having gate then reads a token and produces the predicate provenance of an aggregate comparison. The formal counterpart is the evaluator AggQueryIn.evaluateRew defined here: it runs a rewritten query (a AggQuery over the composite value type T ⊕ K) over rows Tuple (GenValue (T ⊕ K) K) n – the lifted-column carrier of the general evaluator, instantiated at the composite value type – with the kind vector saying which columns hold tokens.

The rewriting rules built on this evaluator live downstream: Provenance.AggQueryGroupRewriting (the bare grouping and the HAVING site) and Provenance.AggQueryClosure (the compositional closure).

Terms and predicates in the rewritten world #

def Sum.annPart {T K : Type} [CommSemiringWithMonus K] :
T ⊕ K → K

The annotation part of a composite value (𝟘 on data values: a malformed provenance read carries no worlds).

Equations
Instances For
    Dependency graph
    noncomputable def TermGIn.evalRew {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {c n : ℕ} {κ : Fin n → ColKind} :
    TermGIn (T ⊕ K) c κ → Tuple (GenValue (T ⊕ K) K) n → (γ : optParam (Fin c → T ⊕ K) fun (x : Fin c) => 0) → T ⊕ K

    Term evaluation in the rewritten world: as TermGIn.eval on the value-reading constructors, with the cmpAgg gate interpreted by the predicate provenance of the token against the comparison term, and the chiGate gate by the characteristic value of its comparison.

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

      Projection-column evaluation in the rewritten world.

      Equations
      Instances For
        Dependency graph
        noncomputable def GenPredIn.evalRew3 {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {c n : ℕ} {κ : Fin n → ColKind} :
        GenPredIn (T ⊕ K) c κ → Tuple (GenValue (T ⊕ K) K) n → (γ : optParam (Fin c → T ⊕ K) fun (x : Fin c) => 0) → Kleene

        Three-valued evaluation of a predicate in the rewritten world (compared tokens read through their deterministic collapse, as in GenPredIn.eval3).

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

          The rows a selection keeps in the rewritten world: those on which the predicate is true.

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

            Structural decidability of holdsRew.

            Equations
            Instances For
              Dependency graph
              @[instance_reducible]
              noncomputable instance GenPredIn.instDecidableHoldsRew {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {c n : ℕ} {κ : Fin n → ColKind} (φ : GenPredIn (T ⊕ K) c κ) (γ : Fin c → T ⊕ K) (u : Tuple (GenValue (T ⊕ K) K) n) :
              Equations
              Dependency graph
              def AggExprFun.projComposite {T : Type} [ValueType T] {K : Type} :
              (Fin 1 → T ⊕ K) → T ⊕ K

              The reading a one-leaf expression of the rewritten world carries: the leaf's value, normalized through the data arm.

              Every aggregate the rewriting emits is data-valued, being lifted from the source's (SeqAggFunc.liftComposite), so the normalization is a no-op on what actually arises. What it buys is that the column is equal to the composite transport of the source's: AggExpr.toComposite lifts an expression's own function the same way, and a bare projection would read alike but not be the same data.

              Equations
              Instances For
                Dependency graph
                def AggExpr.ofGroupWhenRew {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [HasAltLinearOrder K] {c m : ℕ} (f : SeqAggFunc (T ⊕ K)) (t : TermIn (T ⊕ K) c m) (keep : Tuple (T ⊕ K) m → Bool) (U : List (AnnotatedTuple (T ⊕ K) K m)) (γ : Fin c → T ⊕ K := fun (x : Fin c) => 0) :
                AggExpr (T ⊕ K) K

                A filtered aggregate of a group, in the rewritten world: the expression AggQueryIn.GammaTok builds for an aggregate carrying a FILTER clause – one leaf over the whole group, the clause cutting only what it reads – with the reading the composite transport carries.

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

                  The evaluator #

                  noncomputable def AggQueryIn.evaluateRew {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {c n : ℕ} {κ : Fin n → ColKind} {l : List (String × ℕ)} :
                  AggQueryIn (T ⊕ K) c n κ l → Database (T ⊕ K) → (γ : optParam (Fin c → T ⊕ K) fun (x : Fin c) => 0) → Multiset (Tuple (GenValue (T ⊕ K) K) n)

                  The rewritten world's evaluator: plain multiset semantics over token-bearing rows. Value-kinded operators act through the inl embedding; GammaTok builds tokens and the group guard; the gates inside terms are interpreted by predProvOf and Having.chi.

                  Equations
                  Instances For
                    Dependency graph

                    Agreement with the plain semantics off the gates #

                    def AggQueryIn.noGammaTok {T' : Type} {c n : ℕ} {κ : Fin n → ColKind} {l : List (String × ℕ)} :
                    AggQueryIn T' c n κ l → Prop

                    No token-building grouping: together with gate-freeness, this cuts out the fragment on which the rewritten world's evaluator is the plain semantics through the inl embedding.

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

                      No indicator gate anywhere in a query's terms and predicates.

                      Equations
                      Instances For
                        Dependency graph
                        theorem AggQueryIn.evaluateRew_plain {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {c n : ℕ} {κ : Fin n → ColKind} {l : List (String × ℕ)} (q : AggQueryIn (T ⊕ K) c n κ l) (_hq : q.noGammaTok) (_hc : q.chiFree) (D : Database (T ⊕ K)) (γ : Fin c → T ⊕ K) :
                        q.evaluateRew D γ = Multiset.map (fun (t : Tuple (T ⊕ K) n) (k : Fin n) => Sum.inl (t k)) (q.evaluatePlain D γ)

                        Plain agreement. Off the token-building operator, the rewritten world's evaluator is the plain semantics through the inl embedding.

                        Dependency graph

                        The fused predicate provenance under the composite embedding #

                        The rewritten site groups composite rows – the inl-embedded data with the annotation appended as the provenance column – while the annotated site groups the original annotated tuples. The fused predicate provenance is invariant under this embedding: comparisons restrict along inl, the lifted aggregate computes on the embedded values, and the occurrence annotations are read off unchanged.

                        Lift a sequence aggregate to the composite domain (junk on the annotation arm, faithful on inl-embedded values).

                        Equations
                        Instances For
                          Dependency graph
                          def NestedValue.liftComposite {T : Type} [ValueType T] {K : Type} (f : Multiset T → T) :
                          Multiset (T ⊕ K) → T ⊕ K

                          The same lift for an aggregate of a bag – a nested value's outer aggregate, which reads no sequence.

                          Equations
                          Instances For
                            Dependency graph

                            The classical rewriting stays off the token operators #

                            theorem AggQueryIn.rewriting_chiFree {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [HasAltLinearOrder K] {c n : ℕ} {κ : Fin n → ColKind} {l : List (String × ℕ)} (q : AggQueryIn T c n κ l) (hq : q.classical) :

                            The classical rewriting emits no indicator gate: its terms are column reads, their ⊗/⊖ combinations, and composite casts of the source terms – the gate is introduced only by the HAVING site.

                            Dependency graph

                            The group sequence under the composite embedding #

                            theorem Having.havingGroup_toComposite {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [HasAltLinearOrder K] {m n₁ : ℕ} (is : Tuple (Fin m) n₁) (r : AnnotatedRelation T K m) (g : Tuple T n₁) :
                            (havingGroup (fun (k : Fin n₁) => Fin.castLE ⋯ (is k)) (Multiset.map (fun (p : AnnotatedTuple T K m) => (p.toComposite, p.2)) r) fun (k : Fin n₁) => Sum.inl (g k)) = List.map (fun (p : AnnotatedTuple T K m) => (p.toComposite, p.2)) (havingGroup is r g)

                            The group sequence under the composite embedding: embedding the relation and the key inl-wise embeds the group sequence. The embedding is monotone for the sort's tie-break order (data columns compare on the inl arm, the appended provenance column and the annotation both by the alternative order), and sorted lists of the same multiset are unique.

                            Dependency graph

                            Reading a rewritten evaluation back as an annotated relation #

                            theorem AggQueryIn.rewriting_provRel {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {n : ℕ} {κ : Fin n → ColKind} (q : AggQuery T n κ) (hq : classical q) (d : AnnotatedDatabase T K) :

                            The rewritten world reads back as an annotated relation. Pairing the collapsed data columns of the rewritten evaluation of a classical rewriting with the annotation read off its provenance column recovers the composite embedding of the classical annotated semantics – the input the token-building groupings of the rewritten world consume.

                            Dependency graph