Documentation

Provenance.AggQueryRewriting

The rewriting rules (R1)–(R4), natively on the general syntax #

The rewriting of Sen, Maniu & Senellart, ProvSQL turns a query over annotated relations into an ordinary query over the composite encoding: one extra column carries the annotation, of the lifted value type T ⊕ K. With the three-kind discipline the rewriting is expressible natively: the annotation column is marked prov (ColKind.rewKinds), read back by TermGIn.provIndex terms, aggregated by AggQueryIn.ProvSum (the ⊕-gate creation of ε and ∖), and the value-kind bookkeeping is AggQueryIn.Retag – semantically the identity.

AggQueryIn.rewriting below mirrors the classical Query.rewriting rule for rule on the classical fragment (AggQueryIn.classical) of the general syntax. Its correctness against evaluateAnnotated is assembled in stages, over the next two modules: the strip to the classical syntax and its faithfulness (Provenance.AggQueryStrip), then the plain-semantics agreement of the two rewritten queries and the correctness theorem itself (Provenance.AggQueryRewritingValid).

This module holds the syntax of the rewriting: the target kind vector, the classical fragment, the casts into the composite domain, and AggQueryIn.rewriting.

The target kind vector #

def ColKind.rewKinds (n : ℕ) :
Fin (n + 1) → ColKind

The kind vector of a rewritten query: n data columns followed by the provenance column.

Equations
Instances For
    Dependency graph
    theorem ColKind.rewKinds_lt {n : ℕ} {k : Fin (n + 1)} (h : ↑k < n) :
    Dependency graph
    theorem ColKind.rewKinds_of_not_lt {n : ℕ} {k : Fin (n + 1)} (h : ¬↑k < n) :
    Dependency graph
    theorem ColKind.rewKinds_base {n : ℕ} (k : Fin (n + 1)) :
    Dependency graph
    def AggQueryIn.retagToRew {T' : Type} {n : ℕ} {κ : Fin (n + 1) → ColKind} (h : ∀ (k : Fin (n + 1)), (κ k).base = ColKind.reg) (q : AggQuery T' (n + 1) κ) :

    Retag any pointwise value-kinded query to the rewriting kinds.

    Equations
    Instances For
      Dependency graph

      The classical fragment #

      def AggQueryIn.classical {T : Type} {c n : ℕ} {κ : Fin n → ColKind} {l : List (String × ℕ)} :
      AggQueryIn T c n κ l → Prop

      The classical (R1)–(R4) source fragment of the general syntax: no grouping, no provenance aggregation, no retagging, projections through regular terms only, selections without aggregate atoms.

      Equations
      Instances For
        Dependency graph
        theorem AggQueryIn.classical_kinds {T : Type} {c n : ℕ} {κ : Fin n → ColKind} {l : List (String × ℕ)} (q : AggQueryIn T c n κ l) :
        q.classical → ∀ (k : Fin n), κ k = ColKind.reg

        Classical queries have all-regular kinds (pointwise).

        Dependency graph

        Casting terms, predicates and columns to the composite domain #

        def TermGIn.castComposite {T : Type} [ValueType T] {K : Type} {c n : ℕ} {κ : Fin n → ColKind} (hκ : ∀ (k : Fin n), κ k = ColKind.reg) :
        TermGIn T c κ → TermG (T ⊕ K) (ColKind.rewKinds n)

        A term over all-regular columns, over the composite domain with its columns shifted into the data block of the rewritten schema.

        Equations
        Instances For
          Dependency graph
          def GenPredIn.castComposite {T : Type} [ValueType T] {K : Type} {c n : ℕ} {κ : Fin n → ColKind} (hκ : ∀ (k : Fin n), κ k = ColKind.reg) (φ : GenPredIn T c κ) :

          An aggregate-atom-free predicate, over the composite domain.

          Equations
          Instances For
            Dependency graph
            def ProjColIn.castComposite {T : Type} [ValueType T] {K : Type} {c n : ℕ} {κ : Fin n → ColKind} (hκ : ∀ (k : Fin n), κ k = ColKind.reg) (p : ProjColIn T c κ) :

            A regular projection column, over the composite domain.

            Equations
            Instances For
              Dependency graph
              theorem ProjColIn.castComposite_kind {T : Type} [ValueType T] {K : Type} {c n : ℕ} {κ : Fin n → ColKind} (hκ : ∀ (k : Fin n), κ k = ColKind.reg) (p : ProjColIn T c κ) (hp : p.kind = ColKind.reg) :
              Dependency graph

              The rewriting #

              def AggQueryIn.rewriting {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [HasAltLinearOrder K] {c n : ℕ} {κ : Fin n → ColKind} {l : List (String × ℕ)} (q : AggQueryIn T c n κ l) :
              q.classical → AggQuery (T ⊕ K) (n + 1) (ColKind.rewKinds n)

              The (R1)–(R4) rewriting, natively on the general syntax. Each rule mirrors the classical Query.rewriting: the base relation exposes its provenance column (R1), projections keep it verbatim (R2, key case), selections filter the data columns (R2), joins multiply the two provenance columns (R3), unions concatenate (R4, first case), deduplication ⊕-sums the provenance per surviving tuple (R4, ε), and difference combines the unmatched branch with the matched branch's α ⊖ Σβ (R4, ∖).

              Equations
              Instances For
                Dependency graph