Documentation

Provenance.HavingSemantics

Possible-world semantics of the fused Having operator #

This file gives the K-annotated semantics of the fused HAVING operator Query.Having – a grouping γ^≼ whose output is filtered by a comparison between an aggregate value and a regular term – in an arbitrary commutative m-semiring, together with the bridge between its possible worlds and the Finset-of-positions representation on which the algebraic development of Provenance.Having and Provenance.HavingMinMax is built.

Possible worlds #

The occurrences of a group are extracted as a sequence U (a list of annotated tuples, ordered by the canonical lexicographic order – the ordering ≼ along which non-commutative aggregates read their input, with an arbitrary fixed tie-break on the annotations). A possible world of U is a subsequence W ⊑ U; its annotation is, in factored form,

ann_U(W) = (⊗_{(u,α) ∈ W} α) ⊗ (𝟙 ⊖ ⊕_{(u,α) ∈ U∖W} α).

The bridge #

Formally, worlds are represented as sets of positions W : Finset (Fin U.length); seqOf U W is the subsequence of U they select. This representation is faithful: seqOf U W is always a sublist of U (seqOf_sublist), every sublist arises this way (sublist_eq_seqOf), and when the occurrences of U are pairwise distinct the correspondence is a bijection (seqOf_injective). Because annotations and aggregate values factor through positions, the possible-world ⊕-sum below is taken over Finset (Fin U.length) – which is exactly the index representation used by Provenance.Having – and the whole algebraic development attaches to the semantics through worldAnn_eq_T and havingProv_eq_prov (and, for the ≥ comparisons, which need no distributivity, through worldAnn_eq_ann).

The semantics #

For a group with occurrence sequence U and an atomic aggregate comparison f(t) op s, the predicate provenance is

⊕_{∅ ≠ W ⊑ U} ann_U(W) ⊗ χ_op(agg_{t,f}(W), s(g)),

where agg_{t,f}(W) applies the sequence aggregate f to the t-values of the occurrences of W (in order) and χ_op sends a true comparison to 𝟙 and a false one to 𝟘. The sum ranges over non-empty worlds only, so it already enforces group existence. The general evaluator's HAVING site (AggQueryIn.havingSite, in Provenance.AggQueryBridges) has exactly this closed form: one row per group of the inner query, whose data part carries the group key and the (whole-group) aggregate values, and whose annotation is the predicate provenance of its group. Boolean combinations of aggregate comparisons are interpreted by HavingPred.prov: ∧ ↦ ⊗, ∨ ↦ ⊕, and ¬ is pushed to the atoms by De Morgan duality, complementing the comparison operator of an atom (as in ProvSQL's implementation).

Positions and subsequences: the bridge #

def Having.seqOf {β : Type} (U : List β) :
Finset (Fin U.length) → List β

The subsequence of U selected by a set of positions, in order.

