Documentation

Provenance.AnnotatedDedup

Duplicate elimination from the set recursion, annotated #

ε(q) = μ^∪R.(q, σ_false(R)) in every semiring, exactly: the first round of the set recursion is the deduplication of q, the recursive term reads the round and keeps nothing of it, so the second round is the first and the iteration settles there, with the rows of ε(q) and their annotations (evaluate_dedupMu). The recursion always settles (annSettlesAt_dedupMu).

So ε is dispensable in the annotated algebra over every commutative m-semiring: dedupFree replaces each ε by that recursion under a fresh name, and generatesAnn_dedupFree says the classes other than ε generate the annotated algebra (GeneratesAnn). The products go next (Provenance.AnnotatedProd); the unions stay, the recursions' operands being all-regular by typing and nothing re-typing an aggregate column without exploding it.

One duplicate elimination as a set recursion #

def dedupMu {T : Type} [ValueType T] {c n : ℕ} (s : String) (q : AggQueryIn T c n (ColKind.allReg n)) :

μ^∪s.(q, σ_false(s)): the set recursion whose first round is ε(q) and whose term adds nothing.

Equations
Instances For
    Dependency graph
    theorem evaluate_dedupMu {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {c n : ℕ} (s : String) (q : AggQueryIn T c n (ColKind.allReg n)) (d : AnnotatedDatabase T K) (γ : Fin c → T) (E : EvalEnv T K) :
    (dedupMu s q).evaluate d γ E = q.Dedup.evaluate d γ E

    ε(q) = μ^∪s.(q, σ_false(s)), exactly.

    Dependency graph
    theorem annSettlesAt_dedupMu {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {c n : ℕ} (s : String) (q : AggQueryIn T c n (ColKind.allReg n)) (d : AnnotatedDatabase T K) (γ : Fin c → T) (E : EvalEnv T K) (h : q.AnnSettlesAt d γ E) :
    (dedupMu s q).AnnSettlesAt d γ E

    And it settles, at its second round.

    Dependency graph

    The pass #

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

    Every ε replaced by the set recursion under a fresh name, the supply split in three at each node.

    Equations
    Instances For
      Dependency graph
      theorem evaluate_dedupFree {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) (f : ℕ → String) (d : AnnotatedDatabase T K) (γ : Fin c → T) (E : EvalEnv T K) :
      (dedupFree f q).evaluate d γ E = q.evaluate d γ E

      The pass changes no annotated evaluation.

      Dependency graph

      Its plain readings #

      theorem annSettlesAt_dedupFree {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) (f : ℕ → String) (d : AnnotatedDatabase T K) (γ : Fin c → T) (E : EvalEnv T K) :
      q.AnnSettlesAt d γ E → (dedupFree f q).AnnSettlesAt d γ E

      The pass settles wherever the query does.

      Dependency graph

      What the pass keeps #

      The sufficient half: ε is dispensable #

      The classes other than ε generate the annotated algebra, over every schema and every commutative m-semiring: each ε is the set recursion μ^∪s.(q, σ_false(s)) under a fresh name, which reads exactly as ε(q) does and always settles.

      Dependency graph