Scan-computable HAVING provenance for MIN, MAX and PICKFIRST #
For a HAVING predicate comparing an aggregate to a constant, the
possible-world semantics sums the world annotations T_U(W) over the
non-empty valid worlds W ⊆ U of a group, of which there are in general
exponentially many. This file shows that for the aggregates MIN, MAX and
PICKFIRST – those whose validity is decided occurrence by occurrence – that
sum collapses, in an absorptive commutative m-semiring, to a closed form
using O(|U|) semiring operations: the provenance is obtained by a single
scan over the occurrences of the group, hence in polynomial time in data
complexity.
The collapse #
Everything rests on one identity, meet_family_eq: for H ⊆ G ⊆ U,
⊕_{W ⊆ G, W ∩ H ≠ ∅} T_U(W) = (𝟙 ⊖ ⊕_{x ∈ U \ G} α x) ⊗ (⊕_{i ∈ H} α i),
i.e., the provenance of “the world stays inside G and meets H” is the
product of two running sums. Both hypotheses of the absorptive setting are
used: ≤ follows from A_W ≤ α i ≤ ⊕_H α (absorptivity makes A decreasing
under inclusion), and ≥ from upward_expansion in the universe G,
transported to U by T_eq_T_of_subset and sum_monus.
Where the hypotheses are used #
Absorptivity makes A decreasing under inclusion (A_le_of_subset_absorptive)
and is used in both halves. mul_sub_left_distributive is used exactly twice:
in the ≤ half, to pass from T_U(W) – defined in Provenance.Having as
A_W ⊖ ⊕_x A_{W ∪ {x}} – to the factored form A_W ⊗ (𝟙 ⊖ ⊕_{U∖W} α) in which
the possible-world semantics is stated; and in the ≥ half, to rewrite the
right-hand side as ⊕_H α ⊖ (⊕_H α ⊗ ⊕_{U∖G} α), the shape sum_monus needs.
The first use is not a proof convenience: in MaxMin TVL (absorptive but not
mul_sub_left_distributive) the identity is false for T as defined here –
U = {1,2}, G = H = {1} and α₁ = α₂ = unknown give 𝟘 on the left and
unknown on the right – because that is precisely where the two forms of the
world annotation part company.
The six comparison operators then instantiate this with the right pair
(G, H); e.g., MIN(t) ≥ c keeps the worlds inside G = {i | t i ≥ c}, while
MIN(t) ≤ c keeps the worlds meeting H = {i | t i ≤ c}, and MIN(t) = c
uses both. PICKFIRST splits the worlds according to their first occurrence
and applies the identity to each fiber.
Main results #
meet_family_eq– the collapse identity;prov_eq_of_pointwise– its reading as a selection predicate decided occurrence by occurrence;minScan/minScan_correct,maxScan/maxScan_correct,firstScan/firstScan_correct– the three scans and their correctness, for all six comparison operators.
Unlike the COUNT/SUM cases, no world enumeration is involved: the scans
are closed forms, and the absorptivity hypothesis is what makes them exist
(in ℕ[X], for instance, the same provenance is a product rather than a
sum of annotations).
Possible-world provenance of a selection predicate #
The possible-world provenance, at one group, of a selection predicate P
on worlds: the ⊕-sum of the world annotations T_U(W) over the non-empty
worlds satisfying P, in the possible-world semantics of HAVING
predicates.
Instances For
Dependency graph
The MIN and MAX aggregates #
MIN(t) over a world, as an element of WithTop V: the empty world has
aggregate value ⊤ (it is excluded from the possible-world sum anyway).
Equations
- Having.minAgg t W = W.inf fun (i : ι) => ↑(t i)
Instances For
Dependency graph
MAX(t) over a world, as an element of WithBot V.
Equations
- Having.maxAgg t W = W.sup fun (i : ι) => ↑(t i)
Instances For
Dependency graph
The MIN scan. Closed form for the provenance of MIN(t) op c: for
each operator, at most two running ⊕-sums over the occurrences of the group,
combined by one ⊖ and one ⊗. Computing it takes O(|U|) semiring
operations, hence polynomial time in data complexity;
minScan_correct proves it correct.
Equations
- Having.minScan α U t CompOp.lt c = ∑ i ∈ U with t i < c, α i
- Having.minScan α U t CompOp.le c = ∑ i ∈ U with t i ≤ c, α i
- Having.minScan α U t CompOp.ge c = (1 - ∑ x ∈ U with t x < c, α x) * ∑ i ∈ U with c ≤ t i, α i
- Having.minScan α U t CompOp.gt c = (1 - ∑ x ∈ U with t x ≤ c, α x) * ∑ i ∈ U with c < t i, α i
- Having.minScan α U t CompOp.eq c = (1 - ∑ x ∈ U with t x < c, α x) * ∑ i ∈ U with t i = c, α i
- Having.minScan α U t CompOp.syneq c = (1 - ∑ x ∈ U with t x < c, α x) * ∑ i ∈ U with t i = c, α i
- Having.minScan α U t CompOp.ne c = ∑ i ∈ U with t i < c, α i + (1 - ∑ x ∈ U with t x ≤ c, α x) * ∑ i ∈ U with c < t i, α i
- Having.minScan α U t CompOp.synne c = ∑ i ∈ U with t i < c, α i + (1 - ∑ x ∈ U with t x ≤ c, α x) * ∑ i ∈ U with c < t i, α i
Instances For
Dependency graph
The MAX scan, the mirror image of minScan; see maxScan_correct.
Equations
- Having.maxScan α U t CompOp.gt c = ∑ i ∈ U with c < t i, α i
- Having.maxScan α U t CompOp.ge c = ∑ i ∈ U with c ≤ t i, α i
- Having.maxScan α U t CompOp.le c = (1 - ∑ x ∈ U with c < t x, α x) * ∑ i ∈ U with t i ≤ c, α i
- Having.maxScan α U t CompOp.lt c = (1 - ∑ x ∈ U with c ≤ t x, α x) * ∑ i ∈ U with t i < c, α i
- Having.maxScan α U t CompOp.eq c = (1 - ∑ x ∈ U with c < t x, α x) * ∑ i ∈ U with t i = c, α i
- Having.maxScan α U t CompOp.syneq c = (1 - ∑ x ∈ U with c < t x, α x) * ∑ i ∈ U with t i = c, α i
- Having.maxScan α U t CompOp.ne c = ∑ i ∈ U with c < t i, α i + (1 - ∑ x ∈ U with c ≤ t x, α x) * ∑ i ∈ U with t i < c, α i
- Having.maxScan α U t CompOp.synne c = ∑ i ∈ U with c < t i, α i + (1 - ∑ x ∈ U with c ≤ t x, α x) * ∑ i ∈ U with t i < c, α i
Instances For
Dependency graph
Provenance of the six MIN(t) op c predicates #
Provenance of the six MAX(t) op c predicates #
The two scans are correct #
Correctness of the MIN scan. For every comparison operator, the
possible-world provenance of the HAVING MIN(t) op c predicate is computed by
the scan minScan.
Dependency graph
Correctness of the MAX scan.
Dependency graph
The PICKFIRST aggregate #
PICKFIRST is the non-commutative aggregate returning the value of the first
occurrence of its input sequence. Here the occurrences are ordered by a linear
order ≼ on ι (the order along which the group is enumerated), so the first
occurrence of a world is its ≼-minimum.
PICKFIRST(t) over a world: the value of its ≼-first occurrence, with
⊤ for the empty world.
Equations
- Having.firstAgg t W = WithTop.map t W.min
Instances For
Dependency graph
The PICKFIRST scan. Closed form for the provenance of
PICKFIRST(t) op c: one term per satisfying occurrence, each combining the
annotation of that occurrence with the running sum of the annotations of the
occurrences that precede it.
Equations
Instances For
Dependency graph
Correctness of the PICKFIRST scan. The possible-world provenance of
the HAVING PICKFIRST(t) op c predicate is computed by the scan firstScan:
the worlds are partitioned according to their first occurrence.