Duplicate elimination is necessary in the annotated algebra #
A set of classes that generates the annotated algebra over ℕ contains
ε or μ^∪. The invariant is that, without them, every annotation a
query builds is at most 𝟙 as soon as the instance's are. Products, δ
(the support map), a difference and 𝟙 ⊖ s keep it; a sum does not, and
the evaluator adds annotations in three places only:
εandμ^∪, which sum the annotations of the copies of a tuple;- a
DISTINCTwindow, which merges the occurrences of one value – out of the minimal signature,countnot being its own distinct version (count_distinct_ne); - the joint reading of a selection on aggregate values, a sum over the
worlds of the families it reads. There the sum of the worlds' weights is
at most
𝟙(GenPredIn.predsemJ_le_one):ℕis complemented, so a world's weight is a product over the occurrences and the sum over all worlds factors into∏ (a + (𝟙 ⊖ a)), which is𝟙where everyais.
ε of a relation holding one tuple twice, annotated 𝟙, gives 2
(dedup_or_muSet_mem_of_generatesAnn).
With the other rows this makes the basis {∅, Π, σ, apply, γ, win, μ^⊎, ε, −} minimal: no proper subset generates the annotated algebra over both
ℕ and ℕ × ℕ (annEpsOps_minimal).
The weight of a world, over ℕ #
The worlds of a selection weigh at most 𝟙 together #
The weight of a world: its present product times 𝟙 ⊖ its absent sum.
Equations
- worldWeight w = w.1 * (1 - w.2.1)
Instances For
Dependency graph
What a decision over a bag of occurrences weighs over ℕ, occurrence
by occurrence.
Equations
Instances For
Dependency graph
What a decision about an expression family weighs over ℕ.
Equations
- natLeafW e = NestedValue.leafProd e * (1 - NestedValue.leafAbs e)
Instances For
Dependency graph
A selection's joint reading is at most 𝟙 over ℕ when every
token of the row carries annotations at most 𝟙.
Dependency graph
Every annotation a query without ε and μ^∪ builds is at most 𝟙 #
A row's annotations are at most 𝟙: its concrete part and every
annotation the tokens it holds carry. Its pending factors are read only
through δ, which is at most 𝟙 whatever it reads.
Equations
Instances For
Dependency graph
Without ε, μ^∪ and DISTINCT aggregates, every annotation a
query builds is at most 𝟙 over ℕ, as soon as the instance's, the
context's tokens' and the rounds the holes are bound to are.
Dependency graph
The witness #
count is not its own distinct version: on [0, 0] the one
reads 2, the other 1. So a DISTINCT window is out of the minimal
signature.
Dependency graph
Dependency graph
The instance it tells apart from every query without ε and μ^∪:
R holds 0 twice, annotated 𝟙.
Equations
Instances For
Dependency graph
ε or μ^∪ is in every set generating the annotated algebra over
ℕ: without them every annotation a query of the minimal signature
builds is at most 𝟙 when the instance's are (le1_evaluate), and
ε(R) gives 2 on dEps.
Dependency graph
The basis with ε is minimal #
No proper subset of {∅, Π, σ, apply, γ, win, μ^⊎, ε, −} generates
the annotated algebra over both ℕ and ℕ × ℕ, with the counting
aggregate: ∅, Π, γ, μ^⊎, win and σ are inherited from the
plain rows, the apply because × is not in the set, − by the
zero-pattern invariant over ℕ × ℕ, and ε because μ^∪ is not in the
set.