Documentation

Provenance.AggQueryStrip

Stripping the classical fragment to the classical syntax #

The classical fragment AggQueryIn.classical of the general syntax maps back, operator for operator, to the classical Query syntax of Provenance.Query. AggQueryIn.strip is that map, and AggQueryIn.strip_bridge says it is faithful: the general annotated evaluator and the classical one agree on it. The rewriting correctness of Provenance.AggQueryRewritingValid goes through this bridge and the classical theorem Query.rewriting_valid.

The strips of terms, predicates and projection columns send an outer column to the constant 𝟘, which is what the valuation a closed query reads gives it, so the agreement statements below hold as they stand.

Stripping to the classical syntax #

The classical fragment of the general syntax maps back to the classical Query syntax; the correctness of the native rewriting is assembled through this strip, the classical correctness theorem, and the plain-semantics agreement of the two rewritten queries.

def TermGIn.strip {T : Type} [ValueType T] {c n : ℕ} {κ : Fin n → ColKind} :
TermGIn T c κ → Term T n

Strip a term over regular columns to a classical term (the provIndex arm is unreachable on the classical fragment and mapped harmlessly).

Equations
Instances For
    Dependency graph
    def GenPredIn.strip {T : Type} [ValueType T] {c n : ℕ} {κ : Fin n → ColKind} :
    GenPredIn T c κ → Selection T n

    Strip an aggregate-atom-free predicate to a classical selection.

    Equations
    Instances For
      Dependency graph
      def ProjColIn.strip {T : Type} [ValueType T] {c n : ℕ} {κ : Fin n → ColKind} :
      ProjColIn T c κ → Term T n

      Strip a regular projection column to a classical term.

      Equations
      Instances For
        Dependency graph
        def AggQueryIn.strip {T : Type} [ValueType T] {c n : ℕ} {κ : Fin n → ColKind} {l : List (String × ℕ)} (q : AggQueryIn T c n κ l) :
        q.classical → Query T n

        Strip a classical-fragment query to the classical syntax.

        Equations
        Instances For
          Dependency graph
          theorem AggQueryIn.strip_source {T : Type} [ValueType T] {c n : ℕ} {κ : Fin n → ColKind} {l : List (String × ℕ)} (q : AggQueryIn T c n κ l) (hq : q.classical) :
          (q.strip hq).source

          The strip is aggregation-free.

          Dependency graph

          Faithfulness of the strip #

          theorem AggQueryIn.strip_bridge {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {n : ℕ} {κ : Fin n → ColKind} (q : AggQuery T n κ) (hq : classical q) (d : AnnotatedDatabase T K) :

          Faithfulness of the strip: on the classical fragment the general annotated evaluator computes the classical annotated semantics of the stripped query.

          Dependency graph