The annotated basis over a class of semirings #
The nine classes {∅, Π, σ, apply, γ, win, μ^⊎, ε, −} are a basis of the
annotated algebra over the m-semirings where δ is the support map and a
linear set recursion settles within twice the size of its tuple set
(PathSum.SettlesLinear, which holds of ℕ, ℕ[X] and the lineage
semiring), or where δ is the identity (AnnBasisClass): they generate
it over every such semiring (generatesAnn_annEpsOps_of_class), and no
proper subset does over all of them (annEpsOps_minimal_in_class). The
why-provenance semiring Why[X] has the support map but not the bound:
a cycle over an edge carrying m witnesses settles only after m rounds.
The generation half is generatesAnn_annEpsOps_of_support and
generatesAnn_annEpsOps_of_delta_id. For minimality every row needs a
witness inside the class. ℕ is in it and carries all of them but the
difference's: ℕ × ℕ, where the difference row was first checked, has
zero divisors and is not absorptive. The difference's witness inside the
class is ℕ[x, y] (PolyXY): on one instance, R holding a tuple
annotated x ⊕ y and S holding it annotated y, R − S gives x,
while every annotation a query without a difference builds has an
x-coefficient at most its y-coefficient (PolyXY.annClosed_xLeY) – a
property of 𝟘, 𝟙, sums and products, of δ and of 𝟙 ⊖ ·, the last
two giving constants.
ℕ[x, y] #
Polynomials in two variables x = X 0 and y = X 1, with
coefficients in ℕ: How-provenance over two tokens.
Equations
- PolyXY = MvPolynomial (Fin 2) ℕ
Instances For
Dependency graph
Any linear order serves to list the occurrences of a family.
Equations
- PolyXY.instHasAltLinearOrder = { altOrder := linearOrderOfSTO WellOrderingRel }
Dependency graph
The x-coefficient is at most the y-coefficient.
Equations
- p.XLeY = (p.coeff (Finsupp.single 0 1) ≤ p.coeff (Finsupp.single 1 1))
Instances For
Dependency graph
Dependency graph
The difference row inside the class #
The instance: R holds 0 annotated x ⊕ y, and S holds it
annotated y.
Equations
- dDiffXY = AnnotatedDatabase.assign "R" {(fun (x : Fin 1) => 0, MvPolynomial.X 0 + MvPolynomial.X 1)} (AnnotatedDatabase.assign "S" {(fun (x : Fin 1) => 0, MvPolynomial.X 1)} [])
Instances For
Dependency graph
− is in every set generating the annotated algebra over
ℕ[x, y], which is in the class of AnnBasisClass.
Dependency graph
The class, and the basis theorem #
The m-semirings the basis theorem is about: δ the support map
with linear set recursions settling within twice the size of their tuple
set, or δ the identity.
Equations
- AnnBasisClass K = ((∀ (a : K), a ≠ 0 → SemiringWithMonus.delta a = 1) ∧ PathSum.SettlesLinear K ∨ ∀ (a : K), SemiringWithMonus.delta a = a)
Instances For
Dependency graph
The nine classes generate the annotated algebra over every semiring of the class.
Dependency graph
No proper subset of the nine classes generates the annotated algebra
over every semiring of the class, with the counting aggregate: ℕ
carries every row but the difference's, which ℕ[x, y] carries.
Dependency graph
The annotated basis theorem over the class: the nine classes
generate the annotated algebra over every semiring of AnnBasisClass, and
no proper subset of them does over all of those semirings.