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:
- MAX / MIN factorization
(
funcProb_maxLeOnNonempty,funcProb_minGeOnNonempty):Pr[max ≤ C on nonempty] = (∏_{t i > C}(1 - p i)) · (1 - ∏_{t i ≤ C}(1 - p i))and the dual formin. - COUNT (Poisson-binomial) recurrence
(
countMass_insert_succ,countMass_insert_zero):ρ_{J ⊔ {i}}(j+1) = (1 - p i) · ρ_J(j+1) + p i · ρ_J(j),ρ_{J ⊔ {i}}(0) = (1 - p i) · ρ_J(0). - SUM (weighted Poisson-binomial) recurrence
(
sumMass_insert_of_le,sumMass_insert_of_lt):σ_{J ⊔ {i}}(s) = (1 - p i) · σ_J(s) + p i · σ_J(s - t i)(with the convention thatσ_Jat a negative-shifted index is0).
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 #
“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
- HavingProbability.maxNoneAbove α t C = ∏ i : ι with C < t i, (1 - α i)
Instances For
Dependency graph
“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
- HavingProbability.someAtMost α t C = 1 - ∏ i : ι with t i ≤ C, (1 - α i)
Instances For
Dependency graph
“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
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 #
“Random world contains no contributor with value < C”: the AND over the
indicators 1 - α i for all contributors with t i < C.
Equations
- HavingProbability.minNoneBelow α t C = ∏ i : ι with t i < C, (1 - α i)
Instances For
Dependency graph
“Random world contains some contributor with value ≥ C”.
Equations
- HavingProbability.someAtLeast α t C = 1 - ∏ i : ι with C ≤ t i, (1 - α i)
Instances For
Dependency graph
“Random world is nonempty and min_{i ∈ world} t i ≥ C”.
Equations
Instances For
Dependency graph
MIN factorization under independence.
Dependency graph
COUNT (Poisson-binomial) recurrence #
Indicator BoolFunc: evaluates to true at a valuation v iff exactly
j of the indices i ∈ J have α i v = true.
Instances For
Dependency graph
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
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 #
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.
Instances For
Dependency graph
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:
MAX < C– guardr i := C ≤ t i, witnessq i := t i < C;MAX = C– guardr i := C < t i, witnessq i := t i = C;MAX ≥ C/MAX > C– unguarded witnessq i := C ≤ t i/C < t i(non-emptiness is implied by the witness);MAX ≠ Con non-empty worlds – the disjoint union ofMAX < CandMAX > C, whose probabilities add;
and dually for MIN.
“No present contributor satisfies r”: AND of the negated indicators
over the contributors satisfying r.
Equations
- HavingProbability.noneOf α r = ∏ i : ι with r i, (1 - α i)
Instances For
Dependency graph
“Some present contributor satisfies q”: OR of the indicators over the
contributors satisfying q, expressed as 1 - ∏ (1 - α i).
Equations
- HavingProbability.someOf α q = 1 - ∏ i : ι with q i, (1 - α i)
Instances For
Dependency graph
“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
“Non-empty random world with MAX(t) < C”.
Equations
- HavingProbability.maxLtOnNonempty α t C = HavingProbability.guardedSome α (fun (i : ι) => C ≤ t i) fun (i : ι) => t i < C
Instances For
Dependency graph
“Non-empty random world with MAX(t) = C”.
Equations
- HavingProbability.maxEqOnNonempty α t C = HavingProbability.guardedSome α (fun (i : ι) => C < t i) fun (i : ι) => t i = C
Instances For
Dependency graph
“Random world with MAX(t) > C” (such a world is non-empty).
Equations
- HavingProbability.someAbove α t C = HavingProbability.someOf α fun (i : ι) => C < t i
Instances For
Dependency graph
“Random world with MAX(t) < C” (such a world is non-empty).
Equations
- HavingProbability.someBelow α t C = HavingProbability.someOf α fun (i : ι) => t i < C
Instances For
Dependency graph
“Non-empty random world with MAX(t) ≠ C”: disjoint union of
MAX < C and MAX > C.
Equations
Instances For
Dependency graph
“Non-empty random world with MIN(t) > C”.
Equations
- HavingProbability.minGtOnNonempty α t C = HavingProbability.guardedSome α (fun (i : ι) => t i ≤ C) fun (i : ι) => C < t i
Instances For
Dependency graph
“Non-empty random world with MIN(t) = C”.
Equations
- HavingProbability.minEqOnNonempty α t C = HavingProbability.guardedSome α (fun (i : ι) => t i < C) fun (i : ι) => t i = C
Instances For
Dependency graph
“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.
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.
The world realized by a valuation v: the positions of the group
sequence whose annotation evaluates to true under v.
Instances For
Dependency graph
Probability that a random world of Î satisfies a Boolean HAVING
query: the sum of Pr(v) over the valuations whose possible world does.
Equations
- HavingProbability.booleanHavingProb P q Î is ψ = ∑ v : X → Bool, if HavingPred.modelsBoolean (AnnotatedDatabase.randomWorld v Î) q is ψ then P.valProb v else 0