Documentation

Provenance.AnnotatedMuUnion

The set recursion from the bag recursion and ε, in the annotated semantics #

A set recursion μ^∪R.(q₀, q₁) whose body reads R once and through no union is linear in R, and duplicate elimination sums the annotations of the copies of a tuple without applying δ, so its rounds are ε of the truncated sums of the rounds of a bag recursion (PathSum). The bounded simulation of the plain semantics (MuUnion) therefore carries over, with one change: its counter must not multiply the derivations it is paired with. Here it is a successor counter: where δ is the support map, a grouping annotates a counter 𝟙 or 𝟘, and a round moves to the next counter annotated 𝟙 (wt_ctrSucc, wt_ctrLeast), the others carrying rows that weigh nothing (PathSum.SimSpec, with its two lists of counters); the rounds settle within twice the size of a tuple set where the semiring is absorptive, cancellative without zero divisors, or has ⊗ equal to ⊕ on non-zero values (PathSum.SettlesLinear), and evaluate_simResultA is the simulation's correctness under those counts.

The construction takes the counter as a parameter ch: false for the successor counter, true for the all-chains one, which serves where δ is the identity. Its width is (2c + 2) n + 2 either way (ctrWidth). The pass is correct wherever its node is (AggQueryIn.NodeCorrect), and so is the basis theorem (generatesAnnOn_annEpsOps_of); the two nodes are proved in Provenance.AnnotatedChains.

This module works on the annotated relation a query gives, ann, which is all the construction reads: every relation it builds is all-regular.

@[instance_reducible, instance 50]

The commutative semiring underlying a commutative m-semiring, which PathSum speaks in.

