Documentation

Provenance.FragQuery

The first levels of the chain of fragments, as a syntax of their own #

The extensionality theorem of Provenance.Extensionality grades the m-semirings along the first levels of the chain of SQL fragments of the sql-semantics paper: F₀ (projection, selection, product, apply, union, the constant relations), F₁ (F₀ with duplicate elimination, EXISTS and IN) and F₂ (F₁ with EXCEPT, NOT EXISTS and NOT IN); the projections and selections carry the library's terms, so the level F₃ of the paper, which adds expressions, is F₂ here as well. Each construct of these levels is an operator of the kind-indexed syntax, or a query it abbreviates (Provenance.Derived); but the levels are not sets of operator classes – EXISTS is an apply, a scalar count and a selection on an aggregate atom, which AggQueryIn.usesOnly charges to three classes – so they are given here as a syntax of their own, FragQueryIn T c n, with a translation FragQueryIn.toAgg into the general syntax and the levels as predicates on it (FragQueryIn.level0, FragQueryIn.level1; F₂ is the whole syntax).

Every output column is regular, so the translation's annotated evaluation produces plain annotated tuples, and the file gives it in closed form: FragQueryIn.sem is the annotated semantics operator by operator – multiset operations and the m-semiring's ⊕, ⊗ and ⊖ – and FragQueryIn.toAgg_evaluateAnnotated says the general evaluator computes it. The same for the plain semantics, FragQueryIn.semPlain and FragQueryIn.toAgg_evaluatePlain. The one closed form that costs a hypothesis is the semijoin's, α ⊗ ⊕β in an absorptive m-semiring (AggValue.predProvScalar_count_ne_zero), which is why the bridge asks absorptivity of a query with a semijoin and nothing of the others.

An EXISTS or IN counts, in SQL's scalar convention, the rows of its subquery that match the current row; the count is over a constant that is not null (ValueType.nonzero), so that it is 𝟘 exactly where nothing matches, and any aggregate that counts (SeqAggFunc.Counts) may do the counting.

inductive FragQueryIn (T : Type) [ValueType T] :
ℕ → ℕ → Type

The syntax of the first levels of the chain. The context c is the arity of the row an apply's right side reads, as in AggQueryIn; every output column is regular.

