Documentation

Provenance.AnnotatedWhyRow

μ^∪ 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 #

structure Graded {K : Type} [CommSemiringWithMonus K] (G : ℕ → K → Prop) :

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.

  • mono {D D' : ℕ} {a : K} : D ≤ D' → G D a → G D' a
  • zero (D : ℕ) : G D 0
  • one : G 0 1
  • add {D : ℕ} {a b : K} : G D a → G D b → G D (a + b)
  • mul {D D' : ℕ} {a b : K} : G D a → G D' b → G (D + D') (a * b)
  • sub {D : ℕ} {a : K} (b : K) : G D a → G D (a - b)
  • delta (a : K) : G 0 (SemiringWithMonus.delta a)
Instances For
    Dependency graph

    The annotations a token carries, counted #

    def NestInner.annCount {T K : Type} (j : ℕ) :
    NestInner T K j → ℕ

    How many annotations a world of an inner value multiplies at most: each occurrence of each storey, an expression family's with it.

    Equations
    Instances For
      Dependency graph
      def AggTok.annCount {T K : Type} :
      AggTok T K → ℕ

      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
      Instances For
        Dependency graph
        def AggTok.Grade {T K : Type} (G : ℕ → K → Prop) (N D : ℕ) (x : AggTok T K) :

        A token within grade D, with at most N annotations to a world.

        Equations
        Instances For
          Dependency graph
          def GenRow.Grade {T K : Type} (G : ℕ → K → Prop) (N D : ℕ) {n : ℕ} (r : GenRow T K n) :

          A row within grade D: its concrete annotation, and every token it holds. Pending factors are read only through δ, and need nothing.

          Equations
          Instances For
            Dependency graph

            The tokens the operators build #

            A family of evaluations sharing their data #

            def plainDB {T : Type} (P : Database T) (H : String → (m : ℕ) → Multiset (Tuple T m)) :

            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.

            Equations
            Instances For
              Dependency graph
              structure Member {T K : Type} [CommSemiringWithMonus K] (G : ℕ → K → Prop) (N D : ℕ) (P : Database T) {c : ℕ} (γ : Fin c → T) (H : String → (m : ℕ) → Multiset (Tuple T m)) (ρc : Fin c → ColKind) (HK : HoleKinds) (l : List (String × ℕ)) (d : AnnotatedDatabase T K) (E : EvalEnv T K) :

              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.

              Instances For
                Dependency graph
                theorem AggQueryIn.exists_grade {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {G : ℕ → K → Prop} (hG : Graded G) {S : Set OpKind} (hS : OpKind.muSet ∉ S) {Θ : Set (SeqAggFunc T)} {c n : ℕ} {κ : Fin n → ColKind} {l : List (String × ℕ)} (q : AggQueryIn T c n κ l) :
                usesOnly S q → inSig Θ q → q.noExplode → q.hygienic → l.length ≤ 1 → (∀ p ∈ l, noMention p.1 q) → ∀ {ρc : Fin c → ColKind} {HK : HoleKinds}, q.wellKinded ρc HK → ∀ (P : Database T) (γ : Fin c → T) (H : String → (m : ℕ) → Multiset (Tuple T m)) (N D : ℕ), ∃ (N' : ℕ) (D' : ℕ), N ≤ N' ∧ D ≤ D' ∧ ∀ (d : AnnotatedDatabase T K) (E : EvalEnv T K), Member G N D P γ H ρc HK l d E → q.AnnSettlesAt d γ E → ∀ r ∈ q.evaluate d γ E, GenRow.Grade G N' D' r

                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 #

                def Why.grade {α : Type} (D : ℕ) (a : Why α) :

                A why-provenance annotation of grade D: every witness has at most D variables.

                Equations
                Instances For
                  Dependency graph

                  The edge annotation and its powers #

                  def whyEdge (m : ℕ) :

                  The edge annotation: m witnesses, one variable each.

                  Equations
                  Instances For
                    Dependency graph

                    A self-loop on one tuple #

                    The witness #

                    @[instance_reducible]
                    noncomputable instance instDecidableEqWhyNat :
                    Equations
                    Dependency graph
                    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
                      Instances For
                        Dependency graph

                        μ^∪X.(R, Π₂(X × S)).

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

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

                            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).

                            Dependency graph