Equations
Instances For
    Dependency graph

    The world annotation, in factored form #

    def Having.worldAnn {K : Type} [CommSemiringWithMonus K] {N : ℕ} (α : Fin N → K) (W : Finset (Fin N)) :
    K

    The K-annotation of a possible world, in the factored form of the possible-world semantics: the product of the annotations of the kept occurrences times 𝟙 ⊖ the sum of the annotations of the discarded ones. worldAnn_eq_T normalizes it into the Having.T form used by the algebraic development.

    Equations
    Instances For
      Dependency graph
      theorem Having.worldAnn_eq_T {K : Type} [CommSemiringWithMonus K] (h_distrib : mul_sub_left_distributive K) {N : ℕ} (α : Fin N → K) (W : Finset (Fin N)) :

      In an m-semiring where ⊗ left-distributes over ⊖, the factored world annotation coincides with the exactly-W contribution Having.T over the full universe of positions. This is the only place the distributivity hypothesis enters the correspondence between the semantics and the query-free algebra; cf. ChainFive, where the two forms differ.

      Dependency graph
      def Having.relAnn {K : Type} [CommSemiringWithMonus K] {N : ℕ} (α : Fin N → K) (S W : Finset (Fin N)) :
      K

      The annotation a world gives the part of an occurrence family lying in S: the product of the annotations it keeps there against the monus of those it drops there. worldAnn is the case S = univ, and the point of the relative form is that it composes.

      Equations
      Instances For
        Dependency graph
        theorem Having.worldAnn_split {K : Type} [CommSemiringWithMonus K] (hc : complemented K) {N : ℕ} (α : Fin N → K) (S W : Finset (Fin N)) :
        worldAnn α W = (∏ i ∈ W ∩ S, α i) * (1 - ∑ i ∈ S \ W, α i) * ((∏ i ∈ W ∩ Sᶜ, α i) * (1 - ∑ i ∈ Sᶜ \ W, α i))

        A world's annotation splits along a partition of its family when the semiring is complemented: the occurrences inside S and those outside contribute independently. It is what lets a predicate whose atoms read disjoint families be evaluated atom by atom rather than over the union of the families, and complemented is exactly what it needs – the product part splits in any semiring, the 𝟙 ⊖ · part only there.

        Dependency graph
        theorem Having.sum_split {K : Type} [CommSemiringWithMonus K] {N : ℕ} (S : Finset (Fin N)) (F : Finset (Fin N) → Finset (Fin N) → K) :
        ∑ W : Finset (Fin N), F (W ∩ S) (W ∩ Sᶜ) = ∑ A ∈ S.powerset, ∑ B ∈ Sᶜ.powerset, F A B

        Summing over the worlds of a family is summing over the pairs of worlds of its two halves.

        Dependency graph
        theorem Having.sum_mul_sum_of_split {K : Type} [CommSemiringWithMonus K] (hc : complemented K) {N : ℕ} (α : Fin N → K) (S : Finset (Fin N)) (χ₁ χ₂ : Finset (Fin N) → K) :
        (∑ A ∈ S.powerset, relAnn α S A * χ₁ A) * ∑ B ∈ Sᶜ.powerset, relAnn α Sᶜ B * χ₂ B = ∑ W : Finset (Fin N), worldAnn α W * (χ₁ (W ∩ S) * χ₂ (W ∩ Sᶜ))

        Two atoms reading disjoint families may be read one at a time. The product of the two families' world-sums is the single sum over the worlds of their union, when the semiring is complemented – which is what makes worldAnn split and is the only thing this needs of K.

        It is the disjoint half of the ∧ rule: over one family the product is not that sum, and what it takes there is exclusivity with an idempotent ⊗ (AggValue.predProvOf_mul_predProvOf).

        Dependency graph
        theorem Having.sum_mul_sum_of_overlap {K : Type} [CommSemiringWithMonus K] (hc : complemented K) (hexcl : exclusive K) (hidem : mulIdempotent K) {N : ℕ} (α : Fin N → K) (V₁ V₂ : Finset (Fin N)) (χ₁ χ₂ : Finset (Fin N) → K) :
        (∑ A ∈ V₁.powerset, relAnn α V₁ A * χ₁ A) * ∑ B ∈ V₂.powerset, relAnn α V₂ B * χ₂ B = ∑ W ∈ (V₁ ∪ V₂).powerset, relAnn α (V₁ ∪ V₂) W * (χ₁ (W ∩ V₁) * χ₂ (W ∩ V₂))

        Two atoms reading families that overlap without being equal. The product of the two families' world-sums is the single sum over the worlds of their union, under the hypotheses of both settled regimes, each on the part it governs: complemented splits the two private parts off, and exclusivity with an idempotent ⊗ collapses the shared part, which each side reads. The disjoint case is the one where the shared part is empty, the same-family case the one where the private parts are.

        Dependency graph
        theorem Having.worldAnn_mul_eq_zero_of_ne {K : Type} [CommSemiringWithMonus K] (hexcl : exclusive K) {N : ℕ} (α : Fin N → K) {W W' : Finset (Fin N)} (h : W ≠ W') :
        worldAnn α W * worldAnn α W' = 0

        Distinct worlds of one occurrence family annihilate each other, in an exclusive m-semiring. A position kept by one world and dropped by the other contributes a factor α u to the first annotation and a factor 𝟙 ⊖ (α u ⊕ …) to the second, and exclusivity makes that pair 𝟘.

        This is what makes the alternatives of an occurrence mutually exclusive when an aggregate value is read as a key, and the same identity governs the worlds of a frame that contains its current row. It fails in How (How.not_exclusive), which is the universal semiring every provenance circuit is built in, so the spurious terms are carried by the circuit and die only on evaluation into an exclusive semiring, homomorphisms commuting with ⊖.

        Dependency graph

        Group extraction and aggregate values #

        def Having.havingGroup {T : Type} [ValueType T] {K : Type} {m n₁ : ℕ} [HasAltLinearOrder K] (is : Tuple (Fin m) n₁) (r : AnnotatedRelation T K m) (g : Tuple T n₁) :

        The occurrence sequence U^≼ of the group of key g: the annotated tuples of r whose grouping columns match g, as a list sorted by the lexicographic order on annotated tuples – by the canonical order on the value part first (the ordering ≼ along which the group sequence is read), then by the alternative order of HasAltLinearOrder on the annotation, an arbitrary fixed tie-break, matching the possible-world semantics where occurrences with equal value parts are ordered arbitrarily.

        Equations
        Instances For
          Dependency graph
          theorem Having.havingGroup_coe {T : Type} [ValueType T] {K : Type} {m n₁ : ℕ} [HasAltLinearOrder K] (is : Tuple (Fin m) n₁) (r : AnnotatedRelation T K m) (g : Tuple T n₁) :
          ↑(havingGroup is r g) = Multiset.filter (fun (p : AnnotatedTuple T K m) => ∀ (k' : Fin n₁), p.1 (is k') = g k') r

          The group sequence is a permutation of the group multiset: as a multiset, havingGroup is r g is the sub-multiset of r matching the key g.

          Dependency graph
          def Having.aggValOn {T : Type} [ValueType T] {K : Type} {m : ℕ} (U : List (AnnotatedTuple T K m)) (t : Term T m) (f : SeqAggFunc T) (W : Finset (Fin U.length)) :
          T

          The aggregate value of f over the term t in the world W: f applied to the sequence of t-values of the kept occurrences, in order. No algebraic structure on f is required.

          Equations
          Instances For
            Dependency graph
            def Having.aggValOnWhen {T : Type} [ValueType T] {K : Type} {m : ℕ} (U : List (AnnotatedTuple T K m)) (keep : Tuple T m → Bool) (t : Term T m) (f : SeqAggFunc T) (W : Finset (Fin U.length)) :
            T

            The value a group's token takes in a world under a FILTER clause: the aggregate of the term over the occurrences of that world the clause keeps. aggValOn is the case of a clause that keeps everything (aggValOnWhen_of_all).

            The clause cuts the sequence, and that is the only reading that works for all three of SQL's input policies. A null-skipping aggregate and a count can be made to drop the rejected occurrences by nulling their term out instead – that is filterTerm, and aggValOn_filterTerm_sqlOf/_counting say the two readings agree there – but a null-keeping aggregate reads the null as a value, so for it the rejected occurrence has to leave the sequence and no term can arrange that (FilterCounterexample.filterTerm_ne_aggValOnWhen).

            Equations
            Instances For
              Dependency graph

              Predicate provenance #

              def Having.chi {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] (op : CompOp) (a b : T) :
              K

              χ_op: the characteristic value of a comparison, 𝟙 if it holds and 𝟘 otherwise – and 𝟘 also when it is unknown, a comparison with a NULL operand being neither true nor false. A row on which a comparison is unknown is selected by neither the comparison nor its negation, and contributes nothing to either provenance.

              Equations
              Instances For
                Dependency graph
                def Having.chiOf {T K : Type} [CommSemiringWithMonus K] (P : T → Kleene) (a : T) :
                K

                χ_P: the characteristic value of an arbitrary three-valued test on a value, 𝟙 where the test is true and 𝟘 where it is false or unknown. chi is the case of a comparison against a constant, and the general form is what an atom carrying a test – a range, for one – reads its token through.

                Equations
                Instances For
                  Dependency graph
                  def Having.havingProv {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] {m : ℕ} (U : List (AnnotatedTuple T K m)) (t : Term T m) (f : SeqAggFunc T) (op : CompOp) (c : T) :
                  K

                  Predicate provenance of an atomic aggregate comparison on the occurrence sequence U of one group: the ⊕-sum, over the non-empty possible worlds of U, of the world annotation times the characteristic value of the comparison between the aggregate value in the world and the regular value c. The sum ranges over non-empty worlds only: it thereby already enforces group existence, which is why the fused selection semantics drops the annotation of the grouped row itself.

                  Equations
                  Instances For
                    Dependency graph
                    theorem Having.havingProv_count_ge {K : Type} [CommSemiringWithMonus K] {m : ℕ} (h_abs : absorptive K) (U : List (AnnotatedTuple ℕ K m)) (t : Term ℕ m) (C : ℕ) :
                    havingProv U t SeqAggFunc.count CompOp.ge (C + 1) = S (fun (i : Fin U.length) => (U.get i).2) Finset.univ (C + 1)

                    COUNT(*) ≥ C case of the fused semantics. In an absorptive m-semiring, the predicate provenance of COUNT(*) ≥ C + 1 on the group sequence U is the join-side Having.S, the ⊕-sum of the monomials of the worlds of size exactly C + 1. Unlike the = and ≤ cases, no distributivity of ⊗ over ⊖ is needed: the factored world annotations are summed directly through Having.Fann_eq_S, whose proof never rewrites them into the Having.T form.

                    Dependency graph
                    theorem Having.havingProv_count_ge_one {K : Type} [CommSemiringWithMonus K] {m : ℕ} (h_abs : absorptive K) (U : List (AnnotatedTuple ℕ K m)) (t : Term ℕ m) :

                    COUNT(*) ≥ 1 collapses to the group annotation sum. In an absorptive m-semiring, the fused COUNT(*) ≥ 1 predicate provenance of a group sequence is the ⊕-sum of the annotations of its occurrences (the C = 1 instance of the join correspondence: S_1 is the sum of the singleton monomials).

                    Dependency graph

                    Existential aggregate comparisons: MIN and MAX #

                    A comparison f(t) op c is existential when, on a non-empty sequence, it holds iff some element of the sequence satisfies x op c: this is the case of MIN(t) ≤ c, MIN(t) < c, MAX(t) ≥ c and MAX(t) > c. The valid worlds of such a comparison are those meeting the set of qualifying occurrences, and Having.sum_ann_meet collapses the predicate provenance to the ⊕-sum of the qualifying occurrences' annotations, in every absorptive m-semiring and without distributivity of ⊗ over ⊖.

                    def Having.Existential {T : Type} [ValueType T] (f : SeqAggFunc T) (op : CompOp) :

                    A sequence aggregate f is existential for the comparison op when, on non-empty sequences, f L op c holds iff some element x of L satisfies x op c.

                    Equations
                    Instances For
                      Dependency graph
                      def Having.ExistentialOn {T : Type} [ValueType T] (f : SeqAggFunc T) (op : CompOp) (c : T) (P : T → Prop) :

                      An aggregate comparison is existential in a predicate on values: on a non-empty sequence, f L op c is true exactly when some element of L satisfies P.

                      Equations
                      Instances For
                        Dependency graph
                        def Having.Existential3 {T : Type} [ValueType T] (f : SeqAggFunc T) (op : CompOp) :

                        An aggregate comparison is existential, read three-valuedly: on a non-empty sequence, f L op c is true exactly when some element x of L makes x op c true. This is the reading SQL's aggregates need: the aggregate skips the nulls while the comparison is unknown on them, and both readings agree on this – an occurrence whose value is null neither reaches the aggregate nor satisfies the comparison.

                        Equations
                        Instances For
                          Dependency graph
                          theorem Having.havingProv_existential {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] {m : ℕ} [NoNulls T] (h_abs : absorptive K) {f : SeqAggFunc T} {op : CompOp} (hf : Existential f op) (U : List (AnnotatedTuple T K m)) (t : Term T m) (c : T) :
                          havingProv U t f op c = (Multiset.map Prod.snd (Multiset.filter (fun (p : AnnotatedTuple T K m) => op.eval (TermIn.eval t p.1) c) ↑U)).sum

                          The same over a domain where nothing is null, the comparison then being two-valued.

                          Dependency graph

                          SQL's aggregates are existential too #

                          MIN and MAX as SQL reads them skip the nulls and answer NULL over what is left of nothing. That does not disturb the collapse: the values the aggregate skips are exactly the values a strict comparison is unknown on, so the occurrences that qualify are the same either way.

                          Boolean combinations of aggregate comparisons #

                          inductive HavingPred (T : Type) (m n₁ : ℕ) :

                          Boolean combinations of fused aggregate comparisons: atoms compare a sequence aggregate of a term over the group to a regular term over the group key; combinations are negation, conjunction and disjunction.

                          Instances For
                            Dependency graph
                            def HavingPred.provAux {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] {m n₁ : ℕ} (U : List (AnnotatedTuple T K m)) (g : Tuple T n₁) (negated : Bool) :
                            HavingPred T m n₁ → K

                            Worker for HavingPred.prov, carrying the polarity of the enclosing negations (mirroring ProvSQL's rewriting of HAVING predicates, which pushes NOT through Boolean combinations by De Morgan duality and complements the comparison operator at the leaves). Under negated, conjunction becomes ⊕, disjunction becomes ⊗, and an atom's operator is complemented; since χ_op is {𝟘, 𝟙}-valued, complementing the operator is the same as interpreting ¬ world-wise inside the possible-world sum, which keeps the nonempty-world guard (an outer 𝟙 ⊖ · interpretation would instead hold on worlds where the group is empty, although the grouping outputs no row there).

                            Equations
                            Instances For
                              Dependency graph
                              def HavingPred.prov {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] {m n₁ : ℕ} (U : List (AnnotatedTuple T K m)) (g : Tuple T n₁) (ψ : HavingPred T m n₁) :
                              K

                              Predicate provenance of a Boolean combination of aggregate comparisons, on the occurrence sequence U of the group of key g: conjunction is interpreted by ⊗, disjunction by ⊕, and negation by pushing it to the atoms (De Morgan duality, complementing the comparison operator of an atom), as ProvSQL does.

                              Equations
                              Instances For
                                Dependency graph
                                def HavingPred.evalOnSeq {T : Type} [ValueType T] {m n₁ : ℕ} (L : List (Tuple T m)) (g : Tuple T n₁) :
                                HavingPred T m n₁ → Kleene

                                Three-valued evaluation of a HAVING predicate on one possible world: a plain occurrence sequence L (the tuples of one group, in ≼-order) with group key g. An atom applies the sequence aggregate to the t-values of L and compares with the regular term evaluated on the key, in Kleene's three-valued logic – a comparison with a NULL operand is neither true nor false. ∧, ∨ and ¬ are Kleene's.

                                Equations
                                Instances For
                                  Dependency graph
                                  def HavingPred.holdsOnSeq {T : Type} [ValueType T] {m n₁ : ℕ} (L : List (Tuple T m)) (g : Tuple T n₁) (ψ : HavingPred T m n₁) :

                                  The groups a HAVING predicate keeps in one world: those on which it is true. A group on which it is unknown is kept by neither the predicate nor its negation.

                                  Equations
                                  Instances For
                                    Dependency graph
                                    @[instance_reducible]
                                    instance HavingPred.decidableHoldsOnSeq {T : Type} [ValueType T] {m n₁ : ℕ} (L : List (Tuple T m)) (g : Tuple T n₁) (ψ : HavingPred T m n₁) :
                                    Equations
                                    Dependency graph
                                    def HavingPred.modelsBoolean {T : Type} [ValueType T] {m n₁ : ℕ} (d : Database T) (q : Query T m) (is : Tuple (Fin m) n₁) (ψ : HavingPred T m n₁) :

                                    Plain possible-world satisfaction of a Boolean HAVING query: the query grouping the output of q by the columns is and keeping the groups satisfying ψ holds on the database d iff some realized group key satisfies ψ – equivalently, iff its output is non-empty.

                                    Equations
                                    Instances For
                                      Dependency graph
                                      @[instance_reducible]
                                      instance HavingPred.decidableModelsBoolean {T : Type} [ValueType T] {m n₁ : ℕ} (d : Database T) (q : Query T m) (is : Tuple (Fin m) n₁) (ψ : HavingPred T m n₁) :
                                      Equations
                                      • One or more equations did not get rendered due to their size.
                                      Dependency graph
                                      def HavingPred.booleanProv {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] {m n₁ : ℕ} [HasAltLinearOrder K] (q : Query T m) (hq : q.source) (d : AnnotatedDatabase T K) (is : Tuple (Fin m) n₁) (ψ : HavingPred T m n₁) :
                                      K

                                      Boolean provenance of a Boolean HAVING query – the ⊕-sum of the annotations of the output rows of σ_ψ(γ^≼(q)): one summand per distinct group key of the inner query, carrying the predicate provenance of its group.

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