Documentation

Provenance.HavingQueryCounterexamples

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

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.

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
      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
        Dependency graph

        Distributivity is needed: the ChainFive instance #

        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
              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
                        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
                          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
                              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
                              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
                                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 = 𝟙.

                                  def natRangeAnn :
                                  Fin 2 → ℕ

                                  The annotation of the counterexample: two occurrences, each 𝟙.

                                  Equations
                                  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.

                                    def Having.joint2 {T K : Type} [CommSemiringWithMonus K] (a b : AggValue T K) (χ : T → T → Kleene) :
                                    K

                                    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
                                      def Having.jointOr {T K : Type} [CommSemiringWithMonus K] (a b : AggValue T K) (P Q : T → Kleene) :
                                      K

                                      The joint reading of a disjunction of two conditions reading two disjoint families.

                                      Equations
                                      Instances For
                                        Dependency graph
                                        def Having.joint3 {T K : Type} [CommSemiringWithMonus K] (a b c : AggValue T K) (χ : T → T → T → Kleene) :
                                        K

                                        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
                                          theorem Having.joint2_branch_split {T K : Type} [CommSemiringWithMonus K] (a b : AggValue T K) (P : T → Kleene) (χ₁ χ₂ : T → T → Kleene) :
                                          (joint2 a b fun (x y : T) => if P x = Kleene.true then χ₁ x y else χ₂ x y) = (joint2 a b fun (x y : T) => (P x).and (χ₁ x y)) + joint2 a b fun (x y : T) => (Kleene.ofBool !(P x).isTrue).and (χ₂ x y)

                                          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
                                          Instances For
                                            Dependency graph

                                            One occurrence, absent.

                                            Equations
                                            Instances For
                                              Dependency graph
                                              def testNe :

                                              count ≠ 0, true on every non-empty world.

                                              Equations
                                              Instances For
                                                Dependency graph
                                                def testEq :

                                                count = 5, false on every world of a one-occurrence family.

                                                Equations
                                                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
                                                  Instances For
                                                    Dependency graph

                                                    One occurrence of multiplicity 2.

                                                    Equations
                                                    Instances For
                                                      Dependency graph
                                                      def testGe1 :

                                                      count ≥ 1, satisfied.

                                                      Equations
                                                      Instances For
                                                        Dependency graph
                                                        def testGe2 :

                                                        count ≥ 2, not satisfied on a one-occurrence family.

                                                        Equations
                                                        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.

                                                          def testLt1 :

                                                          count < 1, the negation of testGe1, satisfied by no world of a one-occurrence family.

                                                          Equations
                                                          Instances For
                                                            Dependency graph
                                                            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.

                                                            def testEq1 :

                                                            count = 1, satisfied by the world of a one-occurrence family.

                                                            Equations
                                                            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
                                                                  Instances For
                                                                    Dependency graph

                                                                    One occurrence annotated mid, grouped.

                                                                    Equations
                                                                    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
                                                                      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
                                                                      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.

                                                                        def testEq0 :

                                                                        count = 0, false on every non-empty world and true on the empty one.

                                                                        Equations
                                                                        Instances For
                                                                          Dependency graph

                                                                          One row, annotated mid, aggregated by count(*).

                                                                          Equations
                                                                          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
                                                                            Instances For
                                                                              Dependency graph
                                                                              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.

                                                                                          Equations
                                                                                          Instances For
                                                                                            Dependency graph

                                                                                            ORDER BY #1 DESC inside the aggregate.

                                                                                            Equations
                                                                                            Instances For
                                                                                              Dependency graph
                                                                                              @[reducible, inline]
                                                                                              abbrev noKey :
                                                                                              Tuple (Fin 2) 0

                                                                                              The whole relation as one group.

                                                                                              Equations
                                                                                              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.

                                                                                                def peerKinds :
                                                                                                Fin 3 → ColKind

                                                                                                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.

                                                                                                  Equations
                                                                                                  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.

                                                                                                    Equations
                                                                                                    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
                                                                                                      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
                                                                                                        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.

                                                                                                          def testGt0 :

                                                                                                          count > 0, on the range token's worlds.

                                                                                                          Equations
                                                                                                          Instances For
                                                                                                            Dependency graph
                                                                                                            def testLe1 :

                                                                                                            count ≤ 1.

                                                                                                            Equations
                                                                                                            Instances For
                                                                                                              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.

                                                                                                              @[reducible, inline]
                                                                                                              abbrev MM3 :

                                                                                                              The three-element min-max semiring, δ the identity.

                                                                                                              Equations
                                                                                                              Instances For
                                                                                                                Dependency graph

                                                                                                                One occurrence, graded.

                                                                                                                Equations
                                                                                                                Instances For
                                                                                                                  Dependency graph

                                                                                                                  Another, graded differently.

                                                                                                                  Equations
                                                                                                                  Instances For
                                                                                                                    Dependency graph
                                                                                                                    Dependency graph

                                                                                                                    Both satisfied, where the overlap would be counted twice were ⊕ not idempotent.

                                                                                                                    Dependency graph
                                                                                                                    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.

                                                                                                                    @[reducible, inline]
                                                                                                                    abbrev innerOf {K : Type} (l : ℕ) (β : K) :

                                                                                                                    The inner expression of one outer occurrence: a one-occurrence grouped count, of its own family l.

                                                                                                                    Equations
                                                                                                                    Instances For
                                                                                                                      Dependency graph
                                                                                                                      @[reducible, inline]
                                                                                                                      abbrev nestOf {K : Type} [CommSemiringWithMonus K] (α₀ α₁ β₀ β₁ : K) :

                                                                                                                      Two outer occurrences, each carrying a one-occurrence inner family of its own.

                                                                                                                      Equations
                                                                                                                      Instances For
                                                                                                                        Dependency graph
                                                                                                                        @[reducible, inline]
                                                                                                                        abbrev incoherentWorld {K : Type} [CommSemiringWithMonus K] [DecidableEq K] (α₀ α₁ β₀ β₁ : K) :

                                                                                                                        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
                                                                                                                          theorem mm_incoherentWorld_ne_zero :
                                                                                                                          (incoherentWorld { val := 1 } { val := 1 } { val := 1 } { val := 1 }).ann ≠ 0

                                                                                                                          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.

                                                                                                                          @[instance_reducible]

                                                                                                                          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.

                                                                                                                          def nestedInner (l : ℕ) (α : Bool) :

                                                                                                                          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.

                                                                                                                              Dependency graph