Documentation

Provenance.AggQueryEmbedding

The compositional JOIN rewriting, on the general syntax #

The HAVING COUNT(*) site of the compositional rewriting theorem is, in the general syntax, the key projection of σ_ψ ∘ Gamma – all-regular, since the projection drops the token columns – so it composes under every operator of the general syntax, and the ProvSQL-legal contexts around a site are exactly the expressible ones. GenCountHavingRewrite replaces such sites by the embedded padded join query (Query.toAgg, from Provenance.QueryToAgg), and GenCountHavingRewrite.evaluateGen_eq proves the replacement preserves the general evaluator's rows verbatim, in absorptive m-semirings whose ⊗ distributes over ⊖. The expressible contexts around a site are exactly the ProvSQL-legal ones: the kind discipline forbids deduplicating, differencing or re-grouping aggregate values, matching the system.

def genCountHavingSite (ts' : Tuple (Term ℕ 3) 1) (op : CompOp) (C : ℕ) (g : AggQuery ℕ 3 (ColKind.allReg 3)) :

A HAVING COUNT(*) op (C + 1) site on the general syntax: the fused comparison over the grouping, projected to its group key – all-regular output.

Equations
  • One or more equations did not get rendered due to their size.
Instances For
    Dependency graph

    The JOIN rewriting on the general syntax: congruence rules per operator, and the site rule replacing a HAVING COUNT(*) site by the embedded padded join query built over any classical query with the same annotated semantics as the site's grouped subquery.

    Instances For
      Dependency graph

      Compositional correctness of the JOIN rewriting, general syntax: in an absorptive commutative m-semiring whose ⊗ distributes over ⊖, rewriting any number of HAVING COUNT(*) sites – wherever they occur – preserves the general evaluator's rows verbatim.

      Dependency graph