Documentation

Provenance.AnnotatedSum

The union from the bag recursion, annotated #

q₁ ⊎ q₂ is two bag recursions over one driver row (sumByMuK), as in the plain semantics (AggQueryIn.sumByMu), now over operands of any kinds: a round of a bag recursion carries aggregate columns, read through the environment the evaluator binds its name in. The driver row's aggregate columns hold a padding token (a count over the empty relation), which the construction never reads and drops with the driver.

The rows the construction emits are the operands' rows, each with its columns and its finalized annotation – the projections that re-tag a row cash its pending group factors, so the agreement is up to finalization (AggQueryIn.FinEq), which is all the annotated evaluation reads.

A query reads the environment's rounds only at its holes #

The construction, over operands of any kinds #

@[reducible, inline]
abbrev AggQueryIn.tagKind {k : ℕ} (κ : Fin k → ColKind) :
Fin (k + 1) → ColKind

The kinds of a tagged row: a regular tag, then the row's own kinds.

Equations
Instances For
    Dependency graph
    def AggQueryIn.withTagColsK {T : Type} {c k : ℕ} (κ : Fin k → ColKind) (t : T) :
    Fin (k + 1) → ProjColIn T c κ

    The columns of a row with a constant tag prepended, the row's own columns carried through whatever their kinds.

    Equations
    Instances For
      Dependency graph
      theorem AggQueryIn.withTagColsK_kind {T : Type} {c k : ℕ} (κ : Fin k → ColKind) (t : T) :
      (fun (j : Fin (k + 1)) => (withTagColsK κ t j).kind) = tagKind κ
      Dependency graph
      def AggQueryIn.withTagK {T : Type} {c k : ℕ} {κ : Fin k → ColKind} (t : T) (q : AggQueryIn T c k κ) :
      AggQueryIn T c (k + 1) (tagKind κ)

      A relation with the tag t prepended to every row.

      Equations
      Instances For
        Dependency graph
        def AggQueryIn.padColK {T : Type} [ValueType T] {c k : ℕ} (κ : Fin k → ColKind) (i : Fin k) :
        ProjColIn T c fun (x : Fin k) => ColKind.agg

        A padding column of kind κ i over a row of aggregate columns: a constant where the kind holds a value, the row's own token where it holds an aggregate.

        Equations
        Instances For
          Dependency graph
          theorem AggQueryIn.driverCols_kind {T : Type} [ValueType T] {c k : ℕ} (κ : Fin k → ColKind) (t : T) :
          (fun (j : Fin (k + 1)) => (Fin.cons (ProjColIn.term (TermGIn.const t)) (padColK κ) j).kind) = tagKind κ
          Dependency graph
          def AggQueryIn.driverK {T : Type} [ValueType T] {c k : ℕ} (κ : Fin k → ColKind) (cnt : SeqAggFunc T) (t : T) :
          AggQueryIn T c (k + 1) (tagKind κ)

          The driver row: tag t, the other columns padding – a token of the count of the empty relation where the kind is aggregate.

          Equations
          • One or more equations did not get rendered due to their size.
          Instances For
            Dependency graph
            Dependency graph
            Dependency graph
            def AggQueryIn.roundColsK {T : Type} {c k : ℕ} (κ : Fin k → ColKind) (p₁ : T) :
            Fin (k + 1) → ProjColIn T c (Fin.append (tagKind κ) (tagKind κ))

            The columns a round's rows are projected to: the tag p₁, then the columns of the right factor past its tag, carried through.

            Equations
            Instances For
              Dependency graph
              theorem AggQueryIn.roundColsK_kind {T : Type} {c k : ℕ} (κ : Fin k → ColKind) (p₁ : T) :
              (fun (j : Fin (k + 1)) => (roundColsK κ p₁ j).kind) = tagKind κ
              Dependency graph
              def AggQueryIn.sameTagK {T : Type} {c k : ℕ} (κ : Fin k → ColKind) :

              The selection keeping the pairs whose two tags agree.

              Equations
              Instances For
                Dependency graph
                def AggQueryIn.phaseBodyK {T : Type} {c k : ℕ} {κ : Fin k → ColKind} (s : String) (p₁ : T) (Z : AggQueryIn T c (k + 1) (tagKind κ)) :
                AggQueryIn T c (k + 1) (tagKind κ) [(s, k + 1)]

                A round of the construction: the rows of the recursive relation carrying Z's tag each read Z, whose rows are re-tagged p₁.

                Equations
                • One or more equations did not get rendered due to their size.
                Instances For
                  Dependency graph
                  def AggQueryIn.notTagK {T : Type} {c k : ℕ} (κ : Fin k → ColKind) (p₀ : T) :

                  The selection dropping the rows tagged p₀.

                  Equations
                  Instances For
                    Dependency graph
                    def AggQueryIn.unwithTagColsK {T : Type} {c k : ℕ} (κ : Fin k → ColKind) :
                    Fin k → ProjColIn T c (tagKind κ)

                    The columns past the tag.

                    Equations
                    Instances For
                      Dependency graph
                      theorem AggQueryIn.unwithTagColsK_kind {T : Type} {c k : ℕ} (κ : Fin k → ColKind) :
                      (fun (i : Fin k) => (unwithTagColsK κ i).kind) = κ
                      Dependency graph
                      def AggQueryIn.sumByMuK {T : Type} [ValueType T] {c k : ℕ} {κ : Fin k → ColKind} (s₁ s₂ : String) (cnt : SeqAggFunc T) (q₁ q₂ : AggQueryIn T c k κ) :
                      AggQueryIn T c k κ

                      ⊎ from two bag recursions, over operands of any kinds: s₁ binds the recursion listing q₁'s rows behind the driver, s₂ the one adding q₂'s. The phases are 0 and ValueType.nonzero.

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

                        What the construction computes, up to finalization #

                        def AggQueryIn.tagG {T K : Type} {k : ℕ} (t : T) (u : Tuple (GenValue T K) k) :
                        Tuple (GenValue T K) (k + 1)

                        A row with a regular tag prepended.

                        Equations
                        Instances For
                          Dependency graph

                          An empty relation of any kinds #

                          def AggQueryIn.emptyK {T : Type} [ValueType T] {c k : ℕ} (κ : Fin k → ColKind) (cnt : SeqAggFunc T) :
                          AggQueryIn T c k κ

                          An empty relation of any kinds: the driver row, dropped. Unlike AggQueryIn.emptyOf, whose parameter leaf reads constants, its aggregate columns hold tokens, so it is well-kinded at every kind vector.

                          Equations
                          Instances For
                            Dependency graph

                            What the construction keeps #

                            The two recursions, given a split body #

                            The operators a recursive body may sit under distribute over ⊎ #

                            The pass: every ⊎ replaced by the construction #

                            As in the plain semantics (AggQueryIn.exists_sumFree_aux), a ⊎ on the recursive path of a body cannot be replaced where it stands; the body is instead the sum of a body with the non-recursive side of every such ⊎ dropped and a closed query, up to finalization. At a bag recursion that settles the closed query is empty; at a set recursion it moves into the base.

                            structure AggQueryIn.SumFreeAnnOf {T : Type} [ValueType T] (S : Set OpKind) (Θ : Set (SeqAggFunc T)) (f : ℕ → String) {c n : ℕ} {κ : Fin n → ColKind} {l l' : List (String × ℕ)} (q : AggQueryIn T c n κ l) (q' : AggQueryIn T c n κ l') :

                            What the pass keeps of a query, besides its value: the classes of S, the restriction on recursive terms, the signature, the absence of an explosion, the kinds, well-formedness over a schema declaring none of the fresh names, the names (its own, or fresh ones), and the names it does not mention (fresh ones aside).

                            Instances For
                              Dependency graph
                              def AggQueryIn.ClosedMatch {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {c n : ℕ} {κ : Fin n → ColKind} {l l' : List (String × ℕ)} (q : AggQueryIn T c n κ l) (q' : AggQueryIn T c n κ l') :

                              A closed query matched: wherever it settles, in two environments agreeing up to finalization, the match settles and gives the same rows up to finalization.

                              Equations
                              • One or more equations did not get rendered due to their size.
                              Instances For
                                Dependency graph
                                def AggQueryIn.BodySplit {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {c n : ℕ} {κ : Fin n → ColKind} {l l' : List (String × ℕ)} (q : AggQueryIn T c n κ l) (q' : AggQueryIn T c n κ l') (qC : AggQueryIn T c n κ) :

                                A body split: wherever it settles, the body is the sum of the first query and the closed second one, up to finalization.

                                Equations
                                • One or more equations did not get rendered due to their size.
                                Instances For
                                  Dependency graph
                                  def AggQueryIn.ClosedMatchU {T : Type} [ValueType T] {c n : ℕ} {κ : Fin n → ColKind} {l l' : List (String × ℕ)} (q : AggQueryIn T c n κ l) (q' : AggQueryIn T c n κ l') :

                                  A match for every annotation semiring at once: the construction reads no annotation, so one query serves them all.

                                  Equations
                                  Instances For
                                    Dependency graph
                                    def AggQueryIn.BodySplitU {T : Type} [ValueType T] {c n : ℕ} {κ : Fin n → ColKind} {l l' : List (String × ℕ)} (q : AggQueryIn T c n κ l) (q' : AggQueryIn T c n κ l') (qC : AggQueryIn T c n κ) :

                                    A body split for every annotation semiring at once.

                                    Equations
                                    Instances For
                                      Dependency graph
                                      theorem AggQueryIn.exists_sumFreeAnn_aux {T : Type} [ValueType T] {S : Set OpKind} (hS : sumMuOps ⊆ S) {Θ : Set (SeqAggFunc T)} {cnt : SeqAggFunc T} (hcnt : cnt ∈ Θ) {c n : ℕ} {κ : Fin n → ColKind} {l : List (String × ℕ)} (q : AggQueryIn T c n κ l) :
                                      usesOnly (insert OpKind.union S) q → q.hygienic → inSig Θ q → ∀ (f : ℕ → String), Function.Injective f → (∀ (i : ℕ), f i ∉ q.names) → (l = [] → ∃ (q' : AggQueryIn T c n κ), SumFreeAnnOf S Θ f q q' ∧ q.ClosedMatchU q') ∧ ∀ (s : String) (m : ℕ), l = [(s, m)] → noMention s q → ∃ (q' : AggQueryIn T c n κ l) (qC : AggQueryIn T c n κ), noMention s qC ∧ SumFreeAnnOf S Θ f q q' ∧ SumFreeAnnOf S Θ f q qC ∧ q.BodySplitU q' qC

                                      The pass, both halves at once. For every query over the classes of S and ⊎ (restricted recursions, the signature Θ holding the count the construction pads with) and every injective supply of names the query does not use: a query with no ⊎, keeping what SumFreeAnnOf lists and matching the query wherever it settles; and, for a body reading the name s once, a body still reading it once and a closed query the body is the sum of. The operands of a ⊎ may carry aggregate columns.

                                      Dependency graph

                                      ⊎ is dispensable in the annotated algebra #

                                      ε, × and ⊎ are dispensable in the annotated algebra, over every schema and every commutative m-semiring: each ε is a set recursion (dedupFree), each product an apply (prodFree), and then each ⊎ the union by two bag recursions over a driver row (AggQueryIn.sumByMuK), whose operands may carry aggregate columns, the rounds of a bag recursion being bound in the environment. A ⊎ on the recursive path of a body is distributed out of it first, its closed side moving into the base of a set recursion and vanishing at a bag recursion that settles (AggQueryIn.exists_sumFreeAnn_aux). Every row, its columns and its finalized annotation are kept, which is all the annotated evaluation reads.

                                      Dependency graph