Documentation

Provenance.QueryToAgg

Embedding the classical query syntax into the general evaluator #

Query.toAgg embeds a non-aggregating classical query into the kind-indexed general syntax AggQuery, over all-regular kinds: terms, selection predicates and every operator translate one to one. Query.toAgg_bridge proves the embedding faithful – the general evaluator computes the classical annotated semantics – via a row-wise invariant GenRow.Inv (regular data, finalized annotation) that absorbs the bookkeeping differences of the factored annotations (a pending multiset that stays empty, bases multiplied by empty products).

On top of the embedding, Query.toAggHaving_input reads the input relation of a general HAVING site over an embedded subquery off the classical query's annotated semantics, which is what the query-level HAVING correctness results consume.

This module sits below the classical HAVING correctness files (Provenance.HavingQueryCorrectness, Provenance.HavingJoinCompositional) so that they can state their theorems over the embedded general query directly, with no side hypothesis. The compositional JOIN rewriting built on top of the embedding lives in Provenance.AggQueryEmbedding.

Terms and selections over all-regular kinds #

def TermIn.toGenReg {T : Type} {n : ℕ} :
Term T n → TermG T (ColKind.allReg n)

A classical term, as a term over all-regular columns.

Equations
Instances For
    Dependency graph
    Dependency graph

    A classical selection predicate, as a generalized predicate without aggregate atoms (Selection.True becomes the tautology 𝟘 = 𝟘).

    Equations
    Instances For
      Dependency graph

      The embedding #

      theorem ColKind.allReg_append (n₁ n₂ : ℕ) :
      Fin.append (allReg n₁) (allReg n₂) = allReg (n₁ + n₂)

      Appending all-regular kind vectors.

      Dependency graph
      def Query.toAgg {T : Type} [ValueType T] {n : ℕ} (q : Query T n) :

      The embedding of the non-aggregating fragment: every classical operator translates to its general counterpart, over all-regular kinds.

      Equations
      Instances For
        Dependency graph

        Faithfulness #

        def GenRow.Inv {T K : Type} [CommSemiringWithMonus K] {n : ℕ} (r : GenRow T K n) (p : AnnotatedTuple T K n) :

        The row invariant of the embedding: regular data over the classical tuple, a factored annotation finalizing to the classical one, and no pending group factors (the embedding image contains no Gamma).

        Equations
        Instances For
          Dependency graph

          Faithfulness of the embedding: the general evaluator computes the classical annotated semantics on embedded queries.

          Dependency graph

          The embedding at the row level: the general evaluator on an embedded query produces exactly the embedded classical rows.

          Dependency graph

          The fused HAVING, in context #

          The fused HAVING site over an embedded subquery: its input relation is the classical subquery's annotated evaluation, so the closed form AggQueryIn.havingSite_evaluateAnnotated specializes to the classical setting with no side hypothesis.

          Dependency graph