Documentation

Provenance.SemanticExtensionality

Extensionality for every semantics that extends semiring provenance #

Provenance.Extensionality grades the m-semirings for one semantics, the evaluator of the library. This module removes that dependence. A semantics here is any function S from the closed queries of the fragment syntax and the instances annotated in a semiring K to annotated relations. It extends semiring provenance (ExtendsSemiringProvenance) when base relations keep their annotations, the unit is annotated 𝟙, a projection keeps annotations, a union is the multiset sum, a product multiplies, and duplicate elimination sums each class, on all arguments, negative ones included. Nothing is asked of the difference, the semijoin, or the antijoin, nor of homomorphisms, nor of any agreement with SQL, and K is not assumed to have a monus.

For such an S:

The complement comes from two pairs around a query E of arity 0 that holds exactly when R is empty, its own annotation c being anything: R × E against the empty query forces b ⊗ c = 𝟘, and E ⊎ ε(Π∅ R) against the unit forces c ⊕ b = 𝟙. Neither compares values, so NULL plays no part.

Over a commutative m-semiring the converse holds at F₂: exists_semantics_extensional_iff says that a semantics extending semiring provenance and extensional for F₂ exists iff K is a Boolean m-semiring, whatever its δ.

def FragQueryIn.annCollapse {T : Type} [ValueType T] {K : Type} [AddCommMonoid K] {n : ℕ} (r : AnnotatedRelation T K n) (u : Tuple T n) :
K

The ⊕-sum of the annotations one tuple carries, over any semiring.

