Documentation

Provenance.Extensionality

Graded extensionality #

In which m-semirings does the annotation of a tuple depend on the query alone and not on its spelling? Call K extensional for a class of queries when any two queries of the class with regular output columns and the same plain semantics on every instance give, on every K-instance, the same K-relation after collapsing the copies of each tuple by ⊕ – the K-relation of Green, Karvounarakis and Tannen (AnnotatedRelation.annSum). The answer is graded along the first levels of the chain of fragments of the sql-semantics paper, and the grading says which construct asks for which axiom:

Each axiom is forced by one pair of equivalent queries over a one-tuple instance, written with the constructs of the level that forces it: the two sides annotate the one output tuple by a and a ⊕ a, a and a ⊗ a, a and a ⊕ a ⊗ b, 𝟘 and a ⊗ (𝟙 ⊖ a), a and δ(a). Conversely, on F₀ a copy of an output tuple is annotated by a product of the annotations it is derived from; over ℕ[K], the universal commutative semiring, two queries with the same multiplicities on every instance give each tuple the same polynomial, by a polynomial identity over ℕ (FragQueryIn.semPlain_unfold, MvPolynomial.funext_set), and the universal homomorphism carries that to K. Above F₀, a lattice m-semiring has enough homomorphisms onto 𝔹 to separate its elements (IsLatticeSemiring.eq_of_forall_point); those of a Boolean m-semiring preserve the monus and, when δ is the identity, δ; and at each such point the annotated semantics is the plain semantics of the support (FragQueryIn.mem_support_sem, AggQueryIn.genRandomWorld_evaluate).

The levels F₀, F₁ and F₂ are the syntax FragQueryIn of Provenance.FragQuery, read in the general syntax through FragQueryIn.toAgg; the whole algebra is the general syntax under the hygiene the metatheory asks of a query (AggQueryIn.Tame), without recursion, so that nothing has to settle.

Extensionality #

