Documentation

Provenance.HavingProbability

Probability identities for HAVING aggregate comparisons under independence #

This file formalizes the algebraic identities for evaluating HAVING-style aggregate comparisons when the contributors are independent. Given a B[X]-instance in which each contributor i : ι carries an annotation α i : BoolFunc X and the annotations have pairwise disjoint variable supports (so the contributors are independent Bernoullis with marginals p i = P.funcProb (α i)), we give closed-form / recurrence expressions for the probability that the aggregate-comparison atom holds on the contributors of a single group:

All four results follow the same template: the underlying event factors as a Boolean combination of the per-contributor indicators, and the disjoint-supports hypothesis turns that combination into a product of marginal probabilities via ProbAssignment.funcProb_mul_disjoint.

Common setup for the four results #

We fix a probability assignment P over Boolean variables X, a finite type ι of contributors, an annotation α : ι → BoolFunc X, supports S : ι → Finset X that are pairwise disjoint, and a hypothesis hdep : ∀ i, (α i).DependsOn (S i). The contributor marginal is p i := P.funcProb (α i).

MAX factorization #

def HavingProbability.maxNoneAbove {X ι : Type} [Fintype ι] (α : ι → BoolFunc X) {V : Type} [LinearOrder V] (t : ι → V) (C : V) :

“Random world contains no contributor with value > C”: the AND over the indicators 1 - α i for all contributors with t i > C. Evaluates to true iff every such contributor's annotation is false.