Equations
Dependency graph
noncomputable def AggQueryIn.ann {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {c n : ℕ} {κ : Fin n → ColKind} {l : List (String × ℕ)} (q : AggQueryIn T c n κ l) (d : AnnotatedDatabase T K) (γ : Fin c → T) (E : EvalEnv T K) :

The annotated relation of a query in an environment: its rows, each read as a tuple of values with its finalized annotation.

Equations
Instances For
    Dependency graph

    A linear term reads its recursive relation row by row #

    The recursive relation replaced by the current row #

    def AggQueryIn.paramRow {T K : Type} [CommSemiringWithMonus K] {c n : ℕ} (E : EvalEnv T K) (γ : Fin c → T) (pv : Fin n → T ⊕ Fin c) :
    GenRow T K n

    The row a Param leaf reading pv gives, whatever its kinds say.

    Equations
    Instances For
      Dependency graph

      The successor counter #

      def AggQueryIn.halvesLt {T : Type} [ValueType T] {c : ℕ} (K : ℕ) :

      The first half of a row strictly below its second half.

      Equations
      Instances For
        Dependency graph
        def AggQueryIn.midLt {T : Type} [ValueType T] {c : ℕ} (K : ℕ) :
        GenPredIn T c (ColKind.allReg (K + K + K))

        The middle third of a row strictly between its first and last.

        Equations
        • One or more equations did not get rendered due to their size.
        Instances For
          Dependency graph
          def AggQueryIn.eqOuter {T : Type} [ValueType T] {c : ℕ} (n K : ℕ) :
          GenPredIn T (n + K + c) (ColKind.allReg (K + K))

          The first half of a row equals the counter of the current row of an apply, read off its outer columns.

          Equations
          • One or more equations did not get rendered due to their size.
          Instances For
            Dependency graph
            def AggQueryIn.outerThirds (K : ℕ) (j : Fin (K + K)) :
            Fin (K + K + K)

            The column of the first and the last third of a row of three counters.

            Equations
            Instances For
              Dependency graph
              def AggQueryIn.keepCols {T : Type} {c n m : ℕ} {l : List (String × ℕ)} (cols : Fin m → Fin n) (q : AggQueryIn T c n (ColKind.allReg n) l) :

              Keeping the columns cols of an all-regular relation.

              Equations
              Instances For
                Dependency graph
                def AggQueryIn.ctr {T : Type} {c : ℕ} (EQ : AggQueryIn T c 1 (ColKind.allReg 1)) (K : ℕ) :

                The counters: the K-tuples over the values of EQ, each once.

                Equations
                Instances For
                  Dependency graph
                  def AggQueryIn.ctrLt {T : Type} [ValueType T] {c : ℕ} (EQ : AggQueryIn T c 1 (ColKind.allReg 1)) (K : ℕ) :
                  AggQueryIn T c (K + K) (ColKind.allReg (K + K))

                  The pairs of counters, the first below the second.

                  Equations
                  Instances For
                    Dependency graph
                    def AggQueryIn.ctrMid {T : Type} [ValueType T] {c : ℕ} (EQ : AggQueryIn T c 1 (ColKind.allReg 1)) (K : ℕ) :
                    AggQueryIn T c (K + K) (ColKind.allReg (K + K))

                    The pairs of counters with one counter strictly between, once per counter between.

                    Equations
                    Instances For
                      Dependency graph
                      def AggQueryIn.ctrSucc {T : Type} [ValueType T] {c : ℕ} (EQ : AggQueryIn T c 1 (ColKind.allReg 1)) (K : ℕ) :
                      AggQueryIn T c (K + K) (ColKind.allReg (K + K))

                      The successor relation: the pairs of counters, the first below the second, annotated 𝟙 where nothing is between and 𝟘 elsewhere.

                      Equations
                      Instances For
                        Dependency graph
                        def AggQueryIn.ctrLeast {T : Type} [ValueType T] {c : ℕ} (EQ : AggQueryIn T c 1 (ColKind.allReg 1)) (K : ℕ) :

                        The least counter: every counter, annotated 𝟙 where none is below it and 𝟘 elsewhere.

                        Equations
                        Instances For
                          Dependency graph
                          def AggQueryIn.ctrStep {T : Type} [ValueType T] {c : ℕ} (ch : Bool) (EQ : AggQueryIn T c 1 (ColKind.allReg 1)) (K : ℕ) :
                          AggQueryIn T c (K + K) (ColKind.allReg (K + K))

                          The step relation of a counter: the successor relation, or, for the all-chains counter (ch = true), every ordered pair of counters.

                          Equations
                          Instances For
                            Dependency graph
                            def AggQueryIn.ctrStart {T : Type} [ValueType T] {c : ℕ} (ch : Bool) (EQ : AggQueryIn T c 1 (ColKind.allReg 1)) (K : ℕ) :

                            The counters a simulation starts from: the least one, or, for the all-chains counter (ch = true), every counter.

                            Equations
                            Instances For
                              Dependency graph
                              def AggQueryIn.ctrNext {T : Type} [ValueType T] {c : ℕ} (ch : Bool) (EQ : AggQueryIn T c 1 (ColKind.allReg 1)) (n K : ℕ) :
                              AggQueryIn T (n + K + c) K (ColKind.allReg K)

                              The counters after the current row's, under an apply over the simulation's rows: the step relation's second halves, where the first half is the current row's counter.

                              Equations
                              • One or more equations did not get rendered due to their size.
                              Instances For
                                Dependency graph
                                def AggQueryIn.simBodyA {T : Type} [ValueType T] {c : ℕ} (s s' : String) (n K : ℕ) (ch : Bool) (EQ : AggQueryIn T c 1 (ColKind.allReg 1)) (L : AggQueryIn T c n (ColKind.allReg n) [(s, n)]) :
                                AggQueryIn T c (n + K) (ColKind.allReg (n + K)) [(s', n + K)]

                                One round of the annotated simulation: for each row, the term at its tuple part, paired with the counter after the row's.

                                Equations
                                • One or more equations did not get rendered due to their size.
                                Instances For
                                  Dependency graph
                                  def AggQueryIn.simA {T : Type} [ValueType T] {c : ℕ} (s s' : String) (n K : ℕ) (ch : Bool) (EQ : AggQueryIn T c 1 (ColKind.allReg 1)) (BQ : AggQueryIn T c n (ColKind.allReg n)) (L : AggQueryIn T c n (ColKind.allReg n) [(s, n)]) :
                                  AggQueryIn T c (n + K) (ColKind.allReg (n + K))

                                  The annotated simulation: a bag recursion over a tuple and a counter, from the base paired with the starting counters.

                                  Equations
                                  Instances For
                                    Dependency graph
                                    def AggQueryIn.simResultA {T : Type} [ValueType T] {c : ℕ} (s s' : String) (n K : ℕ) (ch : Bool) (EQ : AggQueryIn T c 1 (ColKind.allReg 1)) (BQ : AggQueryIn T c n (ColKind.allReg n)) (L : AggQueryIn T c n (ColKind.allReg n) [(s, n)]) :

                                    Its tuple parts, duplicates eliminated: the set recursion's value.

                                    Equations
                                    Instances For
                                      Dependency graph
                                      def AggQueryIn.powT {T : Type} (V : Multiset (Tuple T 1)) (K : ℕ) :

                                      The K-tuples over a set of unary rows.

                                      Equations
                                      Instances For
                                        Dependency graph
                                        def AggQueryIn.ltPairs {T : Type} [ValueType T] {K' : ℕ} (W : Multiset (Tuple T K')) :
                                        Multiset (Tuple T (K' + K'))

                                        The tuples of the ordered pairs of counters.

                                        Equations
                                        Instances For
                                          Dependency graph

                                          One round of the simulation, and its rounds #

                                          noncomputable def AggQueryIn.simRow {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {c : ℕ} (s : String) (n K' : ℕ) (ch : Bool) (EQ : AggQueryIn T c 1 (ColKind.allReg 1)) (L : AggQueryIn T c n (ColKind.allReg n) [(s, n)]) (d : AnnotatedDatabase T K) (γ : Fin c → T) (E : EvalEnv T K) (u : Tuple T (n + K')) :
                                          AnnotatedRelation T K (n + K')

                                          The right side of one round of the simulation, at a row u: the term at its tuple part, paired with the counters after its counter.

                                          Equations
                                          • One or more equations did not get rendered due to their size.
                                          Instances For
                                            Dependency graph

                                            The simulation, read as PathSum.SimSpec #

                                            def AggQueryIn.splitRow {T K : Type} {n K' : ℕ} (p : AnnotatedTuple T K (n + K')) :
                                            (Tuple T n × Tuple T K') × K

                                            Splitting a row of the simulation into its tuple and its counter.

                                            Equations
                                            Instances For
                                              Dependency graph

                                              Settling #

                                              The counter values: the leaves' values and the constants #

                                              def AggQueryIn.valParts {T : Type} {c : ℕ} (ls : List (ℕ × String)) (cs : List T) :

                                              The unary relations the counter values are the union of: each column of each leaf, and each constant.

                                              Equations
                                              Instances For
                                                Dependency graph
                                                def AggQueryIn.valRel {T : Type} [ValueType T] {c : ℕ} (ls : List (ℕ × String)) (cs : List T) :

                                                The counter values: the non-null values of the leaves ls and of the constants cs. Unlike the plain counter relation it reads no context value, so it is well-kinded under any context.

                                                Equations
                                                Instances For
                                                  Dependency graph

                                                  Iterations that agree, and the settled set #

                                                  The node: a set recursion replaced by its simulation #

                                                  def AggQueryIn.ctrLeaves {T : Type} {c n : ℕ} (s : String) (q₀ : AggQueryIn T c n (ColKind.allReg n)) (q₁ : AggQueryIn T c n (ColKind.allReg n) [(s, n)]) :

                                                  The leaves the counter of a set recursion reads.

                                                  Equations
                                                  Instances For
                                                    Dependency graph
                                                    noncomputable def AggQueryIn.ctrConsts {T : Type} [ValueType T] {c n : ℕ} (s : String) (q₀ : AggQueryIn T c n (ColKind.allReg n)) (q₁ : AggQueryIn T c n (ColKind.allReg n) [(s, n)]) :

                                                    The constants the counter of a set recursion reads: the recursion's own, and two more, so that there are at least two counter values.

                                                    Equations
                                                    Instances For
                                                      Dependency graph

                                                      The width of the counter: (2c + 2) n + 2, which the values of the rows alone bound (AggQueryIn.card_arith_chain), with room for twice as many counters as tuples (AggQueryIn.card_arith_succ).

                                                      Equations
                                                      Instances For
                                                        Dependency graph
                                                        noncomputable def AggQueryIn.muSetSim {T : Type} [ValueType T] {c : ℕ} (ch : Bool) {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)]) :

                                                        The query a set recursion is replaced by.

                                                        Equations
                                                        Instances For
                                                          Dependency graph

                                                          What the simulation mentions, and that it explodes nothing #

                                                          The pass #

                                                          noncomputable def AggQueryIn.muSetFreeA {T : Type} [ValueType T] (ch : Bool) (f : ℕ → String) {c n : ℕ} {κ : Fin n → ColKind} {l : List (String × ℕ)} :
                                                          AggQueryIn T c n κ l → AggQueryIn T c n κ l

                                                          Every set recursion replaced by its simulation, the supply split in three at each node, the recursion's own fresh name the supply's first.

                                                          Equations
                                                          Instances For
                                                            Dependency graph

                                                            What the pass asks of its node: at the instances P admits, a set recursion that settles is its simulation, given matches of its base and body that agree with them wherever these settle.

                                                            Equations
                                                            • One or more equations did not get rendered due to their size.
                                                            Instances For
                                                              Dependency graph

                                                              The classes the pass uses #

                                                              Dependency graph

                                                              The signature of the pass's output #

                                                              The kinds of the pass's output #

                                                              The names of the pass's output #

                                                              Hygiene and the schema of the pass's output #

                                                              The annotated basis with ε and without μ^∪ #

                                                              The annotated basis with ε: {∅, Π, σ, apply, γ, win, μ^⊎, ε, −}, the classes other than ×, ⊎ and μ^∪.

                                                              Equations
                                                              Instances For
                                                                Dependency graph

                                                                A set of classes generates the annotated algebra over the instances P admits: GeneratesAnn, with the instances restricted.

                                                                Equations
                                                                • One or more equations did not get rendered due to their size.
                                                                Instances For
                                                                  Dependency graph

                                                                  The classes {∅, Π, σ, apply, γ, win, μ^⊎, ε, −} match every query of the annotated algebra in the minimal universe, at the instances P admits, wherever the simulation of a set recursion is correct there: the products are written as applies, the unions as bag recursions, and every set recursion as the counter simulation of AggQueryIn.muSetFreeA, whose own unions are written as bag recursions in turn. The construction reads no annotation, so one query serves every semiring at once, at the instances where the counter ch simulates a set recursion.

                                                                  Dependency graph
                                                                  theorem generatesAnnOn_annEpsOps_of {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] (sch : Schema) (cnt : SeqAggFunc T) (ch : Bool) {P : AnnotatedDatabase T K → Prop} (hnode : AggQueryIn.NodeCorrect cnt ch P) :

                                                                  The classes {∅, Π, σ, apply, γ, win, μ^⊎, ε, −} match every query of the annotated algebra in the minimal universe, at the instances P admits, wherever the simulation of a set recursion is correct there.

                                                                  Dependency graph