Documentation

Provenance.HavingQueryCorrectness

Query-level correctness of the fused HAVING operator vs the JOIN rewriting #

This file proves the query-level correspondence between the possible-world semantics of the fused HAVING COUNT(*) operator and its JOIN-based rewriting, in absorptive commutative m-semirings. The monotone comparisons ≥ and > need nothing more (Query.joinCount_monotone_correct); the comparisons <, ≤, =, ≠, which involve a difference of two chains, also need ⊗ to distribute over ⊖ (Query.joinCount_correct).

The proof of the general case runs through three layers: the pure chain algebra (chainAgg, summing to the elementary symmetric sum esymm of the group's annotations over any strictly increasing enumeration), the per-key evaluation invariant of the join chain (joinChain_eval_filter), and the collapse of the fused semantics (Having.havingProv_count_ge with S_eq_esymm).

theorem groupByKey_eq_dedup_map {T : Type} [ValueType T] {K : Type} [SemiringWithMonus K] [DecidableEq K] {n : ℕ} (r : AnnotatedRelation T K n) :
↑↑(groupByKey r) = Multiset.map (fun (u : Tuple T n) => (u, (Multiset.map Prod.snd (Multiset.filter (fun (p : AnnotatedTuple T K n) => p.1 = u) r)).sum)) (Multiset.map Prod.fst r).dedup

Extensional characterization of duplicate elimination. groupByKey produces exactly one row per distinct key of the input, whose annotation is the ⊕-sum of the annotations of the matching rows.

Dependency graph
theorem AggQueryIn.havingSite_count_ge_one {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] (h_abs : absorptive K) {m n₁ : ℕ} (is : Tuple (Fin m) n₁) (ts : Tuple (Term ℕ m) 1) (q : Query ℕ m) (hq : q.source) (d : AnnotatedDatabase ℕ K) :
Multiset.map (fun (p : AnnotatedTuple ℕ K (n₁ + 1)) => (fun (k : Fin n₁) => p.1 (Fin.castAdd 1 k), p.2)) (evaluateAnnotated (havingSite is ts ![SeqAggFunc.count] CompOp.ge 0 (TermIn.const 1) (q.toAgg hq)) d) = (ε ((Π fun (k : Fin n₁) => #(is k)) q)).evaluateAnnotated hq d

Query-level correctness for COUNT(*) ≥ 1. In an absorptive commutative m-semiring (no distributivity of ⊗ over ⊖ is needed), the fused HAVING COUNT(*) ≥ 1 site – with its output rows projected to the group key – computes exactly the duplicate-eliminated key projection ε(Π_{keys}(q)) of the inner query, which is the C = 1 join-based query: one row per non-empty group, annotated by the ⊕-sum of the group's annotations. Stated against any general subquery whose annotated evaluation is the classical inner query's.

Dependency graph

The chain algebra of the C-fold self-join #

The semantic content of the join chain: the annotated strictly increasing chains over a multiset of (value, annotation) pairs, and their ⊕-sum, which is the elementary symmetric sum of the annotations – the multiset form of the join-side provenance Having.S.

def Having.esymm {K : Type} [CommSemiringWithMonus K] (s : Multiset K) (C : ℕ) :
K

The elementary symmetric sum of a multiset of annotations: the ⊕-sum, over the C-element sub-multisets, of their ⊗-products. This is the position-free form of the join-side provenance Having.S (S_eq_esymm).

Equations
Instances For
    Dependency graph
    def Having.chainAgg {V : Type} [LinearOrder V] {K : Type} [CommSemiringWithMonus K] (G : Multiset (V × K)) :
    ℕ → Multiset (V × K)

    The annotated strictly increasing chains of length C + 1 over a multiset G of (value, annotation) pairs, each chain represented by its last value and the ⊗-product of its annotations. This is the semantic content of the C-fold self-join chain of the join-based rewriting.

    Equations
    Instances For
      Dependency graph

      The join chain query and its per-key evaluation #

      The C-fold self-join chain of the join-based rewriting, over an arity-3 base query whose columns are (group key, compared value, occurrence identifier). The identifier column materializes the tie-broken comparison <*: the chain condition compares (value, identifier) pairs lexicographically, so any injective assignment of identifiers within each group realizes an arbitrary resolution of ties between equal values – duplicate values (and duplicate whole occurrences) are fully supported.

      def chainCond (C : ℕ) :
      Selection ℕ (3 * (C + 1) + 3)

      The chain condition relating a new copy of the base query to the last copy of the chain: equal group keys and lexicographically larger (value, identifier) pair – the tie-broken comparison <*.

      Equations
      • One or more equations did not get rendered due to their size.
      Instances For
        Dependency graph
        def joinChain (q : Query ℕ 3) (C : ℕ) :
        Query ℕ (3 * C + 3)

        The C-fold self-join chain: C + 1 copies of the base query, with consecutive copies related by chainCond. Copy j occupies columns 3j, 3j + 1, 3j + 2.

        Equations
        Instances For
          Dependency graph
          theorem joinChain_source (q : Query ℕ 3) (hq : q.source) (C : ℕ) :
          Dependency graph
          def chainCombine {K : Type} [CommSemiringWithMonus K] (C : ℕ) :
          (Tuple ℕ (3 * C + 3) × K) × Tuple ℕ 3 × K → Tuple ℕ (3 * (C + 1) + 3) × K

          The combining map of one chain step: append the new copy's tuple and multiply the annotations.

          Equations
          Instances For
            Dependency graph
            def groupPairs {K : Type} (r : Multiset (Tuple ℕ 3 × K)) (a : ℕ) :

            The (value, identifier) pairs of the group of key a, with their annotations: the chain-algebra view of one group of the base relation.

            Equations
            • One or more equations did not get rendered due to their size.
            Instances For
              Dependency graph
              theorem joinChain_eval_filter {K : Type} [CommSemiringWithMonus K] [DecidableEq K] (q : Query ℕ 3) (hq : q.source) (d : AnnotatedDatabase ℕ K) (a C : ℕ) :
              Multiset.map (fun (p : AnnotatedTuple ℕ K (3 * C + 3)) => (toLex (p.1 ⟨3 * C + 1, ⋯⟩, p.1 ⟨3 * C + 2, ⋯⟩), p.2)) (Multiset.filter (fun (p : AnnotatedTuple ℕ K (3 * C + 3)) => p.1 ⟨0, ⋯⟩ = a) ((joinChain q C).evaluateAnnotated ⋯ d)) = Having.chainAgg (groupPairs (q.evaluateAnnotated hq d) a) C

              Per-key evaluation of the join chain. Within the group of key a, the rows of the C-fold chain, viewed through their last (value, identifier) pair and their annotation, are exactly the annotated strictly increasing chains of length C + 1 of the group.

              Dependency graph

              Assembly: the join-based query computes the fused HAVING provenance #

              theorem q2_source (q : Query ℕ 3) (hq : q.source) (C : ℕ) :
              (ε ((Π fun (x : Fin 1) => #⟨0, ⋯⟩) (joinChain q C))).source
              Dependency graph
              theorem Query.joinChain_count_correct {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] (h_abs : absorptive K) (q : Query ℕ 3) (hq : q.source) (d : AnnotatedDatabase ℕ K) (hnodup : (Multiset.map Prod.fst (q.evaluateAnnotated hq d)).Nodup) (ts : Tuple (Term ℕ 3) 1) (C : ℕ) (g : Tuple ℕ 1) :
              (Multiset.map Prod.snd (Multiset.filter (fun (p : Tuple ℕ 1 × K) => p.1 = g) ((ε ((Π fun (x : Fin 1) => #⟨0, ⋯⟩) (joinChain q C))).evaluateAnnotated ⋯ d))).sum = Having.havingProv (Having.havingGroup (fun (x : Fin 1) => ⟨0, groupPairs._proof_2⟩) (q.evaluateAnnotated hq d) g) (ts 0) SeqAggFunc.count CompOp.ge (C + 1)

              Query-level correctness of the join-based rewriting, general C. In an absorptive commutative m-semiring, for every group key g, the ⊕-sum of the annotations that the join-based query ε(Π_{#0}(joinChain q C)) gives to g equals the fused HAVING COUNT(*) ≥ C + 1 predicate provenance of the group of g. Distributivity of ⊗ over ⊖ is not assumed: the ≥ comparison goes through Having.havingProv_count_ge, hence Having.Fann_eq_S, which never rewrites the factored world annotations into the Having.T form; ChainFive is an absorptive, non-distributive instance where this matters (HavingQueryCounterexamples.ChainFive.query_ge_agree). The hypothesis hnodup states that the occurrence identifiers of the base query's third column make its rows pairwise distinct: it is the formal counterpart of fixing an arbitrary tie-break <* between occurrences with equal compared values, and is satisfiable for every instance (annotate each occurrence with a distinct identifier). The statement is per-key: a group with fewer than C + 1 occurrences has provenance 𝟘 on both sides – the fused operator gives its row a 𝟘 annotation while the join query simply has no row for it.

              Dependency graph
              theorem diff_perKeySum {K : Type} [CommSemiringWithMonus K] [DecidableEq K] {T : Type} [ValueType T] {n : ℕ} (q₁ q₂ : Query T n) (h₁ : q₁.source) (h₂ : q₂.source) (hd : (ε q₁ - q₂).source) (d : AnnotatedDatabase T K) (u : Tuple T n) :
              (Multiset.map Prod.snd (Multiset.filter (fun (p : Tuple T n × K) => p.1 = u) ((ε q₁ - q₂).evaluateAnnotated hd d))).sum = (Multiset.map Prod.snd (Multiset.filter (fun (p : Tuple T n × K) => p.1 = u) ((ε q₁).evaluateAnnotated h₁ d))).sum - (Multiset.map Prod.snd (Multiset.filter (fun (p : Tuple T n × K) => p.1 = u) (q₂.evaluateAnnotated h₂ d))).sum

              Per-key sums through Diff. When the left argument of a difference is duplicate-eliminated (one row per key), the per-key annotation sum of the difference is the monus of the two per-key sums.

              Dependency graph
              def joinChainQuery (q : Query ℕ 3) (C : ℕ) :

              The join-based query for COUNT(*) ≥ C + 1: project the C-fold chain to its group key and eliminate duplicates.

              Equations
              Instances For
                Dependency graph

                Query-level correctness for COUNT(*) = C + 1. The join-based query Q₂^{≥C+1} − Q₂^{≥C+2} gives every group key the fused COUNT(*) = C + 1 predicate provenance.

                Dependency graph

                Query-level correctness for COUNT(*) ≤ C. The join-based query Q₂^{≥1} − Q₂^{≥C+1} gives every group key the fused COUNT(*) ≤ C predicate provenance.

                Dependency graph

                The join-based query realizing COUNT(*) op (C + 1), for each comparison operator op: chains for ≥ and >, differences of two chains for ≤, < and =, and the union of the <- and >-queries for ≠.

                Equations
                Instances For
                  Dependency graph
                  theorem Query.joinCountQuery_source (q : Query ℕ 3) (hq : q.source) (op : CompOp) (C : ℕ) :
                  Dependency graph
                  theorem Query.joinCount_correct {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] (h_abs : absorptive K) (h_distrib : mul_sub_left_distributive K) (q : Query ℕ 3) (hq : q.source) (d : AnnotatedDatabase ℕ K) (hnodup : (Multiset.map Prod.fst (q.evaluateAnnotated hq d)).Nodup) (ts : Tuple (Term ℕ 3) 1) (op : CompOp) (C : ℕ) (g : Tuple ℕ 1) :

                  Query-level correctness of the JOIN rewriting for COUNT(*), for any comparison operator. For every op ∈ {<, ≤, =, ≠, ≥, >}, every threshold C + 1 ≥ 1 and every group key, in an absorptive commutative m-semiring whose ⊗ distributes over ⊖, the join-based query Query.joinCountQuery q op C gives the group key the fused COUNT(*) op (C + 1) predicate provenance. The distributivity hypothesis is used only by the <, ≤, =, ≠ cases; see Query.joinCount_monotone_correct for ≥ and > without it.

                  Dependency graph
                  theorem Query.joinCount_monotone_correct {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] (h_abs : absorptive K) (q : Query ℕ 3) (hq : q.source) (d : AnnotatedDatabase ℕ K) (hnodup : (Multiset.map Prod.fst (q.evaluateAnnotated hq d)).Nodup) (ts : Tuple (Term ℕ 3) 1) (op : CompOp) (hop : op = CompOp.ge ∨ op = CompOp.gt) (C : ℕ) (g : Tuple ℕ 1) :

                  Monotone HAVING conditions need no distributivity. For the comparison operators ≥ and >, the join-based rewriting Query.joinCountQuery q op C is correct in every absorptive commutative m-semiring, whether or not ⊗ distributes over ⊖: the family of worlds satisfying COUNT(*) ≥ C + 1 is upward-closed, so the fused provenance collapses to the monomials of its minimal worlds through Having.Fann_eq_S without ever rewriting the factored world annotations (Having.witness_identity, Having.witness_minimal). This is the ≥/> part of Query.joinCount_correct with the distributivity hypothesis dropped; ChainFive shows the hypothesis cannot be dropped for = (HavingQueryCounterexamples.ChainFive.query_counterexample).

                  Dependency graph