Duplicate elimination from the set recursion, annotated #
ε(q) = μ^∪R.(q, σ_false(R)) in every semiring, exactly: the first round
of the set recursion is the deduplication of q, the recursive term
reads the round and keeps nothing of it, so the second round is the
first and the iteration settles there, with the rows of ε(q) and their
annotations (evaluate_dedupMu). The recursion always settles
(annSettlesAt_dedupMu).
So ε is dispensable in the annotated algebra over every commutative
m-semiring: dedupFree replaces each ε by that recursion under a fresh
name, and generatesAnn_dedupFree says the classes other than ε
generate the annotated algebra (GeneratesAnn). The products go next
(Provenance.AnnotatedProd); the unions stay, the recursions' operands
being all-regular by typing and nothing re-typing an aggregate column
without exploding it.
One duplicate elimination as a set recursion #
μ^∪s.(q, σ_false(s)): the set recursion whose first round is ε(q)
and whose term adds nothing.
Equations
- dedupMu s q = AggQueryIn.MuSet s q (AggQueryIn.Sel falsePred (AggQueryIn.Hole n s) ⋯)
Instances For
Dependency graph
ε(q) = μ^∪s.(q, σ_false(s)), exactly.
Dependency graph
And it settles, at its second round.
Dependency graph
The pass #
Every ε replaced by the set recursion under a fresh name, the
supply split in three at each node.
Equations
- dedupFree f (AggQueryIn.Rel x✝ s) = AggQueryIn.Rel x✝ s
- dedupFree f (AggQueryIn.Hole x✝¹ s x✝) = AggQueryIn.Hole x✝¹ s x✝
- dedupFree f (AggQueryIn.Param pv x✝) = AggQueryIn.Param pv x✝
- dedupFree f AggQueryIn.Empty = AggQueryIn.Empty
- dedupFree f (AggQueryIn.Proj ps q) = AggQueryIn.Proj ps (dedupFree f q)
- dedupFree f (AggQueryIn.Sel φ q hφ) = AggQueryIn.Sel φ (dedupFree f q) hφ
- dedupFree f (q₁.Prod q₂) = (dedupFree (AggQueryIn.tri f 1) q₁).Prod (dedupFree (AggQueryIn.tri f 2) q₂)
- dedupFree f (q₁.Apply q₂) = (dedupFree (AggQueryIn.tri f 1) q₁).Apply (dedupFree (AggQueryIn.tri f 2) q₂)
- dedupFree f (q₁.Sum q₂) = (dedupFree (AggQueryIn.tri f 1) q₁).Sum (dedupFree (AggQueryIn.tri f 2) q₂)
- dedupFree f q.Dedup = dedupMu (f 0) (dedupFree (AggQueryIn.tri f 1) q)
- dedupFree f (q₁.Diff q₂) = (dedupFree (AggQueryIn.tri f 1) q₁).Diff (dedupFree (AggQueryIn.tri f 2) q₂)
- dedupFree f (AggQueryIn.Explode k h q) = AggQueryIn.Explode k h (dedupFree f q)
- dedupFree f (AggQueryIn.Retag h q) = AggQueryIn.Retag h (dedupFree f q)
- dedupFree f (AggQueryIn.Mu s q₀ q₁) = AggQueryIn.Mu s (dedupFree (AggQueryIn.tri f 1) q₀) (dedupFree (AggQueryIn.tri f 2) q₁)
- dedupFree f (AggQueryIn.MuSet s q₀ q₁) = AggQueryIn.MuSet s (dedupFree (AggQueryIn.tri f 1) q₀) (dedupFree (AggQueryIn.tri f 2) q₁)
- dedupFree f (AggQueryIn.Gamma is ts fs q keep ord) = AggQueryIn.Gamma is ts fs (dedupFree f q) keep ord
- dedupFree f (AggQueryIn.GammaScalar ts fs q ord) = AggQueryIn.GammaScalar ts fs (dedupFree f q) ord
- dedupFree f (AggQueryIn.GammaNest is his p g q) = AggQueryIn.GammaNest is his p g (dedupFree f q)
- dedupFree f (AggQueryIn.ProvSum is his t q) = AggQueryIn.ProvSum is his t (dedupFree f q)
- dedupFree f (AggQueryIn.GammaTok is his ts fs a q keep) = AggQueryIn.GammaTok is his ts fs a (dedupFree f q) keep
- dedupFree f (AggQueryIn.Win P O o w t g q hrr dist keep) = AggQueryIn.Win P O o w t g (dedupFree f q) hrr dist keep
- dedupFree f (AggQueryIn.WinExpr P O o ws ts fs g q_1 keeps) = AggQueryIn.WinExpr P O o ws ts fs g (dedupFree f q_1) keeps
Instances For
Dependency graph
The pass changes no annotated evaluation.
Dependency graph
Its plain readings #
The pass settles wherever the query does.
Dependency graph
What the pass keeps #
The sufficient half: ε is dispensable #
The classes other than ε generate the annotated algebra, over
every schema and every commutative m-semiring: each ε is the set
recursion μ^∪s.(q, σ_false(s)) under a fresh name, which reads exactly
as ε(q) does and always settles.