Documentation

Provenance.Query

Relational algebra #

This file defines the abstract syntax and semantics of relational algebra queries over plain (unannotated) databases. The language is the extended relational algebra described in Section III of Sen, Maniu & Senellart, ProvSQL: A General System for Keeping Track of the Provenance and Probability of Data, with multiset semantics, explicit duplicate elimination, multiset difference, and aggregation.

Main definitions #

References #

inductive TermIn (T : Sort u_1) (c n : ℕ) :
Sort (max 1 u_1)
  • const {T : Sort u_1} {c n : ℕ} : T → TermIn T c n
  • outer {T : Sort u_1} {c n : ℕ} : Fin c → TermIn T c n

    An outer column: a column of the query this one is applied to. There are none in a closed query, c being 0 there.

  • index {T : Sort u_1} {c n : ℕ} : Fin n → TermIn T c n
  • add {T : Sort u_1} {c n : ℕ} : TermIn T c n → TermIn T c n → TermIn T c n
  • sub {T : Sort u_1} {c n : ℕ} : TermIn T c n → TermIn T c n → TermIn T c n
  • mul {T : Sort u_1} {c n : ℕ} : TermIn T c n → TermIn T c n → TermIn T c n
  • caseWhen {T : Sort u_1} {c n : ℕ} : CompOp → TermIn T c n → TermIn T c n → TermIn T c n → TermIn T c n → TermIn T c n

    SQL's searched CASE: the third term where the comparison of the first two holds, the fourth – the ELSE – where it does not. A guard that is unknown takes the ELSE, as SQL has it. The ELSE is a term and not the null, so the constructor asks nothing of the value domain; CASE WHEN φ THEN t END is the case where it is the constant null.

    A guard that is a Boolean combination of comparisons needs no more than this: a conjunction is a nested CASE, a disjunction is coalesce of the two cases, and a negation is CompOp.negate.

  • coalesce {T : Sort u_1} {c n : ℕ} : TermIn T c n → TermIn T c n → TermIn T c n

    SQL's COALESCE of two terms: the first where it is not null, the second where it is. It is not null-strict, which is why it is a constructor and not an arithmetic term.

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

    A term of a closed query: no outer column to read.

    Equations
    Instances For
      Dependency graph
      def TermIn.repr {T : Type} {n : ℕ} [Repr T] :
      Term T n → ℕ → Std.Format
      Equations
      Instances For
        Dependency graph
        @[instance_reducible]
        instance instReprTerm {α : Type} {n : ℕ} [Repr α] :
        Repr (Term α n)
        Equations
        Dependency graph
        Dependency graph
        def TermIn.eval {T : Type} [ValueType T] {n c : ℕ} (term : TermIn T c n) (tuple : Tuple T n) (γ : Fin c → T := fun (x : Fin c) => 0) :
        T

        Value of a term on a row. An open term also reads an outer valuation γ, one value per outer column. A closed term reads none, so the argument defaults to a valuation no one looks at (Fin 0 is empty) and closed uses write t.eval u.

        Equations
        Instances For
          Dependency graph
          @[instance_reducible]
          instance instCoeTerm {T : Type} {n : ℕ} :
          Coe T (Term T n)
          Equations
          Dependency graph
          @[instance_reducible]
          instance instOfNatTermNat {n a : ℕ} :
          OfNat (Term ℕ n) a
          Equations
          Dependency graph
          Dependency graph
          inductive BoolTerm (T : Type) (n : ℕ) :
          Instances For
            Dependency graph
            def BoolTerm.repr {T : Type} {n : ℕ} [Repr T] :
            BoolTerm T n → ℕ → Std.Format
            Equations
            Instances For
              Dependency graph
              @[instance_reducible]
              instance instReprBoolTerm {α : Type} {n : ℕ} [Repr α] :
              Repr (BoolTerm α n)
              Equations
              Dependency graph
              Dependency graph
              Dependency graph
              Dependency graph

              IS NOT DISTINCT FROM.

              Equations
              Instances For
                Dependency graph
                Dependency graph
                def BoolTerm.args {T : Type} {n : ℕ} :
                BoolTerm T n → Term T n × Term T n

                The two terms a Boolean term compares.

                Equations
                Instances For
                  Dependency graph
                  def BoolTerm.eval3 {T : Type} [ValueType T] {n : ℕ} (φ : BoolTerm T n) (tuple : Tuple T n) :

                  Three-valued evaluation of a comparison: a comparison with a NULL operand is neither true nor false.

                  Equations
                  Instances For
                    Dependency graph
                    def BoolTerm.eval {T : Type} [ValueType T] {n : ℕ} (φ : BoolTerm T n) (tuple : Tuple T n) :

                    The rows a comparison keeps: those on which it is true.

                    Equations
                    Instances For
                      Dependency graph
                      @[reducible]
                      Equations
                      Instances For
                        Dependency graph
                        inductive Selection (T : Type) (n : ℕ) :
                        Instances For
                          Dependency graph
                          def Selection.repr {T : Type} {n : ℕ} [Repr T] :
                          Equations
                          Instances For
                            Dependency graph
                            @[instance_reducible]
                            instance instReprSelection {α : Type} {n : ℕ} [Repr α] :
                            Equations
                            Dependency graph
                            Dependency graph
                            def Selection.eval3 {T : Type} [ValueType T] {n : ℕ} (φ : Selection T n) (tuple : Tuple T n) :

                            Three-valued evaluation of a selection, in Kleene's logic: a row on which the predicate is unknown is selected by neither it nor its negation.

                            Equations
                            Instances For
                              Dependency graph
                              def Selection.eval {T : Type} [ValueType T] {n : ℕ} (φ : Selection T n) (tuple : Tuple T n) :

                              The rows a selection keeps: those on which it is true.

                              Equations
                              Instances For
                                Dependency graph
                                def Selection.keeps {T : Type} [ValueType T] {n : ℕ} (φ : Selection T n) (u : Tuple T n) :

                                The rows a selection keeps, as a test. SQL keeps a row when the condition is true, an unknown counting as a rejection, so the three-valued reading becomes two-valued here. This is the form a FILTER clause is read in, where a sequence has to be cut.

                                Equations
                                Instances For
                                  Dependency graph
                                  @[reducible]
                                  Equations
                                  Instances For
                                    Dependency graph
                                    @[simp]
                                    theorem Selection.eval_not {T : Type} [ValueType T] {n : ℕ} (φ : Selection T n) (t : Tuple T n) :

                                    A row is kept by NOT φ when φ is false, which is not the same as φ failing to be true: a row on which φ is unknown is kept by neither.

                                    Dependency graph
                                    theorem Selection.eval3_ne_unknown {T : Type} [ValueType T] {n : ℕ} [NoNulls T] (t : Tuple T n) (φ : Selection T n) :

                                    Where nothing is null no selection is ever unknown.

                                    Dependency graph
                                    theorem Selection.eval_not_iff {T : Type} [ValueType T] {n : ℕ} [NoNulls T] (φ : Selection T n) (t : Tuple T n) :
                                    φ.Not.eval t ↔ ¬φ.eval t

                                    Negation is classical where nothing is null.

                                    Dependency graph
                                    @[instance_reducible]
                                    instance instCoeBoolTermSelection {T : Type} {n : ℕ} :
                                    Coe (BoolTerm T n) (Selection T n)
                                    Equations
                                    Dependency graph
                                    def addFn {T : Type} [ValueType T] (a b : T) :
                                    T

                                    Addition as a binary function, the fold of the ⊕-sum performed by the rewriting-target operator Query.ProvSum (and by its general-syntax counterpart AggQueryIn.ProvSum).

                                    Equations
                                    Instances For
                                      Dependency graph
                                      Dependency graph
                                      Dependency graph
                                      def SeqAggFunc (T : Type) :

                                      An aggregate function on sequences of values: an arbitrary function from finite sequences over T to T. Beyond the monoid-shaped ⊕-sum of Query.ProvSum, this interface covers non-commutative aggregates – such as PICKFIRST, whose result depends on the order of its input – and non-associative ones. It is the aggregate interface of the fused Having operator, whose possible-world semantics does not need any algebraic structure on the aggregate.

                                      Equations
                                      Instances For
                                        Dependency graph

                                        An aggregate is a total function on sequences, so each one has to say what it does with the empty sequence. Where a row exists only because its group does, that value is never read and the choice is immaterial. Where the row exists on its own – an aggregation over no grouping, a frame that may exclude the row it is computed for – it is read, by the scalar convention of AggValue.predProvScalar.

                                        Each aggregate of SQL also comes with an input policy, which says what it reads of a sequence in which some values are null. There are three. Null-skipping (SUM, MIN, MAX, AVG …) drops the nulls and answers NULL over what is left of nothing: that is sqlOf. Counting (COUNT) reads every occurrence, which counts when its value is not null, and answers 0 over nothing: that is counting. Null-keeping (ARRAY_AGG, …) reads every value, nulls included: that is the aggregate itself.

                                        The aggregates below are those of a domain with no null, and they give the zero of the value type over no row. COUNT is right that way: SQL counts no row as 0. SUM, MIN and MAX are not, since SQL gives NULL there, and sqlOf is what makes them so on a domain that has a null – it skips the nulls, as SQL does, and gives NULL when nothing is left. COUNT(*) stays unwrapped, being the one aggregate SQL does not read that way.

                                        SUM as a sequence aggregate; 0 on the empty sequence, where SQL has null.

                                        Equations
                                        Instances For
                                          Dependency graph

                                          COUNT(*) as a sequence aggregate (over an ℕ-valued domain); 0 on the empty sequence, as SQL has.

                                          Equations
                                          Instances For
                                            Dependency graph

                                            MIN, with the zero of the value type as its default on the empty sequence, where SQL has null.

                                            Equations
                                            Instances For
                                              Dependency graph

                                              MAX, with the zero of the value type as its default on the empty sequence, where SQL has null.

                                              Equations
                                              Instances For
                                                Dependency graph

                                                PICKFIRST: the first value of the sequence, with the zero of the value type as its default on the empty one, where SQL has null.

                                                Equations
                                                Instances For
                                                  Dependency graph

                                                  The value at offset i of the sequence, counting from 0, with the zero of the value type where the sequence is shorter, and PICKFIRST at offset 0. It is the aggregate SQL's nth_value, lag(t, k) and lead(t, k) read a frame through, which PICKFIRST alone cannot give: it reads one end of the frame and no other position.

                                                  Equations
                                                  Instances For
                                                    Dependency graph

                                                    SQL's reading of an aggregate on a domain with a null: skip the nulls, and give NULL when nothing is left. SUM, MIN and MAX are read this way. COUNT is not: it gives 0 over no row, which is what the unwrapped aggregate already does.

                                                    Equations
                                                    Instances For
                                                      Dependency graph

                                                      SQL's counting input policy: every occurrence is read, and counts when its value is not null. This is COUNT(t).

                                                      It is not sqlOf. The two agree on dropping the nulls and part company on what is left of nothing, where a null-skipping aggregate answers NULL and a count answers 0. COUNT(*) needs neither, being COUNT over a term that is never null, so that every occurrence counts and the plain count of the sequence is already right.

                                                      Equations
                                                      Instances For
                                                        Dependency graph
                                                        structure SeqAggFunc.Counts {V : Type} [ValueType V] (cnt : SeqAggFunc V) :

                                                        What it takes for an aggregate to count matches: it is never null, and it is zero exactly when it has no non-null value to count. SQL's count(e) is such an aggregate.

                                                        Instances For
                                                          Dependency graph

                                                          Which aggregates read their input as a multiset #

                                                          The interface is a function on sequences, so an aggregate may depend on the order of its input, and PICKFIRST does. The ones that do not are the ones a grouping or a window can compute without settling how its rows are sequenced: for them the canonical order the library sorts by is as good as the order an ORDER BY asks for, and for the others it is not.

                                                          An aggregate is symmetric when it reads its input as a multiset: permuting the sequence does not change the answer.

                                                          Equations
                                                          Instances For
                                                            Dependency graph
                                                            def SeqAggFunc.onBag {T : Type} (f : SeqAggFunc T) (hf : f.Symmetric) :
                                                            Multiset T → T

                                                            A symmetric aggregate as a function of a bag. It does not read the order of its sequence, so it is a function of the bag of values. This is what a nested aggregate value needs: the order ≼ is an order on plain tuples, and an occurrence of a nested value carries a tuple with an aggregate column, so there is no sequence for an order-dependent aggregate to read and the bag is the input.

                                                            Equations
                                                            Instances For
                                                              Dependency graph
                                                              Dependency graph
                                                              Dependency graph

                                                              f^distinct: the aggregate read over the distinct values of its sequence. Over plain relations this is SQL's DISTINCT aggregate, an aggregate value being an ordinary value there. Over annotated relations a grouped DISTINCT aggregate is not this transformer but the abbreviation AggQueryIn.gammaDistinct, which deduplicates the rows first, so that each distinct value is one occurrence annotated by the ⊕ of the occurrences it stands for.

                                                              Equations
                                                              Instances For
                                                                Dependency graph

                                                                MIN and MAX return one of their inputs #

                                                                inductive Query (T : Type) :
                                                                ℕ → Type
                                                                • Rel {T : Type} (n : ℕ) : String → Query T n
                                                                • Proj {T : Type} {n m : ℕ} : Tuple (Term T n) m → Query T n → Query T m
                                                                • Sel {T : Type} {n : ℕ} : Selection T n → Query T n → Query T n
                                                                • Prod {T : Type} {n₁ n₂ n : ℕ} {hn : n₁ + n₂ = n} : Query T n₁ → Query T n₂ → Query T n
                                                                • Sum {T : Type} {n : ℕ} : Query T n → Query T n → Query T n
                                                                • Dedup {T : Type} {n : ℕ} : Query T n → Query T n
                                                                • Diff {T : Type} {n : ℕ} : Query T n → Query T n → Query T n
                                                                • ProvSum {T : Type} {m n₁ : ℕ} : Tuple (Fin m) n₁ → Term T m → Query T m → Query T (n₁ + 1)

                                                                  Provenance aggregation: group by the key columns of the first argument and ⊕-sum the term of the second over each group into a single trailing output column. It is not a source operator – aggregation as such lives on the general syntax (AggQueryIn.Gamma) – but the target of the (R1)–(R4) rewriting: the ⊕-gate creation of the ε and ∖ rules of Query.rewriting. Its general-syntax counterpart is AggQueryIn.ProvSum.

                                                                • Having {T : Type} {m n₁ n₂ : ℕ} : Tuple (Fin m) n₁ → Tuple (Term T m) n₂ → Tuple (SeqAggFunc T) n₂ → CompOp → Fin n₂ → Term T n₁ → Query T m → Query T (n₁ + n₂)

                                                                  The fused HAVING operator: grouping by the indices of the first argument, computing the sequence aggregates of the third argument applied to the terms of the second (each group read in the canonical tuple order, which plays the role of the ordering ≼ of non-commutative aggregates), and keeping only the groups whose aggregate value in column l (the Fin n₂ argument) compares, via the comparison operator, with the value of the regular term (the Term T n₁ argument, evaluated on the group key – this covers both query constants and group-key attributes). The output has the group key followed by the aggregate values.

                                                                Instances For
                                                                  Dependency graph
                                                                  def Query.repr {T : Type} {n : ℕ} [Repr T] :
                                                                  Query T n → ℕ → Std.Format
                                                                  Equations
                                                                  Instances For
                                                                    Dependency graph
                                                                    @[instance_reducible]
                                                                    instance instReprQuery {α : Type} {n : ℕ} [Repr α] :
                                                                    Repr (Query α n)
                                                                    Equations
                                                                    Dependency graph
                                                                    def Query.source {T : Type} {n : ℕ} (q : Query T n) :

                                                                    The source fragment of the classical syntax: the operators a query is written with, RA⁺(∖). It excludes the two operators that are not source operators – ProvSum, which the (R1)–(R4) rewriting emits, and the fused Having, whose semantics lives on the general syntax – and is exactly the fragment carrying an annotated semantics (Query.evaluateAnnotated) and accepted by Query.rewriting. Its general-syntax counterpart is AggQueryIn.classical.

                                                                    Equations
                                                                    Instances For
                                                                      Dependency graph
                                                                      @[reducible]
                                                                      Equations
                                                                      Instances For
                                                                        Dependency graph
                                                                        Dependency graph
                                                                        @[simp]
                                                                        theorem Query.sourceProd {T : Type} [ValueType T] {n n₂ : ℕ} {q : Query T n} :
                                                                        q.source → ∀ {n₁ : ℕ} {q₁ : Query T n₁} {q₂ : Query T n₂} {hn : n₁ + n₂ = n}, q = q₁.Prod q₂ → q₁.source ∧ q₂.source
                                                                        Dependency graph
                                                                        @[simp]
                                                                        theorem Query.sourceSum {T : Type} [ValueType T] {n : ℕ} {q : Query T n} :
                                                                        q.source → ∀ {q₁ q₂ : Query T n}, q = (q₁ ⊎ q₂) → q₁.source ∧ q₂.source
                                                                        Dependency graph
                                                                        @[simp]
                                                                        theorem Query.sourceDiff {T : Type} [ValueType T] {n : ℕ} {q : Query T n} :
                                                                        q.source → ∀ {q₁ q₂ : Query T n}, q = (q₁ - q₂) → q₁.source ∧ q₂.source
                                                                        Dependency graph
                                                                        @[simp]
                                                                        theorem Query.sourceProj {T : Type} [ValueType T] {n : ℕ} {q : Query T n} :
                                                                        q.source → ∀ {m : ℕ} {t : Tuple (Term T m) n} {q' : Query T m}, q = Π t q' → q'.source
                                                                        Dependency graph
                                                                        @[simp]
                                                                        theorem Query.sourceSel {T : Type} [ValueType T] {n : ℕ} {q : Query T n} :
                                                                        q.source → ∀ {φ : Selection T n} {q' : Query T n}, q = σ φ q' → q'.source
                                                                        Dependency graph
                                                                        @[simp]
                                                                        theorem Query.sourceDedup {T : Type} [ValueType T] {n : ℕ} {q : Query T n} :
                                                                        q.source → ∀ {q' : Query T n}, q = ε q' → q'.source
                                                                        Dependency graph
                                                                        Dependency graph
                                                                        Dependency graph
                                                                        Dependency graph
                                                                        Dependency graph
                                                                        Dependency graph
                                                                        Dependency graph
                                                                        Dependency graph
                                                                        Dependency graph
                                                                        def Query.arity {T : Type} {n : ℕ} :
                                                                        Query T n → ℕ
                                                                        Equations
                                                                        Instances For
                                                                          Dependency graph
                                                                          Dependency graph
                                                                          def Relation.groupSeq {T : Type} [ValueType T] {m n₁ : ℕ} (is : Tuple (Fin m) n₁) (r : Relation T m) (g : Tuple T n₁) :
                                                                          List (Tuple T m)

                                                                          The occurrences of the group of key g in relation r: the multiset of matching tuples, as a list sorted by the canonical linear order on tuples. The sort order plays the role of the ordering ≼ along which non-commutative sequence aggregates read the occurrences of a group; for commutative aggregates it is irrelevant.

                                                                          Equations
                                                                          Instances For
                                                                            Dependency graph
                                                                            def Relation.groupSeqOpt {T : Type} [ValueType T] {m n₁ : ℕ} (is : Tuple (Fin m) n₁) (r : Relation T m) (g : Tuple T n₁) (keep : Option (Selection T m)) :
                                                                            List (Tuple T m)

                                                                            The occurrence sequence an aggregate of a grouping reads: the group's rows, cut by a FILTER clause where the aggregate carries one. Both the plain evaluator and the rewritten world's evaluator read a group through this, so the two agree clause for clause.

                                                                            Equations
                                                                            Instances For
                                                                              Dependency graph
                                                                              @[irreducible]
                                                                              def Query.evaluate {T : Type} [ValueType T] {n : ℕ} (q : Query T n) (d : Database T) :

                                                                              Standard multiset semantics of a query over a plain database.

                                                                              The Diff case is all-or-nothing difference: every copy of a tuple that occurs at all in r₂ is removed from r₁ (deliberately not Multiset.sub, which would subtract multiplicities as in SQL's EXCEPT ALL). This matches the monus-based annotated semantics of difference (Query.evaluateAnnotated) exactly on 0/1-annotated inputs; on general annotations the two disagree over ℕ (see Nat.counterexample_diff_adequacy and Provenance.QueryAdequacy).

                                                                              Equations
                                                                              Instances For
                                                                                Dependency graph