Instances For
    Dependency graph
    @[reducible, inline]
    abbrev FragQuery (T : Type) [ValueType T] (n : ℕ) :

    A closed query of the fragment syntax.

    Equations
    Instances For
      Dependency graph

      A predicate over regular columns has no aggregate atom: an aggregate atom names a column of aggregate kind, and there is none.

      Dependency graph

      The levels #

      def FragQueryIn.level0 {T : Type} [ValueType T] {c n : ℕ} :
      FragQueryIn T c n → Prop

      Level F₀: no duplicate elimination, no difference, no semijoin and no antijoin.

      Equations
      Instances For
        Dependency graph
        def FragQueryIn.level1 {T : Type} [ValueType T] {c n : ℕ} :
        FragQueryIn T c n → Prop

        Level F₁: F₀ with duplicate elimination and the semijoin, and without the negated forms.

        Equations
        Instances For
          Dependency graph
          def FragQueryIn.hasSemijoin {T : Type} [ValueType T] {c n : ℕ} :
          FragQueryIn T c n → Prop

          Whether a query has a semijoin somewhere: the one construct whose closed form asks absorptivity of the m-semiring.

          Equations
          Instances For
            Dependency graph

            A query of F₀ has no semijoin.

            Dependency graph
            theorem FragQueryIn.level1_of_level0 {T : Type} [ValueType T] {c n : ℕ} (q : FragQueryIn T c n) :
            q.level0 → q.level1

            F₀ ⊆ F₁.

            Dependency graph

            The two semantics, in closed form #

            noncomputable def FragQueryIn.matchesAnn {T : Type} [ValueType T] {K : Type} {c k l : ℕ} (φ : GenPredIn T (k + c) (ColKind.allReg l)) (S : AnnotatedDatabase T K → (Fin (k + c) → T) → AnnotatedRelation T K l) (d : AnnotatedDatabase T K) (γ : Fin c → T) (u : Tuple T k) :

            The rows of the right side of a semijoin that match a left row u: the right side read in the context u extended by the outer one, cut by the predicate.

            Equations
            Instances For
              Dependency graph
              noncomputable def FragQueryIn.sem {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] {c n : ℕ} :
              FragQueryIn T c n → AnnotatedDatabase T K → (Fin c → T) → AnnotatedRelation T K n

              The annotated semantics, operator by operator. A duplicate elimination sums the annotations of the copies of a tuple, a difference subtracts from each copy on the left the sum of the copies on the right, a semijoin multiplies each left row by the sum of the annotations of its matches and an antijoin by 𝟙 ⊖ that sum.

              Equations
              Instances For
                Dependency graph
                noncomputable def FragQueryIn.matchesPlain {T : Type} [ValueType T] {c k l : ℕ} (φ : GenPredIn T (k + c) (ColKind.allReg l)) (S : Database T → (Fin (k + c) → T) → Relation T l) (D : Database T) (γ : Fin c → T) (u : Tuple T k) :

                The rows of the right side of a semijoin that match a left row, in the plain semantics.

                Equations
                Instances For
                  Dependency graph
                  noncomputable def FragQueryIn.semPlain {T : Type} [ValueType T] {c n : ℕ} :
                  FragQueryIn T c n → Database T → (Fin c → T) → Relation T n

                  The plain semantics, operator by operator.

                  Equations
                  Instances For
                    Dependency graph

                    The translation into the general syntax #

                    The projection that keeps the left arm's columns of a match-count row and drops the count, in a context.

                    Equations
                    Instances For
                      Dependency graph
                      def FragQueryIn.matchCountIn {T : Type} [ValueType T] {c k l : ℕ} (cnt : SeqAggFunc T) (φ : GenPredIn T (k + c) (ColKind.allReg l)) (R : AggQueryIn T c k (ColKind.allReg k)) (Q : AggQueryIn T (k + c) l (ColKind.allReg l)) :

                      The match count of a semijoin in a context: the left side, each row extended by the token counting, over a non-null constant, the rows of the right side the predicate matches it with.

                      Equations
                      Instances For
                        Dependency graph
                        def FragQueryIn.countSiteIn {T : Type} [ValueType T] {c k l : ℕ} (op : CompOp) (cnt : SeqAggFunc T) (φ : GenPredIn T (k + c) (ColKind.allReg l)) (R : AggQueryIn T c k (ColKind.allReg k)) (Q : AggQueryIn T (k + c) l (ColKind.allReg l)) :

                        The count site of a semijoin or an antijoin in a context: the match count compared against 𝟘, projected back onto the left side.

                        Equations
                        • One or more equations did not get rendered due to their size.
                        Instances For
                          Dependency graph
                          def FragQueryIn.toAgg {T : Type} [ValueType T] {c n : ℕ} :

                          The translation into the general syntax. Each construct is the operator of the same name, a semijoin or an antijoin the count site that Provenance.Derived gives it, and the unit a scalar aggregation of nothing over the empty relation.

                          Equations
                          Instances For
                            Dependency graph

                            The plain semantics of the translation #

                            theorem FragQueryIn.toAgg_evaluatePlain {T : Type} [ValueType T] {c n : ℕ} (q : FragQueryIn T c n) (D : Database T) (γ : Fin c → T) :

                            The general evaluator computes the plain semantics of the fragment.

                            Dependency graph

                            The annotated semantics of the translation #

                            The rows the general evaluator produces on a translated query are embedded annotated tuples: regular values, and nothing pending. The lemmas below read each operator on such rows.

                            noncomputable def FragQueryIn.countToken {T : Type} [ValueType T] {K : Type} [HasAltLinearOrder K] {c k l : ℕ} (cnt : SeqAggFunc T) (M : AnnotatedRelation T K l) (u : Tuple T k) (γ : Fin c → T) :

                            The token a count site builds on a left row u: the scalar count, over the non-null constant, of the rows of the right side that match u.

                            Equations
                            Instances For
                              Dependency graph
                              theorem FragQueryIn.toAgg_evaluate {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {c n : ℕ} (q : FragQueryIn T c n) :
                              (q.hasSemijoin → absorptive K) → ∀ (d : AnnotatedDatabase T K) (γ : Fin c → T) (E : EvalEnv T K), q.toAgg.evaluate d γ E = Multiset.map GenRow.ofAnnotated (q.sem d γ)

                              The general evaluator computes the annotated semantics of the fragment, row for row: on a translated query it produces the embedded rows of FragQueryIn.sem, in every context and every environment. Absorptivity is asked only of a query with a semijoin, whose closed form needs it.

                              Dependency graph
                              theorem FragQueryIn.toAgg_evaluateAnnotated {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {c n : ℕ} (q : FragQueryIn T c n) (habs : q.hasSemijoin → absorptive K) (d : AnnotatedDatabase T K) (γ : Fin c → T) (E : EvalEnv T K) :
                              q.toAgg.evaluateAnnotated d γ E = q.sem d γ

                              The general evaluator computes the annotated semantics of the fragment.

                              Dependency graph