Documentation

Provenance.RecFreeBasis

The bases of the recursion-free algebra in the minimal universe #

The recursion-free half of the classification, in the scope of the whole algebra's (Provenance.RecursionBases): queries of the algebra with no recursion, in the minimal universe 𝒜(∅, {count}), generated by classes with no recursion either. The rows are the whole algebra's at the same witnesses, all recursion-free, with ⊎ added: without a recursion it has nothing to be derived from.

def GeneratesOnRF (T : Type) [ValueType T] (sch : Schema) (cnt : SeqAggFunc T) (S : Set OpKind) :

Generation of the recursion-free algebra: every query with no recursion, over the schema and in the signature with cnt as its only aggregate, is matched by one over S, defined and equal wherever it is.

Equations
Instances For
    Dependency graph
    theorem union_mem_of_generatesOnRF {T : Type} [ValueType T] {cnt : SeqAggFunc T} {S : Set OpKind} (hmb : OpKind.muBag ∉ S) (hms : OpKind.muSet ∉ S) {sch : Schema} (hS : GeneratesOnRF T sch cnt S) :

    ⊎ is in every basis of the recursion-free algebra whose classes hold no recursion: without it every answer on the all-empty instance has at most one row, and the union of the unit with itself has two.

    Dependency graph

    The difference in place of the selection #

    def DiffBasis.pairU {T : Type} {C : ℕ} (a b : T ⊕ Fin C) :

    {a, b} by a union: {a} and what of {b} is not a.

    Equations
    Instances For
      Dependency graph

      The pair by a union.

      Equations
      Instances For
        Dependency graph

        A selection by its test, decorrelated #

        The classes a test uses, {a, b} built by a union.

        Equations
        Instances For
          Dependency graph
          theorem AggQueryIn.exists_selByTest {T : Type} [ValueType T] {S : Set OpKind} (he : OpKind.empty ∈ S) (hp : OpKind.proj ∈ S) (hd : OpKind.diff ∈ S) (hx : OpKind.prod ∈ S) (hu : OpKind.union ∈ S) (hg : OpKind.gamma ∈ S) (hw : OpKind.win ∈ S) (hmb : OpKind.muBag ∉ S) (hms : OpKind.muSet ∉ S) {Θ : Set (SeqAggFunc T)} {cnt : SeqAggFunc T} (hc : cnt ∈ Θ) (hcnt : cnt.IsCount) (sch : Schema) {n : ℕ} (φ : GenPredIn T 0 (ColKind.allReg n)) (hφ : φ.noFun = true) (q : AggQueryIn T 0 n (ColKind.allReg n)) (hqu : usesOnly S q) (hqi : inSig Θ q) (hqo : overSchema sch q) :
          ∃ (q' : AggQueryIn T 0 n (ColKind.allReg n)), usesOnly S q' ∧ inSig Θ q' ∧ overSchema sch q' ∧ ∀ (D : Database T) (Îł : Fin 0 → T), q.SettlesAt D Îł → q'.SettlesAt D Îł ∧ q'.evaluatePlain D Îł = Multiset.filter (fun (u : Tuple T n) => φ.holdsPlain u Îł) (q.evaluatePlain D Îł)

          A selection on a closed query without σ and without the apply: the test of the predicate, decorrelated over the distinct rows of the query, holds the rows the predicate keeps, and two differences keep the query's rows that are among them. The test uses no product and no apply, so its decorrelation needs neither σ nor Δ.

          Dependency graph

          The pass to ∅, Π, σ, ⊎, Îł, win and one of × and the apply #

          theorem AggQueryIn.exists_rfPass {T : Type} [ValueType T] {S U : Set OpKind} (he : OpKind.empty ∈ S) (hp : OpKind.proj ∈ S) (hs : OpKind.sel ∈ S √ OpKind.diff ∈ S ∧ OpKind.prod ∈ S) (hu : OpKind.union ∈ S) (hg : OpKind.gamma ∈ S) (hw : OpKind.win ∈ S) (hx : OpKind.prod ∈ S √ OpKind.apply ∈ S) (hmbS : OpKind.muBag ∉ S) (hmsS : OpKind.muSet ∉ S) (hU : U ⊆ plainOps) (hUa : OpKind.apply ∈ U → OpKind.apply ∈ S ∧ OpKind.sel ∈ S) {Θ : Set (SeqAggFunc T)} (cnt : SeqAggFunc T) (hcnt : cnt ∈ Θ) (hci : cnt.IsCount) (sch : Schema) {c n : ℕ} {Îș : Fin n → ColKind} {l : List (String × ℕ)} (q : AggQueryIn T c n Îș l) :
          l = [] → c = 0 ∹ OpKind.sel ∈ S → usesOnly U q → inSig Θ q → overSchema sch q → ∃ (q' : AggQueryIn T c n (ColKind.allReg n)), usesOnly S q' ∧ inSig Θ q' ∧ (OpKind.prod ∈ S → OpKind.sel ∈ S → q'.paramsReg) ∧ overSchema sch q' ∧ ∀ (D : Database T) (γ : Fin c → T), q.SettlesAt D γ → q'.SettlesAt D γ ∧ q.evaluatePlain D γ = q'.evaluatePlain D γ

          The recursion-free pass: a query with no recursion, over the classes U, in a signature holding a counting aggregate, over a schema, is matched by one with all-regular columns over S, in the signature, over the schema, defined and equal wherever the source is. S holds ∅, Π, ⊎, Îł, win, one of σ and − (both − and × where it has no σ), and one of × and the apply (the apply, and σ, where U has the apply).

          • a product stays one where S has ×, and becomes an apply otherwise;
          • a difference stays one where S has −, and becomes the NOT IN form otherwise;
          • a selection stays one where S has σ, and is otherwise kept by its test, decorrelated over the distinct rows of its input – which needs the query closed, hence no apply in U;
          • a duplicate elimination becomes a grouping, and a window stays a window. Where S has × and σ, every parameter leaf of the result is regular, which is what its decorrelation asks.
          Dependency graph

          The four candidate bases #

          Dependency graph
          Dependency graph
          Dependency graph
          Dependency graph
          theorem rfDiffApplyOps_generatesOnRF {T : Type} [ValueType T] (sch : Schema) (cnt : SeqAggFunc T) (hcnt : cnt.IsCount) :

          {∅, Π, −, apply, ⊎, Îł, win} generates the recursion-free algebra in the minimal universe: the match over {∅, Π, σ, apply, ⊎, Îł, win}, each selection then an apply of its test, {a, b} built by a union.

          Dependency graph

          The product in place of the apply #

          The classes the decorrelation lands in, windows and groupings kept.

          Equations
          Instances For
            Dependency graph

            The classification #

            Dependency graph
            theorem generatesOnRF_iff {S : Set OpKind} (hmb : OpKind.muBag ∉ S) (hms : OpKind.muSet ∉ S) :

            The generating sets of the recursion-free algebra in the minimal universe, among the classes with no recursion, over ℕ with the counting aggregate: exactly the supersets of one of the four bases – ∅, Π, ⊎, Îł, win, with σ or − and with × or the apply, every pairing. With recursion {−, ×} is not one (not_generatesOnRec_prodDiff): σ or the apply is what a recursive term needs to drop a row.

            Dependency graph