Documentation

Provenance.AnnotatedChains

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 #

def AggQueryIn.relLeaves {T : Type} {c n : β„•} {ΞΊ : Fin n β†’ ColKind} {l : List (String Γ— β„•)} :
AggQueryIn T c n ΞΊ l β†’ List (β„• Γ— String)

The relations a query reads off the instance, each with its arity: its Rel leaves, the holes left out.

Equations
Instances For
    Dependency graph

    A row is below the weights of the values it holds #

    structure AggQueryIn.BdClosed {T K : Type} [CommSemiringWithMonus K] (Bd : T β†’ K β†’ Prop) :

    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.

    • mul_right (v : T) (a b : K) : Bd v a β†’ Bd v (a * b)
    • mul_left (v : T) (a b : K) : Bd v b β†’ Bd v (a * b)
    • add (v : T) (a b : K) : Bd v a β†’ Bd v b β†’ Bd v (a + b)
    • monus (v : T) (a b : K) : Bd v a β†’ Bd v (a - b)
    • delta (v : T) (a : K) : Bd v a β†’ Bd v (SemiringWithMonus.delta a)
    Instances For
      Dependency graph
      def AggQueryIn.RowBd {T K : Type} [CommSemiringWithMonus K] (F : T β†’ Prop) (Bd : T β†’ K β†’ Prop) {n : β„•} (r : GenRow T K n) :

      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
        def AggQueryIn.TupBd {T K : Type} (F : T β†’ Prop) (Bd : T β†’ K β†’ Prop) {n : β„•} (p : Tuple T n Γ— K) :

        The same for a tuple and its annotation.

        Equations
        Instances For
          Dependency graph
          @[reducible, inline]
          abbrev AggQueryIn.leBd {T K : Type} [CommSemiringWithMonus K] (Vl : T β†’ Prop) (e : T β†’ K) (v : T) (a : K) :

          The bound of a weight: a value of Vl whose weight e is above the annotation.

          Equations
          Instances For
            Dependency graph
            @[reducible, inline]
            abbrev AggQueryIn.zeroBd {T K : Type} [CommSemiringWithMonus K] (Z : T β†’ Prop) (v : T) (a : K) :

            The bound of a value held by no row of non-zero annotation: the annotation is 𝟘 where the value is one of Z.

            Equations
            Instances For
              Dependency graph
              def AggQueryIn.HolesBd {T K : Type} [CommSemiringWithMonus K] (F : T β†’ Prop) (Bd : T β†’ K β†’ Prop) (l : List (String Γ— β„•)) (E : EvalEnv T K) :

              The holes of an environment bound to rows within the bound.

              Equations
              Instances For
                Dependency graph
                theorem AggQueryIn.rowBd_evaluate {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {Bd : T β†’ K β†’ Prop} (hB : BdClosed Bd) {d : AnnotatedDatabase T K} {Θ : Set (SeqAggFunc T)} {c n : β„•} {ΞΊ : Fin n β†’ ColKind} {l : List (String Γ— β„•)} (q : AggQueryIn T c n ΞΊ l) :
                inSig Θ q β†’ q.noExplode β†’ βˆ€ {ρc : Fin c β†’ ColKind} {HK : HoleKinds}, q.wellKinded ρc HK β†’ βˆ€ (F : T β†’ Prop), (βˆ€ x ∈ q.allConsts, F x) β†’ (βˆ€ p ∈ q.relLeaves, βˆ€ (r : AnnotatedRelation T K p.1), AnnotatedDatabase.find p.1 p.2 d = some r β†’ βˆ€ a ∈ r, TupBd F Bd (a.1, a.2)) β†’ βˆ€ (Ξ³ : Fin c β†’ T) (E : EvalEnv T K), (βˆ€ (k : Fin c), (ρc k).base β‰  ColKind.agg β†’ F (Ξ³ k)) β†’ (βˆ€ (k : Fin c) (v : T), E.ctxAt c Ξ³ k = Sum.inl v β†’ F v) β†’ HolesBd F Bd l E β†’ βˆ€ r ∈ q.evaluate d Ξ³ E, RowBd F Bd r

                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 #

                theorem AggQueryIn.muSetSim_correct_chain {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {c : β„•} (cnt : SeqAggFunc T) (hΞ΄ : βˆ€ (a : K), SemiringWithMonus.delta a = a) {n : β„•} (s s' : String) (qβ‚€ : AggQueryIn T c n (ColKind.allReg n)) (q₁ : AggQueryIn T c n (ColKind.allReg n) [(s, n)]) (qβ‚€' : AggQueryIn T c n (ColKind.allReg n)) (q₁' : AggQueryIn T c n (ColKind.allReg n) [(s, n)]) (hq₁ : recLinear s n q₁) (hq₁x : q₁.noExplode) (hq₁' : recLinear s n q₁') (hq₁'x : q₁'.noExplode) (hsig : inSig {cnt} (MuSet s qβ‚€ q₁)) (hhyg : (MuSet s qβ‚€ q₁).hygienic) (hx : (MuSet s qβ‚€ q₁).noExplode) {ρc : Fin c β†’ ColKind} {HK : HoleKinds} (hwk : (MuSet s qβ‚€ q₁).wellKinded ρc HK) (d : AnnotatedDatabase T K) (Ξ³ : Fin c β†’ T) (E : EvalEnv T K) (hset : (MuSet s qβ‚€ q₁).AnnSettlesAt d Ξ³ E) (hβ‚€ : qβ‚€'.AnnSettlesAt d Ξ³ E ∧ qβ‚€'.evaluate d Ξ³ E = qβ‚€.evaluate d Ξ³ E) (h₁ : βˆ€ (X : AnnotatedRelation T K n), q₁.AnnSettlesAt d Ξ³ (E.assignHole s (Multiset.map GenRow.ofAnnotated X)) β†’ q₁'.AnnSettlesAt d Ξ³ (E.assignHole s (Multiset.map GenRow.ofAnnotated X)) ∧ q₁'.evaluate d Ξ³ (E.assignHole s (Multiset.map GenRow.ofAnnotated X)) = q₁.evaluate d Ξ³ (E.assignHole s (Multiset.map GenRow.ofAnnotated X))) :
                (muSetSim true s s' qβ‚€ q₁ qβ‚€' q₁').AnnSettlesAt d Ξ³ E ∧ (muSetSim true s s' qβ‚€ q₁ qβ‚€' q₁').evaluate d Ξ³ E = (MuSet s qβ‚€ q₁).evaluate d Ξ³ E

                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 #

                theorem AggQueryIn.muSetSim_correct_succ {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {c : β„•} (cnt : SeqAggFunc T) (hΞ΄ : βˆ€ (a : K), a β‰  0 β†’ SemiringWithMonus.delta a = 1) (hK : PathSum.SettlesLinear K) {n : β„•} (s s' : String) (qβ‚€ : AggQueryIn T c n (ColKind.allReg n)) (q₁ : AggQueryIn T c n (ColKind.allReg n) [(s, n)]) (qβ‚€' : AggQueryIn T c n (ColKind.allReg n)) (q₁' : AggQueryIn T c n (ColKind.allReg n) [(s, n)]) (hq₁ : recLinear s n q₁) (hq₁x : q₁.noExplode) (hq₁' : recLinear s n q₁') (hq₁'x : q₁'.noExplode) (hsig : inSig {cnt} (MuSet s qβ‚€ q₁)) (hhyg : (MuSet s qβ‚€ q₁).hygienic) (hx : (MuSet s qβ‚€ q₁).noExplode) {ρc : Fin c β†’ ColKind} {HK : HoleKinds} (hwk : (MuSet s qβ‚€ q₁).wellKinded ρc HK) (d : AnnotatedDatabase T K) (Ξ³ : Fin c β†’ T) (E : EvalEnv T K) (hset : (MuSet s qβ‚€ q₁).AnnSettlesAt d Ξ³ E) (hβ‚€ : qβ‚€'.AnnSettlesAt d Ξ³ E ∧ qβ‚€'.evaluate d Ξ³ E = qβ‚€.evaluate d Ξ³ E) (h₁ : βˆ€ (X : AnnotatedRelation T K n), q₁.AnnSettlesAt d Ξ³ (E.assignHole s (Multiset.map GenRow.ofAnnotated X)) β†’ q₁'.AnnSettlesAt d Ξ³ (E.assignHole s (Multiset.map GenRow.ofAnnotated X)) ∧ q₁'.evaluate d Ξ³ (E.assignHole s (Multiset.map GenRow.ofAnnotated X)) = q₁.evaluate d Ξ³ (E.assignHole s (Multiset.map GenRow.ofAnnotated X))) :
                (muSetSim false s s' qβ‚€ q₁ qβ‚€' q₁').AnnSettlesAt d Ξ³ E ∧ (muSetSim false s s' qβ‚€ q₁ qβ‚€' q₁').evaluate d Ξ³ E = (MuSet s qβ‚€ q₁).evaluate d Ξ³ E

                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 #

                theorem generatesAnn_annEpsOps_of_delta_id {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] (sch : Schema) (cnt : SeqAggFunc T) (hΞ΄ : βˆ€ (a : K), SemiringWithMonus.delta a = a) :

                ΞΌ^βˆͺ 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
                theorem generatesAnn_annEpsOps_of_support {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] (sch : Schema) (cnt : SeqAggFunc T) (hΞ΄ : βˆ€ (a : K), a β‰  0 β†’ SemiringWithMonus.delta a = 1) (hK : PathSum.SettlesLinear K) :

                ΞΌ^βˆͺ 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.

                Dependency graph