K is extensional for the queries satisfying F: two such queries with the same plain semantics on every instance collapse, 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
    def AggQueryIn.InLevel0 {T : Type} [ValueType T] {n : ℕ} (q : AggQuery T n (ColKind.allReg n)) :

    The queries of F₀, in the general syntax: the translations of the level-0 queries of the fragment syntax.

    Equations
    Instances For
      Dependency graph
      def AggQueryIn.InLevel1 {T : Type} [ValueType T] {n : ℕ} (q : AggQuery T n (ColKind.allReg n)) :

      The queries of F₁.

      Equations
      Instances For
        Dependency graph
        def AggQueryIn.InLevel2 {T : Type} [ValueType T] {n : ℕ} (q : AggQuery T n (ColKind.allReg n)) :

        The queries of F₂: every translation of the fragment syntax.

        Equations
        Instances For
          Dependency graph
          def AggQueryIn.Tame {T : Type} [ValueType T] {n : ℕ} (q : AggQuery T n (ColKind.allReg n)) :

          A tame query of the whole algebra: recursion-free, and with the hygiene the metatheory asks – no provenance sum, hygienic, well-kinded, with distinct labels, recorded reads, source columns and frames containing their row. These are the hypotheses of the homomorphism commutation (AggQueryIn.evaluateAnnotated_hom) and of the random-world commutation (AggQueryIn.genRandomWorld_evaluate) of the general evaluator.

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

            The levels are nested.

            Dependency graph
            Dependency graph
            theorem Extensional.mono {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {F G : {n : ℕ} → AggQuery T n (ColKind.allReg n) → Prop} (hFG : ∀ {n : ℕ} (q : AggQuery T n (ColKind.allReg n)), F q → G q) (hG : Extensional T K fun {n : ℕ} => G) :
            Extensional T K fun {n : ℕ} => F

            Extensionality is antitone in the class of queries.

            Dependency graph

            The plain equivalence of translated queries #

            theorem FragQueryIn.toAgg_plainEquiv_iff {T : Type} [ValueType T] {n : ℕ} (e₁ e₂ : FragQuery T n) :
            (toAgg e₁).PlainEquiv (toAgg e₂) ↔ ∀ (D : Database T) (γ : Fin 0 → T), semPlain e₁ D γ = semPlain e₂ D γ

            Two translated queries are plainly equivalent exactly when their closed-form plain semantics agree on every instance.

            Dependency graph
            theorem FragQueryIn.annSum_toAgg_evaluateAnnotated {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {n : ℕ} (e : FragQuery T n) (habs : hasSemijoin e → absorptive K) (d : AnnotatedDatabase T K) (u : Tuple T n) :
            ((toAgg e).evaluateAnnotated d).annSum u = (sem e d fun (x : Fin 0) => 0).annSum u

            The collapsed annotations of a translated query, in closed form.

            Dependency graph

            (a) Every commutative m-semiring is extensional for F₀ #

            The argument is in ℕ[K], the polynomial semiring over the annotations themselves, read as indeterminates: the instance d is the image of the instance d₀ carrying X a where d carries a, under the universal homomorphism sending X a to a. Over d₀ the collapsed annotation of a tuple is a polynomial, and evaluating it at a valuation n : K → ℕ is the multiplicity of the tuple on the plain instance in which each copy carrying a is repeated n a times. Two queries with the same plain semantics everywhere have the same multiplicities, so the two polynomials agree on all of ℕ^K, and a polynomial identity settles it.

            Every commutative m-semiring is extensional for F₀.

            Dependency graph

            The forcing pairs #

            Each axiom is forced by one pair of queries with the same plain semantics on every instance, read on a one-tuple instance: R holding ![x] annotated a.

            def oneTupleDb {T K : Type} (x : T) (a : K) :

            The instance with one relation R holding one tuple, annotated a.

            Equations
            Instances For
              Dependency graph
              def twoRelDb {T K : Type} (x : T) (a b : K) :

              The instance with two relations R and S, each holding the one tuple ![x], annotated a and b.

              Equations
              Instances For
                Dependency graph

                (a) on the classical layer: the commutativity of ⊗ #

                The general evaluator is defined over commutative m-semirings, so the commutativity of ⊗ is not an axiom it can force. The classical evaluator Query.evaluateAnnotated is defined over every m-semiring, and there the swapped product does force it: Π₂,₁(R × S) and S × R have the same plain semantics on every instance, and annotate the one tuple of a two-relation instance by a ⊗ b and b ⊗ a.

                def swapProd₁ {T : Type} :
                Query T 2

                Π₂,₁(R × S), in the classical syntax.

                Equations
                Instances For
                  Dependency graph
                  def swapProd₂ {T : Type} :
                  Query T 2

                  S × R.

                  Equations
                  Instances For
                    Dependency graph
                    Dependency graph
                    Dependency graph
                    def AnnotatedRelation.collapse {T : Type} [ValueType T] {K₀ : Type} [SemiringWithMonus K₀] {n : ℕ} (r : AnnotatedRelation T K₀ n) (u : Tuple T n) :
                    K₀

                    The K-relation an annotated relation collapses to, over any m-semiring: the ⊕-sum of the annotations of the copies of a tuple. On a commutative m-semiring it is AnnotatedRelation.annSum.

                    Equations
                    Instances For
                      Dependency graph

                      On a commutative m-semiring the collapse is annSum.

                      Dependency graph

                      The two sides of the pair have the same plain semantics on every instance.

                      Dependency graph
                      theorem mul_comm_of_extensional_swap {T : Type} [ValueType T] {K₀ : Type} [SemiringWithMonus K₀] [DecidableEq K₀] (hext : ∀ (d : AnnotatedDatabase T K₀) (u : Tuple T 2), (swapProd₁.evaluateAnnotated ⋯ d).collapse u = (swapProd₂.evaluateAnnotated ⋯ d).collapse u) (a b : K₀) :
                      a * b = b * a

                      ⊗ is commutative where the swapped product is extensional: an m-semiring over which Π₂,₁(R × S) and S × R collapse to the same annotations on every instance has a commutative multiplication.

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

                      The base relation R of arity 1, in any context.

                      Equations
                      Instances For
                        Dependency graph
                        @[reducible, inline]

                        The base relation R of arity 1.

                        Equations
                        Instances For
                          Dependency graph
                          @[reducible, inline]

                          The base relation S of arity 1.

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

                            The projection onto the first column of a relation of arity 2.

                            Equations
                            Instances For
                              Dependency graph
                              @[reducible, inline]

                              The pair forcing a ⊕ a = a: ε(R) against ε(R ⊎ R).

                              Equations
                              Instances For
                                Dependency graph
                                Dependency graph
                                @[reducible, inline]

                                The pair forcing a ⊗ a = a: ε(R) against ε(Π₁(R × R)).

                                Equations
                                Instances For
                                  Dependency graph
                                  Dependency graph
                                  @[reducible, inline]

                                  The pair forcing a ⊕ a ⊗ b = a, and with it 𝟙 ⊕ b = 𝟙: ε(R) against ε(R ⊎ Π₁(R × S)).

                                  Equations
                                  Instances For
                                    Dependency graph
                                    Dependency graph
                                    @[reducible, inline]

                                    The predicate matching the current row with a row of the subquery on their one column: R.x IS NOT DISTINCT FROM S.x.

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

                                      The pair forcing a ⊗ (𝟙 ⊖ a) = 𝟘: the antijoin of R with itself on its column, WHERE NOT EXISTS, against the empty query.

                                      Equations
                                      Instances For
                                        Dependency graph
                                        @[reducible, inline]
                                        abbrev FragQueryIn.pairExcl₂ {T : Type} [ValueType T] (x : T) :
                                        Equations
                                        Instances For
                                          Dependency graph

                                          What the pairs annotate on the one-tuple instance #

                                          The pairs are plainly equivalent #

                                          What extensionality forces #

                                          ⊕ is idempotent where K is extensional for a class holding ε(R) and ε(R ⊎ R).

                                          Dependency graph

                                          ⊗ is idempotent where K is extensional for a class holding ε(R) and ε(Π₁(R × R)).

                                          Dependency graph

                                          K is absorptive where it is extensional for a class holding ε(R) and ε(R ⊎ Π₁(R × S)): the pair gives a ⊕ a ⊗ b = a, and 𝟙 ⊕ b = 𝟙 is its instance at a = 𝟙.

                                          Dependency graph
                                          theorem exclusive_of_extensional {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {F : {n : ℕ} → AggQuery T n (ColKind.allReg n) → Prop} (cnt : SeqAggFunc T) (hc : cnt.Counts) (h₁ : F (FragQueryIn.toAgg (FragQueryIn.pairExcl₁ cnt hc))) (h₂ : F (FragQueryIn.toAgg (FragQueryIn.pairExcl₂ 0))) (hext : Extensional T K fun {n : ℕ} => F) :

                                          K is exclusive where it is extensional for a class holding the antijoin of R with itself and the empty query.

                                          Dependency graph

                                          A counting aggregate, for the antijoin pair: nonzero where the sequence holds a non-null value, 𝟘 otherwise.

                                          Equations
                                          Instances For
                                            Dependency graph
                                            Dependency graph

                                            (b) and (c): the converses, through the points #

                                            theorem annSum_eq_of_points {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] (hL : IsLatticeSemiring K) {n : ℕ} (e₁ e₂ : FragQuery T n) (hpe : (FragQueryIn.toAgg e₁).PlainEquiv (FragQueryIn.toAgg e₂)) (hs₁ : ∀ (f : K →+* Bool), FragQueryIn.hasMonus e₁ → ∀ (x y : K), f (x - y) = f x - f y) (hs₂ : ∀ (f : K →+* Bool), FragQueryIn.hasMonus e₂ → ∀ (x y : K), f (x - y) = f x - f y) (d : AnnotatedDatabase T K) (u : Tuple T n) :

                                            Over a lattice m-semiring, two translated queries with the same plain semantics collapse to the same annotations, provided the translation reaches their semantics and the points pass through them. The annotation of a tuple is determined by its images at the points of K, and each image is a plain evaluation of the support.

                                            Dependency graph

                                            (b) K is extensional for F₁ iff it is a lattice m-semiring.

                                            Dependency graph

                                            (c) K is extensional for F₂ iff it is a Boolean m-semiring, whatever its δ.

                                            Dependency graph

                                            (d) The whole recursion-free algebra #

                                            The pair forcing δ(a) = a is ε(R) against Π₁(γ₁[count](R)), a grouping that aggregates with its aggregate column projected away: the first annotates the one tuple by a, the second by the group's existence factor δ(a). Conversely, when K is Boolean with δ the identity, every point of K is an m-semiring homomorphism onto 𝔹, the general evaluator commutes with it, and over 𝔹 the annotated evaluation is the plain evaluation of the support (AggQueryIn.genRandomWorld_evaluate, read through the constant embedding of 𝔹 into 𝔹[∅]).

                                            @[reducible, inline]
                                            abbrev gammaKinds :
                                            Fin (1 + 1) → ColKind

                                            The kinds of a grouping of arity-one key with one aggregate.

                                            Equations
                                            Instances For
                                              Dependency graph
                                              @[reducible, inline]
                                              abbrev projKey {T : Type} :

                                              The projection reading the key column of such a grouping.

                                              Equations
                                              Instances For
                                                Dependency graph
                                                def pairDelta₂Raw {T : Type} [ValueType T] (cnt : SeqAggFunc T) :
                                                AggQuery T 1 fun (j : Fin 1) => ProjColIn.kind (projKey j)

                                                The grouping of the forcing pair: γ₁[count](R), with any sequence aggregate for the count, its aggregate column projected away.

                                                Equations
                                                Instances For
                                                  Dependency graph
                                                  def pairDelta₂ {T : Type} [ValueType T] (cnt : SeqAggFunc T) :

                                                  The same, with its kinds read as all regular.

                                                  Equations
                                                  Instances For
                                                    Dependency graph

                                                    Duplicate elimination of R, the other side of the pair.

                                                    Equations
                                                    Instances For
                                                      Dependency graph
                                                      theorem delta_id_of_extensional {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {F : {n : ℕ} → AggQuery T n (ColKind.allReg n) → Prop} (cnt : SeqAggFunc T) (h₁ : F pairDelta₁) (h₂ : F (pairDelta₂ cnt)) (hext : Extensional T K fun {n : ℕ} => F) (a : K) :

                                                      δ is the identity where K is extensional for a class holding ε(R) and Π₁(γ₁[count](R)).

                                                      Dependency graph

                                                      Tameness of the forcing pairs #

                                                      The converse: points are m-semiring homomorphisms #

                                                      @[reducible]

                                                      A point of a Boolean m-semiring with δ the identity, into 𝔹[X]: the point followed by the constant embedding.

                                                      Equations
                                                      Instances For
                                                        Dependency graph

                                                        (d) K is extensional for the whole recursion-free algebra iff it is a Boolean m-semiring whose δ is the identity.

                                                        Dependency graph