Equations
Instances For
    Dependency graph
    def HavingProbability.someAtMost {X ι : Type} [Fintype ι] (α : ι → BoolFunc X) {V : Type} [LinearOrder V] (t : ι → V) (C : V) :

    “Random world contains some contributor with value ≤ C”: the OR over the indicators α i for all contributors with t i ≤ C, expressed as 1 - ∏ (1 - α i).

    Equations
    Instances For
      Dependency graph
      def HavingProbability.maxLeOnNonempty {X ι : Type} [Fintype ι] (α : ι → BoolFunc X) {V : Type} [LinearOrder V] (t : ι → V) (C : V) :

      “Random world is nonempty and max_{i ∈ world} t i ≤ C”: the conjunction of the two pieces above. The semantic meaning is recorded in maxLeOnNonempty_eval_iff.

      Equations
      Instances For
        Dependency graph
        theorem HavingProbability.funcProb_maxLeOnNonempty {X : Type} [Fintype X] [DecidableEq X] {ι : Type} [Fintype ι] [DecidableEq ι] (P : ProbAssignment X) (α : ι → BoolFunc X) {V : Type} [LinearOrder V] (t : ι → V) (S : ι → Finset X) (hdep : ∀ (i : ι), (α i).DependsOn (S i)) (hdisj : Set.univ.Pairwise fun (i j : ι) => Disjoint (S i) (S j)) (C : V) :
        P.funcProb (maxLeOnNonempty α t C) = (∏ i : ι with C < t i, (1 - P.funcProb (α i))) * (1 - ∏ i : ι with t i ≤ C, (1 - P.funcProb (α i)))

        MAX factorization under independence. The probability of the “max ≤ C on a nonempty world” event factors as a product of an “all above-C contributors are absent” term and a “some at-most-C contributor is present” term.

        Dependency graph

        MIN factorization #

        def HavingProbability.minNoneBelow {X ι : Type} [Fintype ι] (α : ι → BoolFunc X) {V : Type} [LinearOrder V] (t : ι → V) (C : V) :

        “Random world contains no contributor with value < C”: the AND over the indicators 1 - α i for all contributors with t i < C.

        Equations
        Instances For
          Dependency graph
          def HavingProbability.someAtLeast {X ι : Type} [Fintype ι] (α : ι → BoolFunc X) {V : Type} [LinearOrder V] (t : ι → V) (C : V) :

          “Random world contains some contributor with value ≥ C”.

          Equations
          Instances For
            Dependency graph
            def HavingProbability.minGeOnNonempty {X ι : Type} [Fintype ι] (α : ι → BoolFunc X) {V : Type} [LinearOrder V] (t : ι → V) (C : V) :

            “Random world is nonempty and min_{i ∈ world} t i ≥ C”.

            Equations
            Instances For
              Dependency graph
              theorem HavingProbability.funcProb_minGeOnNonempty {X : Type} [Fintype X] [DecidableEq X] {ι : Type} [Fintype ι] [DecidableEq ι] (P : ProbAssignment X) (α : ι → BoolFunc X) {V : Type} [LinearOrder V] (t : ι → V) (S : ι → Finset X) (hdep : ∀ (i : ι), (α i).DependsOn (S i)) (hdisj : Set.univ.Pairwise fun (i j : ι) => Disjoint (S i) (S j)) (C : V) :
              P.funcProb (minGeOnNonempty α t C) = (∏ i : ι with t i < C, (1 - P.funcProb (α i))) * (1 - ∏ i : ι with C ≤ t i, (1 - P.funcProb (α i)))

              MIN factorization under independence.

              Dependency graph

              COUNT (Poisson-binomial) recurrence #

              def HavingProbability.countEqIndicator {X ι : Type} (α : ι → BoolFunc X) (J : Finset ι) (j : ℕ) :

              Indicator BoolFunc: evaluates to true at a valuation v iff exactly j of the indices i ∈ J have α i v = true.

              Equations
              Instances For
                Dependency graph
                theorem HavingProbability.countMass_insert_succ {X : Type} [Fintype X] [DecidableEq X] {ι : Type} [Fintype ι] [DecidableEq ι] (P : ProbAssignment X) (α : ι → BoolFunc X) (S : ι → Finset X) (hdep : ∀ (i : ι), (α i).DependsOn (S i)) (hdisj : Set.univ.Pairwise fun (i j : ι) => Disjoint (S i) (S j)) {i : ι} {J : Finset ι} (hi : i ∉ J) (j : ℕ) :
                P.funcProb (countEqIndicator α (insert i J) (j + 1)) = (1 - P.funcProb (α i)) * P.funcProb (countEqIndicator α J (j + 1)) + P.funcProb (α i) * P.funcProb (countEqIndicator α J j)

                COUNT Poisson-binomial recurrence (succ case). For i ∉ J and j : ℕ, the probability that exactly j + 1 of the contributors in insert i J are present factors as (1 − p i) · ρ_J(j+1) + p i · ρ_J(j).

                Dependency graph
                theorem HavingProbability.countMass_insert_zero {X : Type} [Fintype X] [DecidableEq X] {ι : Type} [Fintype ι] [DecidableEq ι] (P : ProbAssignment X) (α : ι → BoolFunc X) (S : ι → Finset X) (hdep : ∀ (i : ι), (α i).DependsOn (S i)) (hdisj : Set.univ.Pairwise fun (i j : ι) => Disjoint (S i) (S j)) {i : ι} {J : Finset ι} (hi : i ∉ J) :
                P.funcProb (countEqIndicator α (insert i J) 0) = (1 - P.funcProb (α i)) * P.funcProb (countEqIndicator α J 0)

                COUNT Poisson-binomial recurrence (zero case). For i ∉ J, the probability that exactly 0 contributors in insert i J are present is (1 − p i) · ρ_J(0).

                Dependency graph

                SUM (weighted Poisson-binomial) recurrence #

                def HavingProbability.sumEqIndicator {X ι : Type} (α : ι → BoolFunc X) (t : ι → ℕ) (J : Finset ι) (s : ℕ) :

                Indicator BoolFunc: evaluates to true at a valuation v iff the sum of t i over indices i ∈ J with α i v = true equals s.

                Equations
                Instances For
                  Dependency graph
                  theorem HavingProbability.sumMass_insert_of_le {X : Type} [Fintype X] [DecidableEq X] {ι : Type} [Fintype ι] [DecidableEq ι] (P : ProbAssignment X) (α : ι → BoolFunc X) (t : ι → ℕ) (S : ι → Finset X) (hdep : ∀ (i : ι), (α i).DependsOn (S i)) (hdisj : Set.univ.Pairwise fun (i j : ι) => Disjoint (S i) (S j)) {i : ι} {J : Finset ι} (hi : i ∉ J) {s : ℕ} (hs : t i ≤ s) :
                  P.funcProb (sumEqIndicator α t (insert i J) s) = (1 - P.funcProb (α i)) * P.funcProb (sumEqIndicator α t J s) + P.funcProb (α i) * P.funcProb (sumEqIndicator α t J (s - t i))

                  SUM weighted Poisson-binomial recurrence (weight fits). For i ∉ J and t i ≤ s, the probability that the weighted sum over insert i J equals s factors as (1 − p i) · σ_J(s) + p i · σ_J(s − t i).

                  Dependency graph

                  The remaining MIN / MAX comparison operators #

                  funcProb_maxLeOnNonempty and funcProb_minGeOnNonempty treat MAX ≤ C and MIN ≥ C. The remaining comparisons all follow from two generic events: guardedSome r q – “no present contributor satisfies r, and some present contributor satisfies q” – and its unguarded special case someOf q. Under the disjoint-supports hypothesis, their probabilities factor exactly as before, and each remaining comparison is an instance:

                  and dually for MIN.

                  def HavingProbability.noneOf {X ι : Type} [Fintype ι] (α : ι → BoolFunc X) (r : ι → Prop) [DecidablePred r] :

                  “No present contributor satisfies r”: AND of the negated indicators over the contributors satisfying r.

                  Equations
                  Instances For
                    Dependency graph
                    def HavingProbability.someOf {X ι : Type} [Fintype ι] (α : ι → BoolFunc X) (q : ι → Prop) [DecidablePred q] :

                    “Some present contributor satisfies q”: OR of the indicators over the contributors satisfying q, expressed as 1 - ∏ (1 - α i).

                    Equations
                    Instances For
                      Dependency graph
                      def HavingProbability.guardedSome {X ι : Type} [Fintype ι] (α : ι → BoolFunc X) (r q : ι → Prop) [DecidablePred r] [DecidablePred q] :

                      “No present contributor satisfies r, and some present contributor satisfies q”. Every MIN/MAX aggregate comparison on non-empty random worlds is an instance of this event.

                      Equations
                      Instances For
                        Dependency graph
                        def HavingProbability.maxLtOnNonempty {X ι : Type} [Fintype ι] (α : ι → BoolFunc X) {V : Type} [LinearOrder V] (t : ι → V) (C : V) :

                        “Non-empty random world with MAX(t) < C”.

                        Equations
                        Instances For
                          Dependency graph
                          def HavingProbability.maxEqOnNonempty {X ι : Type} [Fintype ι] (α : ι → BoolFunc X) {V : Type} [LinearOrder V] (t : ι → V) (C : V) :

                          “Non-empty random world with MAX(t) = C”.

                          Equations
                          Instances For
                            Dependency graph
                            def HavingProbability.someAbove {X ι : Type} [Fintype ι] (α : ι → BoolFunc X) {V : Type} [LinearOrder V] (t : ι → V) (C : V) :

                            “Random world with MAX(t) > C” (such a world is non-empty).

                            Equations
                            Instances For
                              Dependency graph
                              def HavingProbability.someBelow {X ι : Type} [Fintype ι] (α : ι → BoolFunc X) {V : Type} [LinearOrder V] (t : ι → V) (C : V) :

                              “Random world with MAX(t) < C” (such a world is non-empty).

                              Equations
                              Instances For
                                Dependency graph
                                def HavingProbability.maxNeOnNonempty {X ι : Type} [Fintype ι] (α : ι → BoolFunc X) {V : Type} [LinearOrder V] (t : ι → V) (C : V) :

                                “Non-empty random world with MAX(t) ≠ C”: disjoint union of MAX < C and MAX > C.

                                Equations
                                Instances For
                                  Dependency graph
                                  def HavingProbability.minGtOnNonempty {X ι : Type} [Fintype ι] (α : ι → BoolFunc X) {V : Type} [LinearOrder V] (t : ι → V) (C : V) :

                                  “Non-empty random world with MIN(t) > C”.

                                  Equations
                                  Instances For
                                    Dependency graph
                                    def HavingProbability.minEqOnNonempty {X ι : Type} [Fintype ι] (α : ι → BoolFunc X) {V : Type} [LinearOrder V] (t : ι → V) (C : V) :

                                    “Non-empty random world with MIN(t) = C”.

                                    Equations
                                    Instances For
                                      Dependency graph
                                      def HavingProbability.minNeOnNonempty {X ι : Type} [Fintype ι] (α : ι → BoolFunc X) {V : Type} [LinearOrder V] (t : ι → V) (C : V) :

                                      “Non-empty random world with MIN(t) ≠ C”: disjoint union of MIN < C (i.e., some contributor below C is present) and MIN > C.

                                      Equations
                                      Instances For
                                        Dependency graph

                                        CDF assembly for COUNT #

                                        The recurrences countMass_insert_zero / countMass_insert_succ compute the point masses ρ_J(j). The results below assemble them into the probability of an arbitrary comparison: the satisfying counts form a subset of {0, …, |J|} (an interval, for the six comparison operators) and the corresponding point masses add; the empty-world mass is ∏ (1 - p i); and the upper tail can be computed as a lower tail of the complemented contributors (Pr[B ≥ C] = Pr[B' ≤ N − C]), which is the shorter of the two summations when C > N/2.

                                        theorem HavingProbability.funcProb_count_filter {X : Type} [Fintype X] [DecidableEq X] {ι : Type} [Fintype ι] [DecidableEq ι] (P : ProbAssignment X) (α : ι → BoolFunc X) (J : Finset ι) (g : ℕ → Prop) [DecidablePred g] :
                                        (P.funcProb fun (v : X → Bool) => decide (g {i ∈ J | α i v = true}.card)) = ∑ j ∈ Finset.range (J.card + 1) with g j, P.funcProb (countEqIndicator α J j)

                                        CDF assembly. For any predicate g on counts, the probability that the number of present contributors satisfies g is the sum of the point masses ρ_J(j) over the satisfying counts j ∈ {0, …, |J|}. For the six comparison operators the satisfying set is an interval.

                                        Dependency graph

                                        The possible-world HAVING provenance under a valuation #

                                        The predicate provenance of an aggregate comparison (Having.havingProv, over 𝔹[X]) is a ⊕-sum of one disjunct per non-empty possible world. Under a fixed valuation of the Boolean variables, exactly one disjunct survives: the one of the realized world, formed of the occurrences whose annotation is true. Consequently the predicate provenance evaluates to true exactly when the realized world is non-empty and satisfies the comparison – the bridge between the intensional possible-world semantics and probabilistic query evaluation: the probability of the predicate provenance is the probability that the realized world is non-empty and satisfies the comparison.

                                        The section culminates in booleanHaving_pqe: for a Boolean query made of a Boolean combination of aggregate comparisons (HavingPred) applied on top of a non-aggregation query over a tuple-independent probabilistic database, the probability that a random world satisfies the query (booleanHavingProb, via the plain semantics HavingPred.modelsBoolean) equals the probability of its Boolean provenance (HavingPred.booleanProv). The non-aggregation operators are handled by randomWorld_evaluateAnnotated and the comparisons by the exactly-one-disjunct bridge, composed through the sorted-sublist identity groupSeq_randomWorld between the plain group sequence of a random world and the realized subsequence of the annotated group sequence.

                                        def HavingProbability.realizedWorld {X T : Type} {m : ℕ} (U : List (AnnotatedTuple T (BoolFunc X) m)) (v : X → Bool) :

                                        The world realized by a valuation v: the positions of the group sequence whose annotation evaluates to true under v.

                                        Equations
                                        Instances For
                                          Dependency graph
                                          noncomputable def HavingProbability.booleanHavingProb {X : Type} [Fintype X] [DecidableEq X] (P : ProbAssignment X) {T : Type} [ValueType T] {m n₁ : ℕ} (q : Query T m) (Î : AnnotatedDatabase T (BoolFunc X)) (is : Tuple (Fin m) n₁) (ψ : HavingPred T m n₁) :

                                          Probability that a random world of Î satisfies a Boolean HAVING query: the sum of Pr(v) over the valuations whose possible world does.

                                          Equations
                                          Instances For
                                            Dependency graph