Query-level counterexamples for the HAVING / JOIN correspondence #
The correspondence between the possible-world semantics of HAVING
comparisons on COUNT(*) and the JOIN-based rewriting holds in
commutative m-semirings that are absorptive and whose ⊗ distributes over
⊖. This file witnesses, at the level of queries evaluated on concrete
annotated databases (not merely of the underlying algebraic identities),
that both hypotheses are needed. All facts are checked by decide.
It also witnesses, at that same level, that the EXCEPT spelling of
WHERE NOT EXISTS is not the antijoin
(HavingQueryCounterexamples.ChainFive.antijoin_query_ne_except,
beside the algebraic
ChainFive.antijoin_ne_difference). An operator-level witness and a
query-level one are different statements, not two presentations of one:
the second has to pick the operators the syntax offers, an instance on
which the two spellings mean the same condition, and the place where a
rewriting claims they agree.
The instances share the base relation R(g, v) of arity 2, grouped by the
first column; on the fused side the query is
the general HAVING site for COUNT(*) op C and on the join side
the queries are
Q₂^{≥1} = ε(Π_{#0}(R)),Q₂^{≥2} = ε(Π_{#0}(σ_{#0=#2 ∧ #1<#3}(R × R))), andQ₂^{=1} = Q₂^{≥1} - Q₂^{≥2},
the tie-broken comparison of the general construction degenerating to the
plain < because the second attributes of the instances are pairwise
distinct. The fused operator's output carries the group key and the
aggregate value while the join queries return the key only, so the
comparison is on the multisets of annotations.
Distributivity is needed (
HavingQueryCounterexamples.ChainFive.query_counterexample): in the five-element chain semiring – absorptive, hence idempotent, but not⊗-over-⊖distributive (ChainFive.not_mul_sub_left_distributive) – with annotations(mid, hi, hi)on one group,COUNT(*) = 1yields annotationhion the fused side but𝟘on the join side. On the same instance the monotone comparisonsCOUNT(*) ≥ 1andCOUNT(*) ≥ 2do agree withQ₂^{≥1}andQ₂^{≥2}(HavingQueryCounterexamples.ChainFive.query_ge_agree,HavingQueryCounterexamples.ChainFive.query_ge_two_agree), asQuery.joinCount_monotone_correctrequires: distributivity is needed for=, not for≥.Absorptivity is needed (
HavingQueryCounterexamples.MinTropicalZ.query_counterexample): in the tropical semiring overℤ ∪ {∞}– idempotent and distributive (MinTropicalZ.mul_sub_left_distributive) but not absorptive (MinTropicalZ.not_absorptive_witness) – with two occurrences annotatedtrop (-1)in one group,COUNT(*) ≥ 1yields annotationtrop (-2)on the fused side buttrop (-1)on the join side.A
FILTERclause that keeps everything is not the unfiltered reading, over a cut family (chain_count_zero_when_ne): inChainFive, one row annotatedmidgrouped and tested byHAVING count(*) ≐ 0gives𝟘, while the same read over the occurrences the clause keeps, in the scalar convention, gives𝟙. This is why no clause cuts a family: a grouping, a window and a multi-frame window all read one throughAggExpr's two flag families (AggExpr.ofGroupWhen,ValueFrame.exprWhen,ValueFrame.exprOfWhen), and what the expression reading gives instead ischainExprNone_zero,chainExprMixed_zeroandchainWinMixed_zero. The empty world weighs𝟙 ⊖ ⊕αand the group's existence factor does not absorb it (chain_delta_not_absorb_empty), whichℕhides (nat_delta_absorb_empty). What the two flag families ofAggExprgive instead – the group fixing the worlds and the clause fixing what the leaf reads – ischainExprNone_zeroandchainExprMixed_zero.
The two-column base relation R(g, v).
Equations
Instances For
Dependency graph
The same base relation as a general query, for the HAVING site.
Equations
Instances For
Dependency graph
Q₂^{≥1} = ε(Π_{#0}(R)).
Equations
Instances For
Dependency graph
Q₂^{≥2} = ε(Π_{#0}(σ_{#0=#2 ∧ #1<#3}(R × R))).
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
Q₂^{=1} = Q₂^{≥1} - Q₂^{≥2}.
Equations
Instances For
Dependency graph
The antijoin and the EXCEPT that spells it #
ChainFive.antijoin_ne_difference is the algebra: a ⊗ (𝟙 ⊖ b) and
a ⊖ a ⊗ b differ at a = b = hi. These are the same two readings as
queries on an instance, which is a different statement and not another
presentation of that one: the operators have to be the ones the syntax
offers, the instance has to make the condition they spell the same, and
the two evaluations have to be compared where the rewriting claims they
agree.
R(a) with one row annotated hi, and Q(b) with the one row it
matches, also annotated hi.
Equations
Instances For
Dependency graph
The left arm, as a general query.
Equations
Instances For
Dependency graph
The right arm, read once per row of the left.
Equations
Instances For
Dependency graph
The correlated match Q.b = R.a.
Equations
Instances For
Dependency graph
WHERE NOT EXISTS as the syntax offers it: the derived antijoin,
which counts the matches and keeps the rows whose count is 𝟘.
Equations
Instances For
Dependency graph
R as a classical query.
Equations
Instances For
Dependency graph
Q as a classical query.
Equations
Instances For
Dependency graph
The EXCEPT that spells the same condition:
R - Π_{#0}(σ_{#0 = #1}(R × Q)).
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
Query-level witness that the EXCEPT spelling of WHERE NOT EXISTS is not the antijoin: on one row with one match in the
absorptive, non-distributive ChainFive, the antijoin keeps the row and
the difference drops it. ChainFive.antijoin_ne_difference is the same
fact about the operations; this one is about two queries evaluated on an
instance, and it is what a rewriting that replaces one spelling by the
other has to answer for.
Dependency graph
One group with key 0, values 1, 2, 3, annotations mid, hi, hi.
Equations
Instances For
Dependency graph
Query-level part of the distributivity necessity: in the
absorptive but non-distributive ChainFive, the fused COUNT(*) = 1
query and its join-based rewriting disagree on a concrete instance.
Dependency graph
The monotone case closes in ChainFive: on the very instance
that separates the fused COUNT(*) = 1 query from its rewriting, the
fused COUNT(*) ≥ 1 query and Q₂^{≥1} agree, as
Query.joinCount_monotone_correct predicts for every absorptive
m-semiring, distributive or not.
Dependency graph
Likewise for COUNT(*) ≥ 2 and Q₂^{≥2}: both sides give
mid ⊗ hi ⊕ mid ⊗ hi ⊕ hi ⊗ hi = hi.
Dependency graph
Absorptivity is needed: the tropical instance over ℤ ∪ {∞} #
One group with key 0, values 1, 2, both annotated trop (-1).
Equations
Instances For
Dependency graph
What a WHERE EXISTS loses outside absorptivity #
evaluateAnnotated_semijoin reads a row kept by WHERE EXISTS (Q) as its
own annotation times the ⊕-sum of its witnesses' – the collapse of
AggValue.predProvScalar_count_ne_zero, which asks K to be absorptive.
Outside absorptivity the annotation is still the sum over the worlds in
which a match is present, and that is not the sum of the matches'
annotations: here it is their product, since every world that omits a
match is weighted 𝟙 ⊖ trop(-1) = 𝟘 and only the full world survives.
MinTropicalZ isolates the property, being distributive
(MinTropicalZ.mul_sub_left_distributive) and not absorptive
(MinTropicalZ.not_absorptive_witness).
The token a WHERE EXISTS reads over two matches, both annotated
trop (-1): counted, in the scalar convention, so that the empty world is
one of its worlds.
Equations
- HavingQueryCounterexamples.MinTropicalZ.existsToken = { agg := SeqAggFunc.count, occs := [(1, MinTropical.trop ↑(-1)), (1, MinTropical.trop ↑(-1))], scalar := true, fam := FamId.none }
Instances For
Dependency graph
What the row actually carries: trop (-1) ⊗ trop (-1) = trop (-2),
the annotation of the one world that keeps both matches.
Dependency graph
What the absorptive collapse would give: the ⊕-sum of the matches'
annotations, trop (-1) ⊕ trop (-1) = trop (-1).
Dependency graph
WHERE EXISTS is not “times the sum of the witnesses” outside
absorptivity. The two differ by a whole trop (-1): the row is read as
asking that every match be present, not that at least one is.
Dependency graph
Query-level part of the absorptivity necessity: in the idempotent
and distributive but non-absorptive tropical semiring over ℤ ∪ {∞}, the
fused COUNT(*) ≥ 1 query and its join-based rewriting disagree on a
concrete instance. Same phenomenon as the algebra-level
MinTropicalR.F_ne_S, here at the level of evaluated queries.
Dependency graph
The collapse of a count needs absorptivity #
AggValue.predProvScalar_count_ne_zero collapses the possible-world sum of
COUNT ≥ 1 to the ⊕-sum of the occurrence annotations, in an absorptive
m-semiring. Outside absorptivity neither that reading nor the indicator
one is the sum.
Over ℕ, with two occurrences annotated 1 and 2: a world that omits
the second is weighted 𝟙 ⊖ 2 = 𝟘, and one that omits the first 𝟙 ⊖ 1 = 𝟘, so the only world contributing is the one holding both, and the sum is
their product. The reading the collapse gives under absorptivity is
⊕αᵢ = 3, and the indicator reading δ(⊕αᵢ) is 𝟙; the sum is 2, and
is neither. What it counts is “every match present”, not “at least one”.
The token of two occurrences annotated 1 and 2, counted.
Equations
Instances For
Dependency graph
It is not the ⊕-sum the absorptive collapse gives.
Dependency graph
Nor is it the indicator reading δ(⊕ᵢ αᵢ).
Dependency graph
Two comparisons of one token do not read jointly #
A selection whose predicate conjoins two comparisons of the same token –
a truncation's m < #(k+1) ≤ m+c, a HAVING such as
count(*) > 2 AND count(*) < 5 – multiplies the two atoms' provenances,
each summed over the worlds of the token separately
(GenPredIn.predsem). AggValue.predProvOf_mul_predProvOf says that
this is the sum over the worlds where both comparisons hold when the
m-semiring is exclusive and its multiplication is idempotent. Neither
hypothesis can be dropped, and the scalar convention does not rescue
the identity either: ℕ is exclusive, the token below is scalar, and the
two readings still differ.
What this divergence needs is an occurrence annotated above 𝟙: the
same token with its occurrence annotated 𝟙 agrees. A domain whose
carrier is bounded by 𝟙, Viterbi for one, has no such annotation to
offer, so this instance is out of its reach.
One occurrence of multiplicity 2, counted, read in the scalar
convention.
Equations
- natRangeToken = { agg := SeqAggFunc.count, occs := [(1, 2)], scalar := true, fam := FamId.none }
Instances For
Dependency graph
A range test on one token is not the sum over the worlds in the
range. The product of the two one-sided provenances is 4, and the
joint sum is 2.
It is also the instance for two spellings of one selection: a chain
σ_{ψ₁}(σ_{ψ₂}(q)) multiplies the two predicates' provenances, while
σ_{ψ₁ ∧ ψ₂}(q) reads the conjunction jointly, one sum over the
family. The structural rule makes the two agree (predsem_and); the
joint reading does not, so the two spellings of what a SQL user would
call one query part here – 4 against 2.
Dependency graph
The same token with its occurrence annotated 𝟙 agrees.
Equations
- natUnitToken = { agg := SeqAggFunc.count, occs := [(1, 1)], scalar := true, fam := FamId.none }
Instances For
Dependency graph
The range closed form needs absorptivity in the difference itself #
Having.range_eq_S_monus_S reads HAVING C+1 ≤ count ≤ D as the
join-side difference S_{C+1} ⊖ S_{D+1} under absorptivity and
left-distributivity of ⊗ over ⊖. The hypotheses are not confined to
the step F_{C+1} = S_{C+1} that the proof passes through: the
difference parts company from the possible-world sum over ℕ, which is
not absorptive, on the smallest instance there is.
Two occurrences, each annotated 𝟙, and the range 1 ≤ count ≤ 1.
Every world of size one has T_U(W) = 𝟙 ⊖ 𝟙 = 𝟘, since its one-step
extension is annotated 𝟙 too, so the possible-world sum is 𝟘; the
join side is S_1 ⊖ S_2 = 2 ⊖ 1 = 𝟙.
The annotation of the counterexample: two occurrences, each 𝟙.
Equations
- natRangeAnn x✝ = 1
Instances For
Dependency graph
The range closed form fails over ℕ.
Dependency graph
∨ over disjoint families is not the ⊕ of the two atoms #
What a predicate annotates is the joint evaluation of its Boolean
function in every world: the ⊕, over the worlds of the union of the
families the function reads, of the world's annotation times the
function's truth there. That is one rule for ∧, ∨, ¬, a
Boolean-valued aggregate column and a searched CASE alike, and it is
AggExpr.predProv – an expression's occurrences are one shared family
V = ⋃ⱼ Uⱼ, a world must meet each grouped leaf, and g may be any
deterministic function of SQL, a Boolean combination among them.
GenPredIn.predsem is not that definition but a short cut for it,
∧ ↦ ⊗ and ∨ ↦ ⊕, the computation ProvSQL performs where the
m-semiring's properties license it – the same semantics, computed
cheaply. The question each instance below settles is where the license
runs out. For ∧ they do under hypotheses
(Having.sum_mul_sum_of_overlap, with complemented alone for
disjoint families and AggValue.predProvOf_mul_predProvOf for one
family). For ∨ there is no such theorem, and the failure is
structural rather than algebraic: it shows already in 𝔹, which is
exclusive, has an idempotent ⊗ and is complemented, so no capability
rescues it.
The reason is which worlds count. A world of a predicate reading two
grouped families must meet each of them, so a world in which one of
the two groups is empty is no world of the disjunction – while the
⊕ of the two atoms fires there, the atom of the non-empty group
holding on its own. A conjunction is unaffected: its product already
demands both groups non-empty.
Over 𝔹 the row's own factors hide the difference: the δ of the
empty group kills the row the ⊕ kept, which is why a disjunction may
remove a δ only when every disjunct entails existence
(GenPredIn.entailsExistence). Over ℕ they do not, δ recording
support where the difference is a multiplicity – so over ℕ the ⊕ is
not a licensed short cut for a disjunction and the sum has to be
computed.
The double sums joint2 and joint3 below write the joint reading in
split form, a product of the halves' world annotations. That is the
annotation of a world of the union in a complemented K
(Having.worldAnn_split); 𝔹 and ℕ are complemented, so over them
the instances are instances about the union reading.
The joint reading of a disjunction of two conditions reading two
disjoint families: one ⊕-sum over the worlds of the union, which
must meet each grouped family, weighted by whether either condition
holds there. The annotation of such a world is the product of the two
halves' (Having.worldAnn_split, under complemented).
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
The joint reading of a disjunction of two conditions reading two disjoint families.
Equations
- Having.jointOr a b P Q = Having.joint2 a b fun (x y : T) => (P x).or (Q y)
Instances For
Dependency graph
The joint reading of an atom over three families: one ⊕-sum over
the worlds of the union, each of which meets all three.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
The branches of a conditional exclude each other. Read world by
world, a two-branch case split is the one sum: in each world the guard
either holds or does not, so exactly one branch fires and the ⊕ counts
it once. No property of the m-semiring is used – and the guard of the
second branch is the test that the first is not true, not its
negation, which would be 𝟘 in a world where the guard is unknown and
leave that world satisfying neither branch, while SQL falls through.
What the statement needs is that the branches read one family. Where
they read different ones the case split and the one sum over the union
part (natCase_ne).
Dependency graph
One occurrence, present.
Equations
- boolTokenT = { agg := SeqAggFunc.count, occs := [(1, true)], fam := FamId.none }
Instances For
Dependency graph
One occurrence, absent.
Equations
- boolTokenF = { agg := SeqAggFunc.count, occs := [(1, false)], fam := FamId.none }
Instances For
Dependency graph
count ≠ 0, true on every non-empty world.
Instances For
Dependency graph
count = 5, false on every world of a one-occurrence family.
Instances For
Dependency graph
The ⊕ claims a provenance for a tuple that is in no world.
The second family is absent – its one occurrence is annotated 𝟘 – so
every world of the union that meets it carries 𝟘 and the joint
reading is ⊥, while the structural ⊕ takes the first side's own sum
and gives ⊤. A tuple carrying both aggregate columns comes from a
join of two groupings and does not exist when one group is empty, so
⊥ is the right answer and the ⊕ is wrong rather than merely
different.
Dependency graph
Dependency graph
Dependency graph
The same over ℕ, where the existence factors do not absorb it #
The 𝔹 instance above parts at predicate level and closes at row level,
the δ of the empty group killing the row. Over ℕ it does not close:
δ records support, and what differs is a multiplicity. Two grouped
families, one row annotated 𝟙 and one annotated 2, with the first
condition satisfied and the second not, give 𝟙 per atom and 2 for
the one sum over the union – and the row's own factors are
δ(1) ⊗ δ(2) = 𝟙, so nothing absorbs the difference.
The extra factor is the unsatisfied disjunct's family, which the
satisfied disjunct never reads. That is not a derivation count, so it is
a different kind of error from the multiplicity ⊕ already gives a
disjunction (p ∨ p is 2 in ℕ), and it is what makes the one-sum
reading over the union the wrong reference for a disjunction.
One occurrence of multiplicity 𝟙.
Equations
- natTokenOne = { agg := SeqAggFunc.count, occs := [(1, 1)], fam := FamId.none }
Instances For
Dependency graph
One occurrence of multiplicity 2.
Equations
- natTokenTwo = { agg := SeqAggFunc.count, occs := [(1, 2)], fam := FamId.none }
Instances For
Dependency graph
count ≥ 1, satisfied.
Instances For
Dependency graph
count ≥ 2, not satisfied on a one-occurrence family.
Instances For
Dependency graph
Dependency graph
Two alternatives of a Boolean aggregate column #
A Boolean combination of aggregate comparisons need not be written as a
predicate: SQL lets it be the value of a column, and an enclosing block
then reads that column through the atom flag = true – as a filter, or
as a key. Read structurally, the true alternative is the ⊕ of the
disjuncts and the false one the ⊗ of their negations, a conjunction
over disjoint families which decomposes under complemented alone.
The two alternatives of one occurrence do not then partition the worlds
of the families the column reads. Over ℕ, with both disjuncts
satisfied on two families each annotated 𝟙, they carry 2 ⊕ 𝟘 = 2,
where the worlds of the two families together carry 𝟙 – which is what
every non-Boolean column's alternatives carry, and what δ of the
support is. The excess is the worlds where both disjuncts hold, counted
once per disjunct.
count < 1, the negation of testGe1, satisfied by no world of a
one-occurrence family.
Instances For
Dependency graph
The alternatives of a Boolean aggregate column overcount.
Dependency graph
A conditional whose branches read different families #
SQL's searched CASE puts a Boolean combination inside a term and a
value comes out, so the atom CASE … END = v is the disjunction of the
branches, ψ̄₁ ∧ … ∧ ψ̄ⱼ₋₁ ∧ ψⱼ ∧ eⱼ ≐ v, with ψ̄ the test that ψ is
not true and not its negation – a negated comparison is 𝟘 where the
comparison is unknown, which would leave such a world satisfying no
branch at all, while SQL falls through to the next one.
The branch guards exclude each other, so the ⊕ over the branches
counts no world twice: that is Having.joint2_branch_split, which holds
in every m-semiring and asks nothing of it. What it needs is that the
branches read one family. As soon as two branches read aggregates
over different occurrence sequences, the case split and the one sum over
the union of all the families part, with no disjunction anywhere in the
query: the union charges the branch that fires for the family the other
branch would have read.
count = 1, satisfied by the world of a one-occurrence family.
Instances For
Dependency graph
A conditional parts the two readings with no disjunction in the query, as soon as its branches read different families.
Dependency graph
The same two instances against the definition #
The sums above are written family by family. Stated against
AggExpr.predProv – the joint evaluation over the worlds of one shared
family, which is the definition – the same numbers come out, and
nothing is assumed of ℕ to get them. Two singleton families are two
occurrences of one family that the leaves read one each.
c ≥ 1 ∨ d ≥ 1 over two families each annotated 𝟙, as the
Boolean function the joint reading evaluates: 𝟙 where the disjunction
holds, 𝟘 where it does not.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
The structural ⊕ is 2, counting the world once per disjunct.
Dependency graph
CASE WHEN c ≥ 1 THEN d ELSE e END, with c and d annotated 𝟙
and e – which no world in which the guard holds reads – annotated
2.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
The branch decomposition is 𝟙, so a conditional whose branches
read different families parts from the definition with no disjunction
anywhere in the query.
Dependency graph
At the row level: an idempotent ⊕ is not what makes the ⊕ exact #
What an implementation reports is not a bare predicate provenance but a
row annotation, a group carrying its existence factor: δ(β₁) ⊗ δ(β₂) ⊗ predsem(ψ). Over 𝔹 those factors close the gap the ∨ rule opens –
bool_or_ne_joint is a statement about the predicate provenance and
not about the row, and bool_row_agree says so.
They do not close it in general, and an idempotent ⊕ is not the
condition. ChainFive is absorptive, so its ⊕ is idempotent, and its
δ is not the identity: δ(hi) = 𝟙. Two singleton grouped families
annotated hi and mid, the first side's test satisfied and the
second's not, give hi for the reported row and lo for the joint
reading, the δ factors having replaced the second family's mid by
𝟙. The missing factor is the other side's annotation, and δ can
only restore it where δ is the identity, which 𝔹, 𝔹[X], interval
union and min-max have (delta := id in each instance) and ChainFive,
ℕ, ℕ[X], Lin[X], Why[X], the tropical semirings, Viterbi and
Łukasiewicz do not.
Min-max is the instructive one: δ = id and ⊕ idempotent are not
sufficient either, since it is not exclusive and so not a Boolean
algebra, and whether the row is exact there beyond two singleton
families is open. What is settled is the Boolean case – see
AggValue.row_agree_of_delta_id for 𝔹[X] at every family size.
One occurrence annotated hi, grouped.
Equations
- chainTokenHi = { agg := SeqAggFunc.count, occs := [(1, ChainFive.hi)], fam := FamId.none }
Instances For
Dependency graph
One occurrence annotated mid, grouped.
Equations
- chainTokenMid = { agg := SeqAggFunc.count, occs := [(1, ChainFive.mid)], fam := FamId.none }
Instances For
Dependency graph
The reported row: the two groups' existence factors times the
structural ⊕ of the two sides.
Dependency graph
The joint reading of the same row.
Dependency graph
So the existence factors do not make the ⊕ exact, in a
semiring whose ⊕ is idempotent.
Dependency graph
Over 𝔹 they do, which is why the 𝔹 instance above is about
the predicate provenance and not about the row: δ is the identity
there, so the factor the ⊕ drops is restored.
Dependency graph
One occurrence annotated α, grouped.
Equations
- boolTokenOf α = { agg := SeqAggFunc.count, occs := [(1, α)], fam := FamId.none }
Instances For
Dependency graph
A FILTER clause that keeps everything is observable #
A filtered aggregate read over the occurrences the clause keeps – a cut
family – has to be read in the scalar convention, and the convention is
forced by the clause that keeps nothing: the family is then empty, so only
the empty world can carry the row SQL still emits for a group that exists.
The library does not read a filtered aggregate that way: it reads it as
an expression over the whole group (AggExpr.ofGroupWhen).
Where the clause keeps everything, the same recipe is not the unfiltered
reading. The empty world of the uncut family weighs 𝟙 ⊖ ⊕α, and the
group's existence factor δ(⊕α) does not absorb it: delta_absorb needs
an occurrence to be present, which is exactly what the empty world denies.
So HAVING count(*) FILTER (WHERE true) ≐ 0 reports a row that
HAVING count(*) ≐ 0 rejects, in a semiring where δ(a) ⊗ (𝟙 ⊖ a) ≠ 𝟘.
ChainFive is such a semiring and ℕ, 𝔹 and 𝔹[X] are not – there
𝟙 ⊖ a is 𝟘 wherever δ(a) is 𝟙 – which is why the instances above
did not show it. What the pair of readings would have to be to make a
trivially true clause a no-op is an occurrence that stays in the family
while the clause takes it out of what the aggregate reads: the worlds
and their annotations would then be the group's, as they are with no
clause, and the kept part of a non-empty world could still be empty.
AggValue cannot express that – its occurrence carries a value and an
annotation, and nothing else – while AggExpr can, which is what
AggExpr's per-leaf reads flags are and why an occurrence no leaf reads
is allowed.
count = 0, false on every non-empty world and true on the empty
one.
Instances For
Dependency graph
One row, annotated mid, aggregated by count(*).
Equations
- chainCount = { agg := SeqAggFunc.count, occs := [(1, ChainFive.mid)], fam := FamId.none }
Instances For
Dependency graph
The same group under FILTER (WHERE true): the same occurrences, read
in the scalar convention. The two tokens differ in nothing else, the
clause keeping every occurrence.
Equations
- chainCountWhen = { agg := SeqAggFunc.count, occs := [(1, ChainFive.mid)], scalar := true, fam := FamId.none }
Instances For
Dependency graph
So a clause that keeps everything is not the unfiltered reading.
Dependency graph
The root of it, as an identity about the semiring: the existence factor does not absorb the empty world's weight.
Dependency graph
Over ℕ it does, for every annotation a non-empty group can carry,
which is why a numeric instance shows nothing here.
Dependency graph
What the two flag families give instead #
AggExpr carries the group and the clause apart (AggExpr.inFrame,
AggExpr.reads), which is what a filtered aggregate needs: the worlds
are the group's, every occurrence carrying its annotation to them, and
the clause says what the leaf aggregates there. The three readings below
are the ones the cut family gets wrong, in the semiring that shows it.
A clause that keeps everything needs no test: its flags are the ones no clause gives, so the expression is the unfiltered one.
The group of chainCount read as a one-leaf aggregate expression:
one occurrence annotated mid, in the leaf's group and read by it.
Equations
Instances For
Dependency graph
The same under FILTER (WHERE false): the occurrence stays in the
group and leaves what the leaf reads.
Equations
Instances For
Dependency graph
Two occurrences, annotated mid and hi, the clause keeping the
first: count(*) FILTER (WHERE φ) where φ holds of one row of two.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
HAVING count(*) ≐ 0 still rejects the row, as it does for the
token: no world of a grouped leaf is empty.
Dependency graph
Under FILTER (WHERE false) the row is reported with the group's
own weight – mid, the annotation of the occurrence that makes the
group exist – and not with 𝟙, which is what the cut family gives
(chain_count_zero_when). SQL emits that row, with 0.
Dependency graph
And a clause that keeps some of the group reports exactly the
worlds in which it keeps none of the present rows: hi ⊗ (𝟙 ⊖ mid),
the world holding the rejected occurrence alone. The cut family cannot
express that world at all.
Dependency graph
What a filtered window reads, and what DISTINCT decides #
A window's clause cuts what its leaf reads of the frame, exactly as a
grouping's does, so the readings below are the window's counterpart of
the three above. The last pair records the choice DISTINCT forces: the
classes of the kept part carry the ⊕ of their occurrences, which is
what a DISTINCT aggregate is, being defined through ε, and not a
deduplication inside each world. The two differ, and ℕ shows
it.
The family a filtered window builds over a frame of two rows, the
clause keeping the first: AggExpr.ofSeqWhen's, with the frame flag on
both and the clause flag on the first alone.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
The clause keeping one row of the frame reports the worlds holding
none of the kept ones: hi ⊗ (𝟙 ⊖ mid), the world with the rejected
row alone – which is a world of the frame that a cut family loses.
Dependency graph
count(DISTINCT x) FILTER (WHERE true) OVER (w) over two occurrences
of equal value annotated 𝟙: by mergeOccs_two the family is the one
class annotated 2.
Equations
Instances For
Dependency graph
The same data read without the merge, the leaf deduplicating
inside each world instead: the family is one occurrence per row and the
aggregate is count^distinct (count_distinct_eq_dedup_length). This is
the reading the merge was chosen against.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
The merge counts the class once, with the ⊕ of its
occurrences: 𝟙 ⊕ 𝟙 = 2 over ℕ.
Dependency graph
Deduplicating in the reading gives 𝟙 instead: the two
one-occurrence worlds weigh 𝟙 ⊗ (𝟙 ⊖ 𝟙) = 𝟘, and only the full world
weighs anything – where the two equal values are one distinct value, so
the test holds there too.
Dependency graph
So the two readings of a DISTINCT aggregate are different
provenances – 2 against 𝟙 – and the merge is the one ε defines.
Dependency graph
An aggregation's ORDER BY is not decoration #
AggQueryIn.Gamma and GammaScalar carry a GroupOrder: their
aggregates read the group in that clause's order
(Relation.groupSeqOrd, Having.havingGroupOrd) rather than in the
domain's canonical one. For a symmetric aggregate that changes nothing,
which is why count and sum never needed it; for an order-dependent
one it does, so the clause is the aggregate's own and not an order the
library could pick for it. The two rows below differ in the column the
clause reads, and first_value of that column comes out 2 under the
clause against 1 without it.
Two rows of one group, differing in the column the clause reads.
Instances For
Dependency graph
ORDER BY #1 DESC inside the aggregate.
Equations
Instances For
Dependency graph
The whole relation as one group.
Instances For
Dependency graph
A window may not read an aggregate column of its input #
AggQueryIn.Win takes any input kinds, and reads its input through
ColKind.readTuple: the regular columns, and nothing of the aggregate
ones – not even to break a tie in the ORDER BY. This is why the second
half is needed and WinReadsReg alone would not do. The two relations
below hold the same regular columns row for row and differ only in the
middle column, an aggregate one; read whole, the determinized peer
order (OrderSpec.readLe, whose ties are broken by the row) puts a
different row first, and first_value of the regular column the window
does read comes out 2 on one and 1 on the other. An aggregate
column's value is what its token reads in a world, so a window reading
its input whole would order two peers one way in one world and the other
way in the next, and its column would not read in a world what the plain
window reads of that world.
Three columns: a key the ORDER BY reads, an aggregate column, and
the value the aggregate reads.
Equations
Instances For
Dependency graph
Two rows the ORDER BY leaves tied, with an aggregate column whose
deterministic reading is 5 and 3.
Instances For
Dependency graph
The same two rows in a world where that column reads 1 and 9:
the same regular columns, row for row.
Instances For
Dependency graph
Inclusion–exclusion is not the joint reading of a disjunction #
Over disjoint families whose totals are 𝟙 – the scalar convention,
where the empty world counts – the joint reading of a disjunction is
sometimes written S₁ ⊕ S₂ ⊖ S₁ ⊗ S₂, on the reading of ⊖ as a
subtraction that removes the worlds counted twice. That is an identity
about numbers, not about m-semirings: it holds over ℕ, and fails in
𝔹, where ⊤ ⊕ ⊤ ⊖ ⊤ ⊗ ⊤ is ⊤ ⊖ ⊤ = ⊥ while both sides of the
disjunction hold. The overlap is not a quantity to be removed; in an
idempotent ⊕ it was never counted twice.
One occurrence, present, read in the scalar convention – so the
empty world counts and the family's total is 𝟙.
Equations
- boolScalarT = { agg := SeqAggFunc.count, occs := [(1, true)], scalar := true, fam := FamId.none }
Instances For
Dependency graph
Inclusion–exclusion fails in 𝔹: the joint reading is ⊤ and
the formula gives ⊥.
Dependency graph
One occurrence annotated 𝟙, scalar – the ℕ counterpart, where
the formula does hold.
Equations
- natScalarOne = { agg := SeqAggFunc.count, occs := [(1, 1)], scalar := true, fam := FamId.none }
Instances For
Dependency graph
Dependency graph
jointPair reads two families as disjoint #
Having.jointPair sums over the worlds of the concatenation of the two
occurrence families, so it reads them as independent. That is the joint
reading when the families genuinely are disjoint – two columns coming
from two different groupings – and it is not the joint reading when
they coincide. Two aggregates of one group are one family
(AggValue.annList_ofGroup), and reading them as two independent ones
counts a world once per half: over ℕ, 4 where the one-family
reading gives 2. So a conjunction of tests on two aggregate columns
is the column-by-column product exactly where the columns come from
different groupings, and parts from it where they come from one – the
same 4 against 2 that separates a chain of selections from one
selection on the conjunction.
count > 0, on the range token's worlds.
Instances For
Dependency graph
Dependency graph
Read as two disjoint families, one family is counted twice.
Dependency graph
The one-family reading of the same conjunction is 2.
Dependency graph
Min-max: δ = id with no exclusivity, and the row still absorbs #
ChainFive shows an idempotent ⊕ is not what makes the existence
factors absorb the ∨ rule's difference (chain_row_ne); δ = id is
necessary, by the identity a ⊗ δ(b) = a ⊗ b at a = 𝟙. Min-max has
δ = id and is not exclusive, which is the one place in the catalog
where the two roads to killing an invented world both fail – so whether
it keeps the row-level absorption is exactly whether δ = id suffices.
It does, here: ⊗ is max and ⊕ is min, so
max(a, b, min(a, b)) = max(a, b) and the reported row is the joint
one, in each configuration of the two tests.
The three-element min-max semiring, δ the identity.
Instances For
Dependency graph
One occurrence, graded.
Instances For
Dependency graph
Another, graded differently.
Instances For
Dependency graph
One test satisfied: the configuration ChainFive parts on.
Dependency graph
Both satisfied, where the overlap would be counted twice were
⊕ not idempotent.
Dependency graph
Neither satisfied.
Dependency graph
An aggregate over an inner grouping's aggregates: min-max invents a world #
A nested aggregate's worlds range over the occurrences of the outer
family and those of the inner values, so a world may keep an inner
occurrence of an outer occurrence it drops – a combination of rows the
inner grouping could not have produced. Such a world carries
(⊗ over what it keeps) ⊗ (𝟙 ⊖ α) for the dropped outer occurrence's
annotation α, so it dies exactly where that product is 𝟘.
Over ℕ it dies: α = 𝟙 and 𝟙 ⊖ 𝟙 = 𝟘. Over min-max it does not:
𝟙 is ⊥, and ⊥ ⊖ g = ⊥ = 𝟙 for any grade g ≠ 𝟙, so the
complement factor is 𝟙 and the invented world keeps the weight of the
rows it does hold. That is the one row of the catalog where neither
road – an exclusive ⊕ nor a δ saturating to 𝟙 – is open.
The inner expression of one outer occurrence: a one-occurrence
grouped count, of its own family l.
Equations
Instances For
Dependency graph
Two outer occurrences, each carrying a one-occurrence inner family of its own.
Equations
Instances For
Dependency graph
The invented world: it keeps the first outer occurrence and the inner occurrence of the second, which it drops.
Equations
Instances For
Dependency graph
Over ℕ the invented world is annotated 𝟘.
Dependency graph
Over min-max it is not: the complement factor is 𝟙, so the
world keeps the weight of the rows it holds.
Dependency graph
Complementedness is not an m-semiring identity #
Every semiring of the catalog is complemented (complemented's
docstring lists the eleven proofs), which is why the hypothesis the
nested homomorphism commutation carries excludes nothing anyone computes
in. It is not, however, a consequence of the axioms: the non-negative
rationals with truncated subtraction are an m-semiring and fail the law
at a = b = ½. They are not a provenance semiring – ordinary
multiplication is not ⊗ of any provenance reading – which is what the
counterexample needs them not to be.
The non-negative reals with truncated subtraction: an m-semiring,
with the indicator δ. The non-negative rationals refute the law just as
well; ℝ≥0 is the carrier this development already has at hand
(Viterbi's), so the law is refuted over it.
Equations
- One or more equations did not get rendered due to their size.
Dependency graph
Complementedness is not an m-semiring identity: over the
non-negative reals it fails at a = b = ½, where the left side is
𝟙 ⊖ 𝟙 = 𝟘 and the right side is ½ ⊗ ½ = ¼. Every semiring of the
catalog satisfies it (see complemented's docstring), so the hypothesis
the nested homomorphism commutation carries excludes nothing anyone
computes in – but it is a hypothesis and not a theorem.
Dependency graph
The coherent reading of a nested world is not a convention #
The question is whether a world of a nested value may keep an
inner occurrence of an outer occurrence it drops. The library's
NestedValue.World.IsWorld allows it; IsWorldCoherent forbids it. It
would be tempting to close the question by showing the two readings agree
wherever anyone computes – in a Boolean algebra with δ = id – and the
argument for that is: an incoherent world keeps an inner α while the
outer occurrence's own β sits in the monus, so the weight is
α ⊗ (𝟙 ⊖ (β ⊕ …)), which exclusivity kills if α ≤ β.
Nothing makes α ≤ β. An occurrence's outer annotation and its inner
family's annotations are independent fields, and the evaluator can build
a row whose annotation is 𝟘 while its aggregate column has a realized
occurrence – a selection with an aggregate atom keeps its failing rows
annotated 𝟘. Over 𝔹, the two readings then differ: the incoherent
world weighs ⊤ ⊗ (𝟙 ⊖ 𝟘) = ⊤, so the current reading reports ⊤ where
the coherent one reports 𝟘. The question is therefore a choice about
the semantics and not a convention that the catalog's semirings make
invisible.
An inner expression with one occurrence annotated α, grouped, of
the family l.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
Two outer occurrences, grouped: one annotated ⊤, one annotated 𝟘,
each carrying an inner family of its own with one occurrence annotated
⊤. The second is the row a selection keeps annotated 𝟘 whose
aggregate column is still realized.
Equations
Instances For
Dependency graph
And they weigh the row differently over 𝔹: ⊤ against 𝟘. So
whether a nested world must be coherent is not settled by δ = id with
exclusivity, and the
two readings are not interchangeable in any semiring of the catalog.
Dependency graph
The world a valuation realizes is this incoherent one, which is
what settles the question rather than merely opening it: the realized
world sets an occurrence present exactly when the valuation makes its
outer annotation true, and keeps the inner occurrences the valuation
makes true, independently (NestedValue.realizedWorld). So where a
selection has brought a row's annotation to 𝟘 while its aggregate
column stays realized, the actual world keeps the inner occurrences of an
absent outer one.
Dependency graph
And the current reading admits it, so it is the reading under
which the 𝔹-sum is the indicator of the actual world. A reading that
forbade it would annotate this value 𝟘 where the world as it is holds
the row, which NestedValue.World.ann_eval_iff and the possible-world
results built on it would then contradict.