The set recursion from the bag recursion and Ξ΅: the two counters #
Both counters rest on one invariant (AggQueryIn.rowBd_evaluate): a value
enters a row from a row holding it, so the row's annotation is built from
the annotations of rows holding it by operations that keep any bound
BdClosed describes. Two bounds serve: below the value's weight where Ξ΄
is the identity (leBd), and π where every row holding the value is
annotated π, which holds in every m-semiring (zeroBd).
Where Ξ΄ is the support map (muSetSim_correct_succ), a counter
holding a value carried only by rows annotated π is annotated π, and
so is every derivation through a tuple holding one: the derivations of
non-zero weight live on the tuples holding no such value, and the
successor counter runs over the counters annotated π. Rows annotated π
therefore need no fence, and the simulation is exact.
Where Ξ΄ is the identity β the Boolean algebras and the min-max
semirings β a grouping annotates a counter value by the sum of the
annotations of the rows holding it, not by π, so the successor counter
of AnnotatedMuUnion multiplies the derivations it is paired with by
annotations it should not. The all-chains counter does not: a round
pairs each derived tuple with every counter above the current one, and a
derivation is paired with every chain of counters as long as itself
(PathSum.ChainSpec). Such a semiring is absorptive with an idempotent
β, so what a derivation must meet is one chain whose annotations are
all above its own weight; then the chain absorbs nothing of it.
A chain over the values the derivation's tuples hold is one: every row
holding a value of the instance is annotated below that value's weight
(AggQueryIn.rowBd_evaluate), a tuple being free to repeat what its
predecessor holds, the query's constants and its context. There are as
many such chains as the tuples a derivation through distinct tuples can
visit, at width (2c + 2) n, which needs no bound of the plain semantics:
counting the tuples over those values is enough, for either counter.
The relations a query reads off the instance #
The relations a query reads off the instance, each with its arity:
its Rel leaves, the holes left out.
Equations
- (AggQueryIn.Rel xβ s).relLeaves = [(xβ, s)]
- (AggQueryIn.Hole xβΒΉ s xβ).relLeaves = []
- (AggQueryIn.Param pv xβ).relLeaves = []
- AggQueryIn.Empty.relLeaves = []
- (AggQueryIn.Proj ps q).relLeaves = q.relLeaves
- (AggQueryIn.Sel Ο q hΟ).relLeaves = q.relLeaves
- (qβ.Prod qβ).relLeaves = qβ.relLeaves ++ qβ.relLeaves
- (qβ.Apply qβ).relLeaves = qβ.relLeaves ++ qβ.relLeaves
- (qβ.Sum qβ).relLeaves = qβ.relLeaves ++ qβ.relLeaves
- q.Dedup.relLeaves = q.relLeaves
- (qβ.Diff qβ).relLeaves = qβ.relLeaves ++ qβ.relLeaves
- (AggQueryIn.Explode k a q).relLeaves = q.relLeaves
- (AggQueryIn.Retag h q).relLeaves = q.relLeaves
- (AggQueryIn.Mu s qβ qβ).relLeaves = qβ.relLeaves ++ qβ.relLeaves
- (AggQueryIn.MuSet s qβ qβ).relLeaves = qβ.relLeaves ++ qβ.relLeaves
- (AggQueryIn.Gamma is ts fs q keep ord).relLeaves = q.relLeaves
- (AggQueryIn.GammaScalar ts fs q ord).relLeaves = q.relLeaves
- (AggQueryIn.GammaNest is his p f q).relLeaves = q.relLeaves
- (AggQueryIn.ProvSum is his t q).relLeaves = q.relLeaves
- (AggQueryIn.GammaTok is his ts fs a q keep).relLeaves = q.relLeaves
- (AggQueryIn.Win P O o w t f q a dist keep).relLeaves = q.relLeaves
- (AggQueryIn.WinExpr P O o ws ts fs g q_1 keeps).relLeaves = q_1.relLeaves
Instances For
Dependency graph
A row is below the weights of the values it holds #
A bound on the rows holding a value: a property Bd v a of a value
and an annotation that every operator keeps β a product keeps it from
either factor, a sum from both summands, a difference from its left side,
and Ξ΄ from its argument.
Instances For
Dependency graph
A row is within the bound on its values: each value it holds is
free (F), or its annotation is within the bound Bd on that value.
Equations
Instances For
Dependency graph
The same for a tuple and its annotation.
Equations
- AggQueryIn.TupBd F Bd p = β (k : Fin n), F (p.1 k) β¨ Bd (p.1 k) p.2
Instances For
Dependency graph
The bound of a weight: a value of Vl whose weight e is above the
annotation.
Equations
- AggQueryIn.leBd Vl e v a = (Vl v β§ a β€ e v)
Instances For
Dependency graph
The bound of a value held by no row of non-zero annotation: the
annotation is π where the value is one of Z.
Equations
- AggQueryIn.zeroBd Z v a = (Z v β a = 0)
Instances For
Dependency graph
The holes of an environment bound to rows within the bound.
Equations
- AggQueryIn.HolesBd F Bd l E = β p β l, β r β E.holes p.1 p.2, AggQueryIn.RowBd F Bd r
Instances For
Dependency graph
Every row a query computes is within the bound on the values it
holds, for a bound every operator keeps (BdClosed): each value is free
β a constant of the query, a value of the context, or one the instance's
rows are given as free β or the row's annotation is within the bound on
it, as soon as the instance's rows and the rounds the holes are bound to
are. A value enters a row from a row holding it, so its annotation is
built from annotations within the bound by the operations that keep it; a
grouping's is Ξ΄ of the sum over its group.
Dependency graph
The counters, annotated by the weights of their values #
The node: a set recursion replaced by its all-chains simulation #
A set recursion is its all-chains simulation, where Ξ΄ is the
identity, at an instance where it settles, given matches qβ', qβ' of
its base and body that agree with them wherever these settle.
Dependency graph
The node: a set recursion replaced by its successor simulation #
A set recursion is its successor simulation, where Ξ΄ is the
support map and the semiring settles its linear recursions within twice the
size of their tuple set (PathSum.SettlesLinear), at every instance where the recursion settles β
rows annotated π included β given matches qβ', qβ' of its base and
body that agree with them wherever these settle. A counter value held only
by rows annotated π is annotated π, and so is every row holding it, so
the derivations of non-zero weight live on the counters annotated π.
Dependency graph
The annotated basis with Ξ΅ and without ΞΌ^βͺ, where Ξ΄ is the identity #
ΞΌ^βͺ is dispensable beside ΞΌ^β and Ξ΅ in the annotated algebra
where Ξ΄ is the identity β the Boolean algebras and the min-max
semirings, over every instance: the classes
{β
, Ξ , Ο, apply, Ξ³, win, ΞΌ^β, Ξ΅, β} match every query of the annotated
algebra in the minimal universe, every set recursion written as its
all-chains simulation.
Dependency graph
ΞΌ^βͺ is dispensable beside ΞΌ^β and Ξ΅ in the annotated algebra
where Ξ΄ is the support map, over every instance β rows annotated π
included β in the semirings that settle their linear recursions within
twice the size of their tuple set (PathSum.SettlesLinear: absorptive, β
cancellative with no zero divisors, or β equal to β on non-zero values β
β, β[X], the tropical, Viterbi and Εukasiewicz semirings, Lin[X]):
the classes {β
, Ξ , Ο, apply, Ξ³, win, ΞΌ^β, Ξ΅, β} match every query of the
annotated algebra in the minimal universe, every set recursion written as
its successor simulation.