Documentation

Provenance.AnnotatedEpsRow

Duplicate elimination is necessary in the annotated algebra #

A set of classes that generates the annotated algebra over ℕ contains ε or μ^∪. The invariant is that, without them, every annotation a query builds is at most 𝟙 as soon as the instance's are. Products, δ (the support map), a difference and 𝟙 ⊖ s keep it; a sum does not, and the evaluator adds annotations in three places only:

ε of a relation holding one tuple twice, annotated 𝟙, gives 2 (dedup_or_muSet_mem_of_generatesAnn).

With the other rows this makes the basis {∅, Π, σ, apply, γ, win, μ^⊎, ε, −} minimal: no proper subset generates the annotated algebra over both ℕ and ℕ × ℕ (annEpsOps_minimal).

The weight of a world, over ℕ #

The worlds of a selection weigh at most 𝟙 together #

def worldWeight {T : Type} {n : ℕ} (w : ℕ × ℕ × (Fin n → Option T)) :

The weight of a world: its present product times 𝟙 ⊖ its absent sum.

Equations
Instances For
    Dependency graph
    def natDecW {X : Type} (D : Multiset (X × ℕ × Bool)) :

    What a decision over a bag of occurrences weighs over ℕ, occurrence by occurrence.

    Equations
    Instances For
      Dependency graph
      def natLeafW {T : Type} (e : LeafKey T ℕ × Finset ℕ) :

      What a decision about an expression family weighs over ℕ.

      Equations
      Instances For
        Dependency graph
        theorem GenPredIn.predsemJ_le_one {T : Type} [ValueType T] {c n : ℕ} {κ : Fin n → ColKind} (φ : GenPredIn T c κ) (neg : Bool) (u : Tuple (GenValue T ℕ) n) (γ : Fin c → T) (hu : ∀ (k : Fin n) (a : AggTok T ℕ), u k = Sum.inr a → AggTok.AnnsIn (fun (x : ℕ) => x ≤ 1) a) :
        φ.predsemJ neg u γ ≤ 1

        A selection's joint reading is at most 𝟙 over ℕ when every token of the row carries annotations at most 𝟙.

        Dependency graph

        Every annotation a query without ε and μ^∪ builds is at most 𝟙 #

        def GenRow.Le1 {T : Type} {n : ℕ} (r : GenRow T ℕ n) :

        A row's annotations are at most 𝟙: its concrete part and every annotation the tokens it holds carry. Its pending factors are read only through δ, which is at most 𝟙 whatever it reads.

        Equations
        Instances For
          Dependency graph
          theorem le1_evaluate {T : Type} [ValueType T] {d : AnnotatedDatabase T ℕ} {S : Set OpKind} (hS₁ : OpKind.dedup ∉ S) (hS₂ : OpKind.muSet ∉ S) {Θ : Set (SeqAggFunc T)} (hΘ : ∀ (f : SeqAggFunc T), f.distinct ∉ Θ) (hD : ∀ (k : ℕ) (t : String) (r : AnnotatedRelation T ℕ k), AnnotatedDatabase.find k t d = some r → ∀ a ∈ r, a.2 ≤ 1) {c n : ℕ} {κ : Fin n → ColKind} {l : List (String × ℕ)} (q : AggQueryIn T c n κ l) :
          AggQueryIn.usesOnly S q → AggQueryIn.inSig Θ q → q.noExplode → ∀ (γ : Fin c → T) (E : EvalEnv T ℕ), (∀ (k : Fin c) (a : AggTok T ℕ), E.ctxAt c γ k = Sum.inr a → AggTok.AnnsIn (fun (x : ℕ) => x ≤ 1) a) → (∀ p ∈ l, ∀ r ∈ E.holes p.1 p.2, r.Le1) → ∀ r ∈ q.evaluate d γ E, r.Le1

          Without ε, μ^∪ and DISTINCT aggregates, every annotation a query builds is at most 𝟙 over ℕ, as soon as the instance's, the context's tokens' and the rounds the holes are bound to are.

          Dependency graph

          The witness #

          count is not its own distinct version: on [0, 0] the one reads 2, the other 1. So a DISTINCT window is out of the minimal signature.

          Dependency graph

          ε(R).

          Equations
          Instances For
            Dependency graph

            The instance it tells apart from every query without ε and μ^∪: R holds 0 twice, annotated 𝟙.

            Equations
            Instances For
              Dependency graph

              ε or μ^∪ is in every set generating the annotated algebra over ℕ: without them every annotation a query of the minimal signature builds is at most 𝟙 when the instance's are (le1_evaluate), and ε(R) gives 2 on dEps.

              Dependency graph

              The basis with ε is minimal #

              theorem annEpsOps_minimal {S : Set OpKind} (hS : S ⊆ annEpsOps) (hN : ∀ (sch : Schema), GeneratesAnn ℕ ℕ sch SeqAggFunc.count S) (hP : ∀ (sch : Schema), GeneratesAnn ℕ NatPair sch SeqAggFunc.count S) :

              No proper subset of {∅, Π, σ, apply, γ, win, μ^⊎, ε, −} generates the annotated algebra over both ℕ and ℕ × ℕ, with the counting aggregate: ∅, Π, γ, μ^⊎, win and σ are inherited from the plain rows, the apply because × is not in the set, − by the zero-pattern invariant over ℕ × ℕ, and ε because μ^∪ is not in the set.

              Dependency graph