Documentation

Provenance.AnnotatedBasisClass

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] #

@[reducible, inline]
abbrev PolyXY :

Polynomials in two variables x = X 0 and y = X 1, with coefficients in ℕ: How-provenance over two tokens.

Equations
Instances For
    Dependency graph
    @[instance_reducible]

    Any linear order serves to list the occurrences of a family.

    Equations
    Dependency graph

    The x-coefficient is at most the y-coefficient.

    Equations
    Instances For
      Dependency graph

      Every operator but the difference keeps it.

      Dependency graph

      The difference row inside the class #

      noncomputable def dDiffXY :

      The instance: R holds 0 annotated x ⊕ y, and S holds it annotated y.

      Equations
      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
        Instances For
          Dependency graph

          The nine classes generate the annotated algebra over every semiring of the class.

          Dependency graph
          theorem annEpsOps_minimal_in_class {S : Set OpKind} (hS : S ⊆ annEpsOps) (h : ∀ (K : Type) [inst : CommSemiringWithMonus K] [inst_1 : DecidableEq K] [inst_2 : HasAltLinearOrder K], AnnBasisClass K → ∀ (sch : Schema), GeneratesAnn ℕ K sch SeqAggFunc.count S) :

          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
          theorem annEpsOps_isBasis_in_class :
          (∀ (K : Type) [inst : CommSemiringWithMonus K] [inst_1 : DecidableEq K] [inst_2 : HasAltLinearOrder K], AnnBasisClass K → ∀ (sch : Schema), GeneratesAnn ℕ K sch SeqAggFunc.count annEpsOps) ∧ ∀ S ⊆ annEpsOps, (∀ (K : Type) [inst : CommSemiringWithMonus K] [inst_1 : DecidableEq K] [inst_2 : HasAltLinearOrder K], AnnBasisClass K → ∀ (sch : Schema), GeneratesAnn ℕ K sch SeqAggFunc.count S) → S = annEpsOps

          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.

          Dependency graph