Documentation

Provenance.AnnotatedProd

The product from the apply, annotated #

q₁ × q₂ is the apply of q₁ with q₂ read under the ambient context only, in every semiring: both build the row (u, v) annotated α_u ⊗ β_v (evaluate_prodApply). Since an apply's left side may carry aggregate columns, so may the factors, and nothing re-types a token.

In a recursive term whose hole is in the right factor the apply cannot take that factor as its right side, which must be closed, so the two factors are swapped and the columns put back by a projection (AggQueryIn.prodSwap). A projection cashes the pending group factors of the groups whose tokens it does not keep, so the rows it builds differ from the product's in how their annotation is split between the concrete part and the pending factors – never in what the annotation finalizes to. What is preserved is therefore agreement up to finalization (AggQueryIn.FinEq): the same columns, tokens included, and the same finalized annotations, which every operator respects (the selection on an aggregate value through GenAnn.finalize_sel, its superseded factors being absorbed by the comparison) and which is all the annotated evaluation reads.

prodFree replaces each product, and generatesAnn_dedupProdFree says the classes other than ε and × generate the annotated algebra.

Agreement up to finalization #

def EvalEnv.FinRel {T K : Type} [CommSemiringWithMonus K] {c : ℕ} (γ : Fin c → T) (E E' : EvalEnv T K) :

Two environments agree up to finalization, at a context arity: the same context there, and rounds whose rows finalize alike.

Equations
Instances For
    Dependency graph
    def AggQueryIn.FinEq {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') :

    Two queries agree up to finalization: on every instance, in every context, and in two environments agreeing up to finalization, the same rows with the same columns and the same finalized annotations.

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

      Every operator respects it #

      Agreement up to finalization at two given environments: what each operator makes of it, operator by operator.

      theorem AggQueryIn.FinEq.proj {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {c n m : ℕ} {κ : Fin n → ColKind} {l l' : List (String × ℕ)} (ps : Tuple (ProjColIn T c κ) m) {q : AggQueryIn T c n κ l} {q' : AggQueryIn T c n κ l'} (h : q.FinEq q') :
      (Proj ps q).FinEq (Proj ps q')
      Dependency graph

      Substitution keeps the fences and the settling #

      A column carried through, in any context #

      def carryColIn {T : Type} {c n : ℕ} (κ : Fin n → ColKind) (k : Fin n) :
      ProjColIn T c κ

      A column carried through a projection whatever its kind – carryCol in a context of any arity.

      Equations
      Instances For
        Dependency graph

        The product as an apply #

        theorem swapCarry_kind {T : Type} {c n₁ n₂ : ℕ} (κ₁ : Fin n₁ → ColKind) (κ₂ : Fin n₂ → ColKind) :
        (fun (j : Fin (n₁ + n₂)) => (carryColIn (Fin.append κ₂ κ₁) (swapIdx n₁ n₂ j)).kind) = Fin.append κ₁ κ₂
        Dependency graph
        def prodAnn {T : Type} {c n₁ n₂ : ℕ} {κ₁ : Fin n₁ → ColKind} {κ₂ : Fin n₂ → ColKind} {l₁ l₂ : List (String × ℕ)} (q₁ : AggQueryIn T c n₁ κ₁ l₁) (q₂ : AggQueryIn T c n₂ κ₂ l₂) :
        AggQueryIn T c (n₁ + n₂) (Fin.append κ₁ κ₂) (l₁ ++ l₂)

        The product written with an apply: q₁ ⊳ q₂ with q₂ read under the ambient context only. When the hole of a recursive term is in q₂, which an apply's right side cannot hold, the factors are swapped and the columns put back by a projection; a product with a hole on each side, which no recursive term has, is left alone.

        Equations
        • One or more equations did not get rendered due to their size.
        Instances For
          Dependency graph
          theorem evaluate_prodApply {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {c n₁ n₂ : ℕ} {κ₁ : Fin n₁ → ColKind} {κ₂ : Fin n₂ → ColKind} {l₁ : List (String × ℕ)} (q₁ : AggQueryIn T c n₁ κ₁ l₁) (q₂ : AggQueryIn T c n₂ κ₂) (dB : AnnotatedDatabase T K) (γ : Fin c → T) (E : EvalEnv T K) :
          (q₁.Apply (AggQueryIn.substMap (applyOuter T c n₁) q₂)).evaluate dB γ E = (q₁.Prod q₂).evaluate dB γ E

          The product is the apply of its left factor with its right factor read under the ambient context, exactly.

          Dependency graph
          theorem finEq_prodSwap {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {c n₁ n₂ : ℕ} {κ₁ : Fin n₁ → ColKind} {κ₂ : Fin n₂ → ColKind} {l₂ : List (String × ℕ)} (q₁ : AggQueryIn T c n₁ κ₁) (q₂ : AggQueryIn T c n₂ κ₂ l₂) :
          (AggQueryIn.castKind ⋯ (AggQueryIn.Proj (fun (j : Fin (n₁ + n₂)) => carryColIn (Fin.append κ₂ κ₁) (swapIdx n₁ n₂ j)) (q₂.Apply (AggQueryIn.substMap (applyOuter T c n₂) q₁)))).FinEq (q₁.Prod q₂)

          The product the other way round, its columns put back: the same rows with the same finalized annotations.

          Dependency graph

          The pass #

          def prodFree {T : Type} {c n : ℕ} {κ : Fin n → ColKind} {l : List (String × ℕ)} :
          AggQueryIn T c n κ l → AggQueryIn T c n κ l

          Every product replaced by its apply form.

          Equations
          Instances For
            Dependency graph

            What the pass keeps #

            The sufficient half: ε and × are dispensable #

            The classes other than ε and × generate the annotated algebra, over every schema and every commutative m-semiring: each ε is a set recursion (dedupFree), then each product the apply of its left factor with its right factor read under the ambient context, swapped when the right factor holds a recursive term's hole (prodFree). The second pass keeps every row, its columns and its finalized annotation, which is all the annotated evaluation reads.

            Dependency graph