Equations
Instances For
    Dependency graph
    structure FragQueryIn.ExtendsSemiringProvenance {T : Type} [ValueType T] {K : Type} [Semiring K] (S : (n : ℕ) → FragQuery T n → AnnotatedDatabase T K → AnnotatedRelation T K n) :

    A semantics extends semiring provenance when it follows the clauses of semiring provenance on the positive operators, for all arguments. The negative operators are left free.

    Instances For
      Dependency graph
      def FragQueryIn.ExtensionalUnder {T : Type} [ValueType T] {K : Type} [Semiring K] (S : (n : ℕ) → FragQuery T n → AnnotatedDatabase T K → AnnotatedRelation T K n) (F : (n : ℕ) → FragQuery T n → Prop) :

      K is extensional under S for the queries satisfying F: two such queries with the same plain semantics on every instance collapse, under S and on every K-instance, to the same K-relation.

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

        The lattice laws of a semiring.

        Instances For
          Dependency graph

          A semiring that is a lattice in which every element has a complement.

          Instances For
            Dependency graph

            The queries #

            @[reducible, inline]
            abbrev FragQueryIn.swapCols {T : Type} :
            Tuple (TermGIn T 0 (ColKind.allReg (1 + 1))) (1 + 1)

            The swap of the two columns of a product of two relations of arity one.

            Equations
            Instances For
              Dependency graph
              @[reducible, inline]
              abbrev FragQueryIn.leftCol {T : Type} :
              Tuple (TermGIn T 0 (ColKind.allReg (1 + 0))) 1

              The left column of a product with a relation of arity 0.

              Equations
              Instances For
                Dependency graph
                @[reducible, inline]

                The projection of a relation of arity one on no column.

                Equations
                Instances For
                  Dependency graph
                  @[reducible, inline]

                  ε(Π∅ R): the one empty tuple, exactly when R is non-empty.

                  Equations
                  Instances For
                    Dependency graph
                    @[reducible, inline]

                    𝟏 − ε(Π∅ R): the one empty tuple, exactly when R is empty.

                    Equations
                    Instances For
                      Dependency graph

                      E tests that R is empty, on the plain semantics.

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

                        The difference tests emptiness.

                        Dependency graph
                        @[reducible, inline]

                        The always-true match of a subquery row: 0 IS NOT DISTINCT FROM 0.

                        Equations
                        Instances For
                          Dependency graph
                          @[reducible, inline]
                          abbrev FragQueryIn.notExistsR {T : Type} [ValueType T] (cnt : SeqAggFunc T) (hc : cnt.Counts) :

                          SELECT 1 WHERE NOT EXISTS (SELECT * FROM R), on the empty tuple.

                          Equations
                          Instances For
                            Dependency graph

                            NOT EXISTS tests emptiness.

                            Dependency graph

                            The computations under a semantics #

                            What extensionality forces #

                            theorem FragQueryIn.ExtendsSemiringProvenance.mul_comm_of_level0 {T : Type} [ValueType T] {K : Type} [Semiring K] {S : (n : ℕ) → FragQuery T n → AnnotatedDatabase T K → AnnotatedRelation T K n} (h : ExtendsSemiringProvenance S) (hext : ExtensionalUnder S fun (x : ℕ) (q : FragQuery T x) => level0 q) (a b : K) :
                            a * b = b * a

                            ⊗ is commutative where K is extensional for F₀ under S.

                            Dependency graph

                            (K, ⊕, ⊗) is a lattice where K is extensional for F₁ under S.

                            Dependency graph

                            The complement #

                            theorem FragQueryIn.ExtendsSemiringProvenance.compl_of_test {T : Type} [ValueType T] {K : Type} [Semiring K] {S : (n : ℕ) → FragQuery T n → AnnotatedDatabase T K → AnnotatedRelation T K n} (h : ExtendsSemiringProvenance S) (hext : ExtensionalUnder S fun (x : ℕ) (x_1 : FragQuery T x) => True) {E : FragQuery T 0} (hE : TestsEmptyR E) (b : K) (u₀ : Tuple T 0) :
                            b * annCollapse (S 0 E (oneTupleDb 0 b)) u₀ = 0 ∧ annCollapse (S 0 E (oneTupleDb 0 b)) u₀ + b = 1

                            Every element has a complement where K is extensional for F₂ under S: the annotation S gives a query that tests the emptiness of R, whatever it is, is the complement.

                            Dependency graph

                            Extensionality for F₂ under a semantics that extends semiring provenance makes K a Boolean algebra, whatever the semantics does on negation.

                            Dependency graph

                            Over a commutative m-semiring #

                            In a commutative m-semiring, a Boolean rig is a Boolean m-semiring: the monus against 𝟙 is below the complement, hence disjoint from the element.

                            Dependency graph

                            The semantics of the fragment extends semiring provenance.

                            Dependency graph

                            Over a commutative m-semiring, a semantics extending semiring provenance and extensional for F₂ exists iff K is a Boolean m-semiring, whatever its δ.

                            Dependency graph

                            The copies themselves need not agree #

                            Collapsing is necessary from F₂ on. Splitting R on whether S is non-empty returns R on every plain instance, without counting anything, and gives one tuple two copies where R gives it one.

                            @[reducible, inline]
                            abbrev FragQueryIn.relSIn {T : Type} [ValueType T] (c : ℕ) :

                            The base relation S of arity 1, in a context.

                            Equations
                            Instances For
                              Dependency graph
                              @[reducible, inline]

                              The always-true match of a row of R with a row of S.

                              Equations
                              Instances For
                                Dependency graph
                                @[reducible, inline]
                                abbrev FragQueryIn.splitR {T : Type} [ValueType T] (cnt : SeqAggFunc T) (hc : cnt.Counts) :

                                The split of R on whether S is non-empty: SELECT x FROM R WHERE EXISTS (SELECT * FROM S) UNION ALL SELECT x FROM R WHERE NOT EXISTS (SELECT * FROM S).

                                Equations
                                • One or more equations did not get rendered due to their size.
                                Instances For
                                  Dependency graph
                                  theorem FragQueryIn.splitR_semPlain {T : Type} [ValueType T] (cnt : SeqAggFunc T) (hc : cnt.Counts) (D : Database T) (γ : Fin 0 → T) :
                                  semPlain (splitR cnt hc) D γ = semPlain relR D γ

                                  The split of R is R on every plain instance.

                                  Dependency graph
                                  theorem FragQueryIn.splitR_sem {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] (cnt : SeqAggFunc T) (hc : cnt.Counts) (x : T) (a s : K) (γ : Fin 0 → T) :
                                  sem (splitR cnt hc) (twoRelDb x a s) γ = {(![x], a * s)} + {(![x], a * (1 - s))}

                                  The copies of the split: on R = {x : a} and S = {x : s}, the tuple has two copies, annotated a ⊗ s and a ⊗ (𝟙 ⊖ s), where R gives it one, annotated a.

                                  Dependency graph
                                  theorem FragQueryIn.splitR_copies_ne {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] (cnt : SeqAggFunc T) (hc : cnt.Counts) (x : T) (s : K) (γ : Fin 0 → T) (h₁ : s ≠ 1) (h₂ : 1 - s ≠ 1) :
                                  ((![x], 1) ∈ have this := sem relR (twoRelDb x 1 s) γ; this) ∧ (![x], 1) ∉ have this := sem (splitR cnt hc) (twoRelDb x 1 s) γ; this

                                  The copies differ, even with 𝟘 set aside: R holds a copy annotated 𝟙 that the split does not, as soon as neither s nor 𝟙 ⊖ s is 𝟙, in particular for a variable s of 𝔹[X].

                                  Dependency graph