Documentation

Provenance.HavingMonotone

Monotone HAVING conditions: absorptivity suffices #

The join-based rewriting of a HAVING condition is correct in every absorptive commutative m-semiring – distributivity of ⊗ over ⊖ not required – as soon as the condition is monotone: a Boolean combination, by ∧ and ∨ only, of atoms whose validity is preserved when occurrences are added to the group. The atoms covered are COUNT(*) ≥ C, COUNT(*) > C (Query.joinCount_monotone_correct, Provenance.HavingQueryCorrectness), and the existential comparisons MIN(t) ≤ c, MIN(t) < c, MAX(t) ≥ c, MAX(t) > c, which hold in a world iff it contains a qualifying occurrence (Having.Existential).

The base query has the (key, value, identifier) schema of Provenance.HavingQueryCorrectness, with the group key in column #0.

Comparison atoms as selection predicates #

Dependency graph

Existential atoms: ε(Π_{#0}(σ_{t op c}(q))) #

def atomSel (t : Term ℕ 3) (op : CompOp) (c : ℕ) :

The selection predicate t op c of an existential atom.

Equations
Instances For
    Dependency graph
    def existentialQuery (t : Term ℕ 3) (op : CompOp) (c : ℕ) (q : Query ℕ 3) :

    The rewriting ε(Π_{#0}(σ_{t op c}(q))) of an existential comparison f(t) op c: the group keys of the qualifying occurrences, duplicate- eliminated.

    Equations
    Instances For
      Dependency graph
      theorem existentialQuery_source (t : Term ℕ 3) (op : CompOp) (c : ℕ) (q : Query ℕ 3) (hq : q.source) :
      Dependency graph
      theorem existential_perKey {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] (h_abs : absorptive K) {f : SeqAggFunc ℕ} {op : CompOp} (hf : Having.Existential f op) (q : Query ℕ 3) (hq : q.source) (d : AnnotatedDatabase ℕ K) (ts : Tuple (Term ℕ 3) 1) (c : ℕ) (g : Tuple ℕ 1) :
      (Multiset.map Prod.snd (Multiset.filter (fun (p : Tuple ℕ 1 × K) => p.1 = g) ((existentialQuery (ts 0) op c q).evaluateAnnotated ⋯ d))).sum = Having.havingProv (Having.havingGroup keyIdx (q.evaluateAnnotated hq d) g) (ts 0) f op c

      Existential atoms, per key. In an absorptive commutative m-semiring, the existential rewriting gives every group key the fused f(t) op c predicate provenance of its group, for any existential comparison (MIN with ≤/<, MAX with ≥/>). No distributivity of ⊗ over ⊖ is assumed (Having.havingProv_existential).

      Dependency graph
      theorem existential_site_rewrite {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] (h_abs : absorptive K) {f : SeqAggFunc ℕ} {op : CompOp} (hf : Having.Existential f op) (q : Query ℕ 3) (hq : q.source) (d : AnnotatedDatabase ℕ K) (ts' : Tuple (Term ℕ 3) 1) (c : ℕ) :
      Multiset.map (fun (p : AnnotatedTuple ℕ K (1 + 1)) => (fun (x : Fin 1) => p.1 ⟨0, existential_site_rewrite._proof_2⟩, p.2)) (AggQueryIn.evaluateAnnotated (AggQueryIn.havingSite keyIdx ts' (fun (x : Fin 1) => f) op 0 (TermIn.const c) (q.toAgg hq)) d) = (keyPadded (existentialQuery (ts' 0) op c) q).evaluateAnnotated ⋯ d

      Site substitution for existential atoms. In every absorptive commutative m-semiring, the key-projected fused HAVING f(t) op c site and the padded rewriting ε(Π_{#0}(σ_{t op c}(q))) evaluate to the same multiset of annotated tuples, for any existential comparison.

      Dependency graph

      MIN(t) ≤ c.

      Dependency graph
      Dependency graph

      MAX(t) ≥ c.

      Dependency graph
      Dependency graph

      Boolean closure: join on the group key and set union #

      A conjunction of conditions is rewritten as the join of the two rewritings on the group key, ε(Π_{#0}(σ_{#0 = #1}(Q₁ × Q₂))), and a disjunction as their set union ε(Q₁ ⊎ Q₂). Per key, the join multiplies and the union adds the annotations, which is exactly how the fused semantics (HavingPred.prov) interprets ∧ and ∨.

      The key-equality predicate #0 = #1 on a pair of one-column rows.

      Equations
      Instances For
        Dependency graph
        def pairKey :
        Tuple (Term ℕ 2) 1

        The projection of a pair of one-column rows to its first column.

        Equations
        Instances For
          Dependency graph
          def keyJoinInner (Q₁ Q₂ : Query ℕ 1) :

          The key-equality selection over the product, σ_{#0 = #1}(Q₁ × Q₂).

          Equations
          Instances For
            Dependency graph
            def keyJoin (Q₁ Q₂ : Query ℕ 1) :

            Join on the group key, ε(Π_{#0}(σ_{#0 = #1}(Q₁ × Q₂))).

            Equations
            Instances For
              Dependency graph
              def keyUnion (Q₁ Q₂ : Query ℕ 1) :

              Set union, ε(Q₁ ⊎ Q₂).

              Equations
              Instances For
                Dependency graph
                theorem keyJoin_source (Q₁ Q₂ : Query ℕ 1) (h₁ : Q₁.source) (h₂ : Q₂.source) :
                (keyJoin Q₁ Q₂).source
                Dependency graph
                theorem keyUnion_source (Q₁ Q₂ : Query ℕ 1) (h₁ : Q₁.source) (h₂ : Q₂.source) :
                (keyUnion Q₁ Q₂).source
                Dependency graph

                The row of a product: appended data parts, multiplied annotations.

                Equations
                Instances For
                  Dependency graph
                  theorem keyJoin_perKeySum {K : Type} [CommSemiringWithMonus K] [DecidableEq K] (Q₁ Q₂ : Query ℕ 1) (h₁ : Q₁.source) (h₂ : Q₂.source) (d : AnnotatedDatabase ℕ K) (g : Tuple ℕ 1) :
                  (Multiset.map Prod.snd (Multiset.filter (fun (p : Tuple ℕ 1 × K) => p.1 = g) ((keyJoin Q₁ Q₂).evaluateAnnotated ⋯ d))).sum = (Multiset.map Prod.snd (Multiset.filter (fun (p : Tuple ℕ 1 × K) => p.1 = g) (Q₁.evaluateAnnotated h₁ d))).sum * (Multiset.map Prod.snd (Multiset.filter (fun (p : Tuple ℕ 1 × K) => p.1 = g) (Q₂.evaluateAnnotated h₂ d))).sum

                  Join on the key multiplies the per-key annotations.

                  Dependency graph
                  theorem keyUnion_perKeySum {K : Type} [CommSemiringWithMonus K] [DecidableEq K] (Q₁ Q₂ : Query ℕ 1) (h₁ : Q₁.source) (h₂ : Q₂.source) (d : AnnotatedDatabase ℕ K) (g : Tuple ℕ 1) :
                  (Multiset.map Prod.snd (Multiset.filter (fun (p : Tuple ℕ 1 × K) => p.1 = g) ((keyUnion Q₁ Q₂).evaluateAnnotated ⋯ d))).sum = (Multiset.map Prod.snd (Multiset.filter (fun (p : Tuple ℕ 1 × K) => p.1 = g) (Q₁.evaluateAnnotated h₁ d))).sum + (Multiset.map Prod.snd (Multiset.filter (fun (p : Tuple ℕ 1 × K) => p.1 = g) (Q₂.evaluateAnnotated h₂ d))).sum

                  Set union adds the per-key annotations.

                  Dependency graph

                  Monotone conditions and their compositional rewriting #

                  inductive MonoCond (n₂ : ℕ) :

                  Monotone HAVING conditions over the aggregate columns of a grouping: COUNT(*) ≥ C + 1 and COUNT(*) > C + 1 on the token column l, an existential comparison f(t) op c on the token column l, and conjunctions and disjunctions. Negation is excluded: it flips monotonicity.

                  Instances For
                    Dependency graph
                    def MonoCond.WF {n₂ : ℕ} (fs : Tuple (SeqAggFunc ℕ) n₂) :
                    MonoCond n₂ → Prop

                    Well-formedness with respect to the aggregates fs of the grouping: the COUNT(*) atoms sit on COUNT(*) columns and the existential atoms on existential aggregate/operator pairs (MIN with ≤/<, MAX with ≥/>, see Having.Existential).

                    Equations
                    Instances For
                      Dependency graph
                      def MonoCond.toHavingPred {n₂ : ℕ} (ts : Tuple (Term ℕ 3) n₂) (fs : Tuple (SeqAggFunc ℕ) n₂) :
                      MonoCond n₂ → HavingPred ℕ 3 1

                      The condition as a Boolean combination of fused aggregate comparisons, whose provenance is HavingPred.prov (∧ ↦ ⊗, ∨ ↦ ⊕).

                      Equations
                      Instances For
                        Dependency graph
                        def MonoCond.rewrite {n₂ : ℕ} (ts : Tuple (Term ℕ 3) n₂) :
                        MonoCond n₂ → Query ℕ 3 → Query ℕ 1

                        The compositional positive rewriting Q_ψ: COUNT(*) atoms become the join chains Q₂^{≥ C}, existential atoms ε(Π_{#0}(σ_{t op c}(q))), a conjunction the join of the two rewritings on the group key, and a disjunction their set union.

                        Equations
                        Instances For
                          Dependency graph
                          theorem MonoCond.rewrite_source {n₂ : ℕ} (ts : Tuple (Term ℕ 3) n₂) (q : Query ℕ 3) (hq : q.source) (ψ : MonoCond n₂) :
                          (rewrite ts ψ q).source
                          Dependency graph

                          The fused site of a compound condition, in the general evaluator #

                          The condition as a generalized selection predicate over the output of Gamma: each atom compares its token column against a constant (GenPredIn.fusedCmp), and ∧/∨ are the Boolean connectives of GenPred.

                          Equations
                          Instances For
                            Dependency graph
                            def MonoCond.isAtom {n₂ : ℕ} :
                            MonoCond n₂ → Bool

                            A single comparison. The general evaluator reads a combination of comparisons of one group in one world of that group (GenPredIn.predsemJ), while HavingPred.prov reads ∧ as ⊗ and ∨ as ⊕; the two agree on one comparison (toGenPred_predsemJ), and that is where the fused site is related to the evaluator.

                            Equations
                            Instances For
                              Dependency graph
                              @[reducible, inline]
                              abbrev MonoCond.site {n₂ : ℕ} (ts : Tuple (Term ℕ 3) n₂) (fs : Tuple (SeqAggFunc ℕ) n₂) (ψ : MonoCond n₂) (qg : AggQuery ℕ 3 (ColKind.allReg 3)) :
                              AggQuery ℕ (1 + n₂) (ColKind.gammaKinds 1 n₂)

                              The fused site σ_ψ(γ_{#0}[ts : fs](qg)) of a monotone condition, as a general query.

                              Equations
                              Instances For
                                Dependency graph
                                theorem MonoCond.toGenPred_predsemJ {K : Type} [CommSemiringWithMonus K] [DecidableEq K] {n₂ : ℕ} (u : Tuple (GenValue ℕ K) (1 + n₂)) (γ : Fin 0 → ℕ) (ψ : MonoCond n₂) :

                                On one comparison the evaluator's joint reading is the structural one.

                                Dependency graph
                                theorem MonoCond.site_evaluateAnnotated {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {n₂ : ℕ} (ts : Tuple (Term ℕ 3) n₂) (fs : Tuple (SeqAggFunc ℕ) n₂) (ψ : MonoCond n₂) (hψ : ψ.isAtom = true) (qg : AggQuery ℕ 3 (ColKind.allReg 3)) (d : AnnotatedDatabase ℕ K) :

                                Closed form of the fused site of a monotone condition. 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 fused provenance HavingPred.prov of the condition on the group's occurrence sequence: the pending group factor introduced by Gamma is superseded by the compared tokens (every atom compares a token of that very group). Stated for one comparison (MonoCond.isAtom), where the evaluator's joint reading of the condition is its fused provenance.

                                Dependency graph
                                theorem MonoCond.site_rewrite {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {n₂ : ℕ} (h_abs : absorptive K) (ts : Tuple (Term ℕ 3) n₂) (fs : Tuple (SeqAggFunc ℕ) n₂) (ψ : MonoCond n₂) (hψ : ψ.isAtom = true) (hwf : WF fs ψ) (q : Query ℕ 3) (hq : q.source) (d : AnnotatedDatabase ℕ K) (hnodup : (Multiset.map Prod.fst (q.evaluateAnnotated hq d)).Nodup) :
                                Multiset.map (fun (p : AnnotatedTuple ℕ K (1 + n₂)) => (fun (x : Fin 1) => p.1 ⟨0, ⋯⟩, p.2)) (AggQueryIn.evaluateAnnotated (site ts fs ψ (q.toAgg hq)) d) = (keyPadded (rewrite ts ψ) q).evaluateAnnotated ⋯ d

                                Site substitution for monotone conditions: absorptivity suffices. In every absorptive commutative m-semiring – distributivity of ⊗ over ⊖ not required – the key-projected fused site σ_ψ(γ_{#0}[ts : fs](q)) of a well-formed comparison ψ and the padded compositional rewriting Q_ψ evaluate to the same multiset of annotated tuples: the rewriting can be substituted for the key-projected fused operator inside any surrounding query. The sole hypothesis on the instance is the global row-distinctness of the base query's output (the occurrence identifiers of the COUNT(*) join chains).

                                Dependency graph