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 #
The subsequence of U selected by a set of positions, in order.
Equations
Instances For
Dependency graph
The world annotation, in factored form #
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
- Having.worldAnn α W = (∏ i ∈ W, α i) * (1 - ∑ i ∈ Wᶜ, α i)
Instances For
Dependency graph
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
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.
Instances For
Dependency graph
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
Summing over the worlds of a family is summing over the pairs of worlds of its two halves.
Dependency graph
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
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
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 #
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
- Having.havingGroup is r g = ↑(Multiset.foldr sortedInsert ⟨[], ⋯⟩ (Multiset.filter (fun (p : AnnotatedTuple T K m) => ∀ (k' : Fin n₁), p.1 (is k') = g k') r))
Instances For
Dependency graph
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
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
- Having.aggValOn U t f W = f (List.map (fun (p : AnnotatedTuple T K m) => TermIn.eval t p.1) (Having.seqOf U W))
Instances For
Dependency graph
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
- Having.aggValOnWhen U keep t f W = f (List.map (fun (u : Tuple T m) => TermIn.eval t u) (List.filter keep (List.map Prod.fst (Having.seqOf U W))))
Instances For
Dependency graph
Predicate provenance #
χ_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
- Having.chi op a b = if op.eval3 a b = Kleene.true then 1 else 0
Instances For
Dependency graph
χ_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
- Having.chiOf P a = if P a = Kleene.true then 1 else 0
Instances For
Dependency graph
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
- Having.havingProv U t f op c = ∑ W : Finset (Fin U.length) with W.Nonempty, Having.worldAnn (fun (i : Fin U.length) => (U.get i).2) W * Having.chi op (Having.aggValOn U t f W) c
Instances For
Dependency graph
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
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 ⊖.
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
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
- Having.ExistentialOn f op c P = ∀ (L : List T), L ≠ [] → (op.eval3 (f L) c = Kleene.true ↔ ∃ x ∈ L, P x)
Instances For
Dependency graph
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
- Having.Existential3 f op = ∀ (L : List T) (c : T), L ≠ [] → (op.eval3 (f L) c = Kleene.true ↔ ∃ x ∈ L, op.eval3 x c = Kleene.true)
Instances For
Dependency graph
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 #
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.
- cmp {T : Type} {m n₁ : ℕ} : Term T m → SeqAggFunc T → CompOp → Term T n₁ → HavingPred T m n₁
- not {T : Type} {m n₁ : ℕ} : HavingPred T m n₁ → HavingPred T m n₁
- and {T : Type} {m n₁ : ℕ} : HavingPred T m n₁ → HavingPred T m n₁ → HavingPred T m n₁
- or {T : Type} {m n₁ : ℕ} : HavingPred T m n₁ → HavingPred T m n₁ → HavingPred T m n₁
Instances For
Dependency graph
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
- One or more equations did not get rendered due to their size.
- HavingPred.provAux U g negated (HavingPred.cmp t f op s) = Having.havingProv U t f (if negated = true then op.negate else op) (TermIn.eval s g)
- HavingPred.provAux U g negated ψ.not = HavingPred.provAux U g (!negated) ψ
Instances For
Dependency graph
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
- HavingPred.prov U g ψ = HavingPred.provAux U g false ψ
Instances For
Dependency graph
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
- HavingPred.evalOnSeq L g (HavingPred.cmp t f op s) = op.eval3 (f (List.map (fun (tuple : Tuple T m) => TermIn.eval t tuple) L)) (TermIn.eval s g)
- HavingPred.evalOnSeq L g ψ.not = (HavingPred.evalOnSeq L g ψ).not
- HavingPred.evalOnSeq L g (ψ₁.and ψ₂) = (HavingPred.evalOnSeq L g ψ₁).and (HavingPred.evalOnSeq L g ψ₂)
- HavingPred.evalOnSeq L g (ψ₁.or ψ₂) = (HavingPred.evalOnSeq L g ψ₁).or (HavingPred.evalOnSeq L g ψ₂)
Instances For
Dependency graph
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
- HavingPred.holdsOnSeq L g ψ = (HavingPred.evalOnSeq L g ψ = Kleene.true)
Instances For
Dependency graph
Equations
Dependency graph
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
- HavingPred.modelsBoolean d q is ψ = ∃ g ∈ Multiset.map (fun (u : Tuple T m) (k : Fin n₁) => u (is k)) (q.evaluate d), HavingPred.holdsOnSeq (Relation.groupSeq is (q.evaluate d) g) g ψ
Instances For
Dependency graph
Equations
- One or more equations did not get rendered due to their size.
Dependency graph
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.