Documentation

Provenance.AggQueryBridges

Regression bridges for the general evaluator #

The fused HAVING operator is recovered from the decomposed general syntax: on its fragment – one aggregate comparison directly above the grouping – the general evaluator σ_ψ ∘ Gamma computes exactly the fused semantics in closed form (AggQueryIn.havingSite_evaluateAnnotated). Row by row, the pending group factor introduced by Gamma is superseded by the predicate provenance of the comparison (the token's predProv, which is the fused Having.havingProv by AggValue.predProv_ofGroup), and the data part collapses to the whole-group aggregate values.

Every theorem about the fused semantics – the possible-world collapses of Provenance.HavingSemantics, the query-level correctness results – is therefore stated directly against the general evaluator, with this closed form as the working lemma; no separate fused evaluator is needed. The kind transport AggQueryIn.castKind is transparent to evaluation (AggQueryIn.evaluate_castKind).

def TermIn.toGenKey {T : Type} {n₁ : ℕ} (n₂ : ℕ) :
Term T n₁ → TermG T (ColKind.gammaKinds n₁ n₂)

A term over the group key, embedded as a term over the key columns of a Gamma output.

Equations
Instances For
    Dependency graph
    theorem AggValue.annList_ofGroup {T : Type} [ValueType T] {K : Type} {c m : ℕ} (f : SeqAggFunc T) (t : TermIn T c m) (U : List (AnnotatedTuple T K m)) {γ : Fin c → T} :

    The annotation list of a group token is the group's annotation list.

    Dependency graph
    def GenPredIn.fusedCmp {T : Type} {n₁ n₂ : ℕ} (op : CompOp) (l : Fin n₂) (s : Term T n₁) :

    The fused aggregate comparison, as a generalized selection atom on a Gamma output: the l-th token column compared against a term over the group key.

    Equations
    Instances For
      Dependency graph
      @[reducible, inline]
      abbrev AggQueryIn.havingSite {T : Type} {m n₁ n₂ : ℕ} (is : Tuple (Fin m) n₁) (ts : Tuple (Term T m) n₂) (fs : Tuple (SeqAggFunc T) n₂) (op : CompOp) (l : Fin n₂) (s : Term T n₁) (qg : AggQuery T m (ColKind.allReg m)) :
      AggQuery T (n₁ + n₂) (ColKind.gammaKinds n₁ n₂)

      The fused HAVING site as a general query: one aggregate comparison directly above the grouping.

      Equations
      Instances For
        Dependency graph
        theorem AggQueryIn.havingSite_evaluateAnnotated {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {m n₁ n₂ : ℕ} (is : Tuple (Fin m) n₁) (ts : Tuple (Term T m) n₂) (fs : Tuple (SeqAggFunc T) n₂) (op : CompOp) (l : Fin n₂) (s : Term T n₁) (qg : AggQuery T m (ColKind.allReg m)) (d : AnnotatedDatabase T K) :
        evaluateAnnotated (havingSite is ts fs op l s qg) d = Multiset.map (fun (g : Fin n₁ → T) => (Fin.append g fun (k : Fin n₂) => fs k (List.map (fun (p : AnnotatedTuple T K m) => TermIn.eval (ts k) p.1) (Having.havingGroup is (evaluateAnnotated qg d) g)), Having.havingProv (Having.havingGroup is (evaluateAnnotated qg d) g) (ts l) (fs l) op (TermIn.eval s g))) (Multiset.map (fun (p : AnnotatedTuple T K m) (k : Fin n₁) => p.1 (is k)) (evaluateAnnotated qg d)).dedup

        Closed form of the fused HAVING site. On its fragment – one aggregate comparison directly above the grouping – the general evaluator produces one row per group key of the subquery, carrying the key followed by the whole-group aggregate values and annotated by the predicate provenance Having.havingProv of the group's occurrence sequence. This is what makes the fused site a theorem rather than a semantics of its own: the pending group factor introduced by Gamma is superseded by the comparison's predicate provenance, and the data part collapses to the whole-group aggregate values.

        Dependency graph

        A predicate over two groups keeps both groups' factors #

        The general evaluator drops a pending group factor only where every compared token carries that group's annotation list. A predicate reading two groups therefore removes nothing: both factors stay pending, and GenAnn.finalize cashes them into the row's annotation.

        This is what keeps the ⊕ of a disjunction from ever being read on its own. The predicate provenance of φ₁ ∨ φ₂ over two groups can be non-𝟘 in worlds where neither group is read at all – 𝔹 with both disjuncts on ⊤ is the instance – and it is the factors the row keeps that make the row's annotation 𝟘 there.

        theorem AggQueryIn.evaluate_Sel_of_two_groups {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {c n : ℕ} {κ : Fin n → ColKind} (φ : GenPredIn T c κ) (q : AggQueryIn T c n κ) (d : AnnotatedDatabase T K) (γ : Fin c → T) (hagg : φ.hasAggAtom = true) (htwo : ∀ r ∈ q.evaluate d γ, ∃ k₁ ∈ φ.comparedCols, ∃ k₂ ∈ φ.comparedCols, ∃ (a₁ : AggTok T K) (a₂ : AggTok T K), r.1 k₁ = Sum.inr a₁ ∧ r.1 k₂ = Sum.inr a₂ ∧ a₁.annList ≠ a₂.annList) :
        (Sel φ q ⋯).evaluate d γ = Multiset.map (fun (r : GenRow T K n) => (r.1, { base := r.2.base * φ.predsemJ false r.1 γ, pending := r.2.pending })) (q.evaluate d γ)
        Dependency graph
        theorem AggQueryIn.evaluate_Sel_or_of_two_groups {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {c n : ℕ} {κ : Fin n → ColKind} {k₁ k₂ : Fin n} (h₁ : κ k₁ = ColKind.agg) (h₂ : κ k₂ = ColKind.agg) (op₁ op₂ : CompOp) (t₁ t₂ : TermGIn T c κ) (q : AggQueryIn T c n κ) (d : AnnotatedDatabase T K) (γ : Fin c → T) (hdis : ∀ r ∈ q.evaluate d γ, ∃ (a₁ : AggTok T K) (a₂ : AggTok T K), r.1 k₁ = Sum.inr a₁ ∧ r.1 k₂ = Sum.inr a₂ ∧ a₁.annList ≠ a₂.annList) :
        (Sel ((GenPredIn.aggCmp k₁ h₁ op₁ t₁).or (GenPredIn.aggCmp k₂ h₂ op₂ t₂)) q ⋯).evaluate d γ = Multiset.map (fun (r : GenRow T K n) => (r.1, { base := r.2.base * ((GenPredIn.aggCmp k₁ h₁ op₁ t₁).or (GenPredIn.aggCmp k₂ h₂ op₂ t₂)).predsemJ false r.1 γ, pending := r.2.pending })) (q.evaluate d γ)

        The disjunction of two aggregate atoms over two groups keeps both group factors. The instance of AggQueryIn.evaluate_Sel_of_two_groups the ∨ rule is about: the row's annotation is the disjunction's ⊕ times every group's pending factor, never the ⊕ alone.

        Dependency graph

        A projection that keeps every group's tokens changes nothing #

        The projection clause cashes the pending factors of the groups whose token columns it drops. Where it drops none – a reordering, a renaming, anything keeping every token column a pending factor belongs to – the concrete part and the pending part come through untouched, so such a projection standing inside a chain of aggregate selections changes neither the families the chain reads nor the annotation it builds.

        theorem AggQueryIn.evaluate_Proj_of_pending_le {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {c n m : ℕ} {κ : Fin n → ColKind} (ps : Fin m → ProjColIn T c κ) (q : AggQueryIn T c n κ) (d : AnnotatedDatabase T K) (γ : Fin c → T) (h : ∀ r ∈ q.evaluate d γ, r.2.pending ≤ tokenLists fun (j : Fin m) => (ps j).eval r.1 γ) :
        (Proj ps q).evaluate d γ = Multiset.map (fun (r : GenRow T K n) => (fun (j : Fin m) => (ps j).eval r.1 γ, r.2)) (q.evaluate d γ)
        Dependency graph

        Equality up to impossible rows #

        A tuple annotated 𝟘 holds in no world, so an implementation is free to drop it. Two annotated relations that agree after that removal say the same thing about every world, and some equalities between query spellings hold only in that sense.

        Dropping the impossible rows: what is left of an annotated relation when the tuples annotated 𝟘 – those in no world – are removed. (Not AnnotatedRelation.support, which is the 𝔹-specific data-part reading of Provenance.SupportAdequacy.)

        Equations
        Instances For
          Dependency graph

          Equality up to impossible rows.

          This drops 𝟘-annotated tuples only. It is stated on annotated relations, where that is all there is to drop: GenRow.toAnnotated collapses every aggregate column through GenRow.plainTuple, so a finalized relation carries no aggregate value and hence no occurrence annotation. A coarser equivalence that also dropped the 𝟘-annotated occurrences inside aggregate values would differ from this one on GenRows, which still carry their tokens, and coincide with it on everything evaluateAnnotated returns.

          Equations
          Instances For
            Dependency graph
            theorem AggQueryIn.evaluate_Sel_reg_absorb {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {c n : ℕ} {κ : Fin n → ColKind} (op : CompOp) (t₁ t₂ : TermGIn T c κ) (ψ : GenPredIn T c κ) (hψ : ψ.hasAggAtom = true) (q : AggQueryIn T c n κ) (d : AnnotatedDatabase T K) (γ : Fin c → T) :
            ((Sel (GenPredIn.cmp op t₁ t₂) (Sel ψ q ⋯) ⋯).evaluateAnnotated d γ).ZEq ((Sel ((GenPredIn.cmp op t₁ t₂).and ψ) q ⋯).evaluateAnnotated d γ)

            A regular selection may be absorbed into the aggregate predicate below it – up to impossible rows, and not up to equality of relations.

            A selection whose predicate has an aggregate atom keeps every row, annotating the failing ones 𝟘; a selection on regular columns removes them. So the chain and the single selection on the conjunction give the same annotation to every row the regular test keeps, and part on the rows it rejects: gone on one side, present annotated 𝟘 on the other. They therefore have the same support and are not the same relation, which is the equality a normalization rewriting a chain into one predicate can claim and the one it cannot.

            Dependency graph

            Guard absorption and the finalize identities #

            These belong to the evaluator, not to any particular metatheorem: an existence-entailing predicate provenance absorbs the δ-guard of the group it compares, which is what licenses the evaluator's supersede of a pending factor, and the finalize identities say what the three row transformations do to the factored annotation. The homomorphism layer and the rewriting closure both read them.

            Guard absorption #

            The first substantive use of the delta_absorb axiom: an existence-entailing predicate provenance algebraically absorbs its group's δ-guard. Every monomial of the possible-world sum contains some occurrence annotation of the group (the worlds are non-empty), and delta_absorb lets that occurrence swallow δ of the whole group sum.

            The comparison case.

            Dependency graph
            theorem GenPredIn.predsem_delta_absorb {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] {c n : ℕ} {κ : Fin n → ColKind} (φ : GenPredIn T c κ) {γ : Fin c → T} (neg : Bool) (u : Tuple (GenValue T K) n) (ℓ₀ : List K) (huni : ∀ k ∈ φ.comparedCols, ∀ (a : AggTok T K), u k = Sum.inr a → a.scalar = false ∧ a.annList = ℓ₀) (hent : φ.entailsExistence neg = true) :
            φ.predsem neg u γ * SemiringWithMonus.delta ℓ₀.sum = φ.predsem neg u γ

            Guard absorption for entailing predicates: when a predicate entails existence and all its compared tokens carry the annotation list ℓ₀, its predicate provenance absorbs δ(⊕ℓ₀).

            Dependency graph
            theorem GenPredIn.predsem_absorb_prod {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] {c n : ℕ} {κ : Fin n → ColKind} (φ : GenPredIn T c κ) {γ : Fin c → T} (u : Tuple (GenValue T K) n) (hent : φ.entailsExistence false = true) (D : Multiset (List K)) (hD : ∀ l ∈ D, ∀ k ∈ φ.comparedCols, ∀ (a : AggTok T K), u k = Sum.inr a → a.scalar = false ∧ a.annList = l) :
            φ.predsem false u γ * (Multiset.map (fun (l : List K) => SemiringWithMonus.delta l.sum) D).prod = φ.predsem false u γ

            An existence-entailing predicate provenance absorbs the δ-guards of any collection of pending factors, each of which is the occurrence list of every compared token.

            Dependency graph
            theorem GenAnn.finalize_sel {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] {c n : ℕ} {κ : Fin n → ColKind} (φ : GenPredIn T c κ) {γ : Fin c → T} (u : Tuple (GenValue T K) n) (b : K) (P C Cs : Multiset (List K)) (hC : ∀ k ∈ φ.comparedCols, ∀ (a : AggTok T K), u k = Sum.inr a → a.annList ∈ C) (hCs : ∀ k ∈ φ.comparedCols, ∀ (a : AggTok T K), u k = Sum.inr a → a.scalar = true → a.annList ∈ Cs) (hCex : ∀ l ∈ C, ∃ k ∈ φ.comparedCols, ∃ (a : AggTok T K), u k = Sum.inr a) :
            { base := b * φ.predsemJ false u γ, pending := if φ.entailsExistence false = true then Multiset.filter (fun (l : List K) => ¬(Cs = 0 ∧ C ≠ 0 ∧ ∀ l' ∈ C, l' = l)) P else P }.finalize = φ.predsemJ false u γ * { base := b, pending := P }.finalize

            Selection finalize identity. On each side separately, the annotation produced by an aggregate-atom selection finalizes to the predicate provenance times the input's finalized annotation: kept pending factors commute out, and each superseded factor is absorbed by the predicate provenance, every world it is read in meeting the superseded group. The compared-lists multiset C is abstract; what is used is that every compared token's occurrence list belongs to it and that each of its lists comes from a compared token.

            Dependency graph