Documentation

Provenance.AggQueryRewritingValid

Correctness of the native rewriting #

The last stage: the query the general syntax rewrites to and the classical rewriting of its strip evaluate identically under the plain semantics (AggQueryIn.rewriting_plain), whence the correctness theorem AggQueryIn.rewriting_valid – evaluating the annotated semantics and folding the rows into composite T ⊕ K tuples is evaluating the rewritten query over the composite database.

Plain-semantics agreement of the two rewritten queries #

theorem AggQueryIn.rewriting_plain {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {c n : ℕ} {κ : Fin n → ColKind} {l : List (String × ℕ)} (q : AggQueryIn T c n κ l) (hq : q.classical) (D : Database (T ⊕ K)) :

Plain-semantics agreement: the native rewriting and the classical rewriting of the stripped query evaluate identically on any composite database.

Dependency graph

Rewriting correctness #

Correctness of the native rewriting. For a classical query in the general syntax, evaluating the annotated semantics and folding the result into composite T ⊕ K tuples agrees with evaluating the rewritten query under the plain semantics over the composite database. This is the general-syntax form of the classical rewriting correctness.

Dependency graph