μ^∪ is necessary in the annotated algebra: the why-provenance semiring #
Over the why-provenance semiring Why[X], a set recursion cannot be
replaced by bag recursions, duplicate elimination and the other
operators. On one value a, with S = {a} annotated 𝟙 and
E = {(a, a)} annotated {{x₁}, …, {x_m}}, the set recursion
μ^∪R.(S, Π₁(R ⋈ E)) settles after m rounds, and its row carries the
witness {x₁, …, x_m}. The data does not depend on m, so a query
without μ^∪ runs the same rounds, groups and frames on every instance
of the family: its annotations are built from the input ones by a number
of products bounded by the query and the data alone, and their witnesses
are unions of boundedly many input witnesses.
The argument is a graded invariant (Graded): a family of properties
G D of annotations, closed under sums, under monus on the left and
under δ, with products adding the grades. Why.grade D a says that
every witness of a has at most D variables. No single instance can
separate the classes: the fixpoint of a linear recursion is a finite sum
of powers of its input annotations, which sums and products reach.
The basis theorem follows (annMuOps_isBasis): {∅, Π, σ, apply, γ, win, μ^⊎, −, μ^∪} generates the annotated algebra over every commutative
m-semiring, and no proper subset of it does over all of them. It holds up
to ≈ too (annMuOps_isBasis_approx): the passes agree with their source
row by row up to finalization, and the witness's row is not 𝟘.
Graded properties of annotations #
A grading of the annotations: G D a says a has grade at most
D. It is monotone, holds of 𝟘 at every grade and of 𝟙 at grade 0,
of sums at the larger grade, of products at the sum of the grades, of a
monus at its left argument's grade, and of δ at grade 0.
- zero (D : ℕ) : G D 0
- one : G 0 1
- delta (a : K) : G 0 (SemiringWithMonus.delta a)
Instances For
Dependency graph
The annotations a token carries, counted #
How many annotations a world of an inner value multiplies at most: each occurrence of each storey, an expression family's with it.
Equations
- NestInner.annCount 0 e = e.occs.length
- NestInner.annCount j.succ (Sum.inl x_2) = NestInner.annCount j x_2
- NestInner.annCount j.succ (Sum.inr N) = (Multiset.map (fun (o : NestInner T K j × K) => 1 + NestInner.annCount j o.1) N.occs).sum
Instances For
Dependency graph
How many annotations a world of a token multiplies at most: its occurrences, and for a nested value each of its own occurrences and every inner one, at every storey.
Equations
- (AggTok.tok a).annCount = a.occs.length
- (AggTok.expr e).annCount = e.occs.length
- (AggTok.nest a).annCount = (Multiset.map (fun (o : NestInner T K a.lev × K) => 1 + NestInner.annCount a.lev o.1) a.occs).sum
Instances For
Dependency graph
A token within grade D, with at most N annotations to a world.
Equations
- AggTok.Grade G N D x = (AggTok.AnnsIn (G D) x ∧ x.annCount ≤ N)
Instances For
Dependency graph
A row within grade D: its concrete annotation, and every token
it holds. Pending factors are read only through δ, and need nothing.
Equations
- GenRow.Grade G N D r = (G D r.2.base ∧ ∀ (k : Fin n) (a : AggTok T K), r.1 k = Sum.inr a → AggTok.Grade G N D a)
Instances For
Dependency graph
The tokens the operators build #
A family of evaluations sharing their data #
The plain instance a family's evaluations read: the instance's data, the one hole of a recursive term bound to its round's data.
Instances For
Dependency graph
A member of a family of evaluations: an annotated instance and an
environment whose data is P and, at the holes, H, and whose
annotations are within grade D, with at most N annotations to a
token's world.
- holesPlain (p : String × ℕ) : p ∈ l → Multiset.map (fun (r : GenRow T K p.2) => GenRow.plainTuple r.1) (E.holes p.1 p.2) = H p.1 p.2
- inst (m : ℕ) (s : String) (r : AnnotatedRelation T K m) : AnnotatedDatabase.find m s d = some r → ∀ x ∈ r, G D x.2
- kinded : E.Kinded γ ρc HK
Instances For
Dependency graph
The uniform bound: a query without μ^∪ has, over a family of
evaluations sharing their data, annotations within one grade – the data
fixes its rounds, its groups and its frames, and so how many products it
takes.
Dependency graph
The grading of Why[X]: the size of a witness #
A why-provenance annotation of grade D: every witness has at most
D variables.
Instances For
Dependency graph
The edge annotation and its powers #
The edge annotation: m witnesses, one variable each.
Instances For
Dependency graph
A self-loop on one tuple #
The witness #
Equations
Dependency graph
Equations
- instHasAltLinearOrderWhyNat = { altOrder := linearOrderOfSTO WellOrderingRel }
Dependency graph
The instances: R holds 0 annotated 𝟙, and S holds 0
annotated by the m one-variable witnesses.
Equations
Instances For
Dependency graph
The body: the recursive relation joined with S, kept on S's
column.
Equations
- whyBody = AggQueryIn.Proj (fun (x : Fin 1) => ProjColIn.term (TermGIn.index 1 whyBody._proof_2)) ((AggQueryIn.Hole 1 "X").Prod (AggQueryIn.Rel 1 "S"))
Instances For
Dependency graph
μ^∪X.(R, Π₂(X × S)).
Equations
- whyWitness = AggQueryIn.MuSet "X" (AggQueryIn.Rel 1 "R") whyBody
Instances For
Dependency graph
The row #
μ^∪ is in every set generating the annotated algebra over Why[X],
with the counting aggregate. Over the instances dWhy m, which share their
data, a query without μ^∪ keeps its annotations within one grade
(AggQueryIn.exists_grade), while μ^∪X.(R, Π₂(X × S)) gives a row with
a witness of m variables.
Dependency graph
The annotated basis theorem #
The basis of the annotated algebra: {∅, Π, σ, apply, γ, win, μ^⊎, −, μ^∪}, the classes of the whole algebra but ε, × and ⊎.
Equations
Instances For
Dependency graph
The annotated basis theorem: {∅, Π, σ, apply, γ, win, μ^⊎, −, μ^∪}
generates the annotated algebra in the minimal universe over every
commutative m-semiring, and no proper subset of it does over all of them.
In particular set recursion is required: over Why[X] no set of classes
without μ^∪ generates (muSet_mem_of_generatesAnn).
Dependency graph
With ε in place of μ^∪ the classes do not generate over Why[X]:
the set {∅, Π, σ, apply, γ, win, μ^⊎, ε, −}, which generates over the
semirings of AnnBasisClass, misses μ^∪.
Dependency graph
Up to ≈ #
μ^∪ is in every set generating the annotated algebra over Why[X]
up to ≈, with the counting aggregate: the witness's row is not 𝟘, so
≈ keeps it, and a match without μ^∪ has no row annotated with a witness
of m variables.
Dependency graph
The annotated basis theorem up to ≈: {∅, Π, σ, apply, γ, win, μ^⊎, −, μ^∪} generates
the annotated algebra up to ≈ over every commutative m-semiring, and no
proper subset of it does over all of them – set recursion being required
over Why[X] (muSet_mem_of_generatesAnnZ).