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.
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.
- refl {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {d : AnnotatedDatabase ℕ K} {n : ℕ} {κ : Fin n → ColKind} (q : AggQuery ℕ n κ) : GenCountHavingRewrite d q q
- proj {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {d : AnnotatedDatabase ℕ K} {n m : ℕ} {κ : Fin n → ColKind} (ps : Tuple (ProjCol ℕ κ) m) {q q' : AggQuery ℕ n κ} : GenCountHavingRewrite d q q' → GenCountHavingRewrite d (AggQueryIn.Proj ps q) (AggQueryIn.Proj ps q')
- sel {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {d : AnnotatedDatabase ℕ K} {n : ℕ} {κ : Fin n → ColKind} (φ : GenPred ℕ κ) {q q' : AggQuery ℕ n κ} : GenCountHavingRewrite d q q' → GenCountHavingRewrite d (AggQueryIn.Sel φ q ⋯) (AggQueryIn.Sel φ q' ⋯)
- prod {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {d : AnnotatedDatabase ℕ K} {n₁ n₂ : ℕ} {κ₁ : Fin n₁ → ColKind} {κ₂ : Fin n₂ → ColKind} {q₁ q₁' : AggQuery ℕ n₁ κ₁} {q₂ q₂' : AggQuery ℕ n₂ κ₂} : GenCountHavingRewrite d q₁ q₁' → GenCountHavingRewrite d q₂ q₂' → GenCountHavingRewrite d (AggQueryIn.Prod q₁ q₂) (AggQueryIn.Prod q₁' q₂')
- sum {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {d : AnnotatedDatabase ℕ K} {n : ℕ} {κ : Fin n → ColKind} {q₁ q₁' q₂ q₂' : AggQuery ℕ n κ} : GenCountHavingRewrite d q₁ q₁' → GenCountHavingRewrite d q₂ q₂' → GenCountHavingRewrite d (AggQueryIn.Sum q₁ q₂) (AggQueryIn.Sum q₁' q₂')
- dedup {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {d : AnnotatedDatabase ℕ K} {n : ℕ} {q q' : AggQuery ℕ n (ColKind.allReg n)} : GenCountHavingRewrite d q q' → GenCountHavingRewrite d (AggQueryIn.Dedup q) (AggQueryIn.Dedup q')
- diff {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {d : AnnotatedDatabase ℕ K} {n : ℕ} {q₁ q₁' q₂ q₂' : AggQuery ℕ n (ColKind.allReg n)} : GenCountHavingRewrite d q₁ q₁' → GenCountHavingRewrite d q₂ q₂' → GenCountHavingRewrite d (AggQueryIn.Diff q₁ q₂) (AggQueryIn.Diff q₁' q₂')
- gamma {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {d : AnnotatedDatabase ℕ K} {lab m n₁ n₂ : ℕ} {rd : Fin 0 → Bool} (is : Tuple (Fin m) n₁) (ts : Tuple (Term ℕ m) n₂) (fs : Tuple (SeqAggFunc ℕ) n₂) {q q' : AggQuery ℕ m (ColKind.allReg m)} : GenCountHavingRewrite d q q' → GenCountHavingRewrite d (AggQueryIn.Gamma is ts fs q) (AggQueryIn.Gamma is ts fs q')
- site {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {d : AnnotatedDatabase ℕ K} (ts' : Tuple (Term ℕ 3) 1) (op : CompOp) (C : ℕ) {g g' : AggQuery ℕ 3 (ColKind.allReg 3)} (q' : Query ℕ 3) (hq' : q'.source) : GenCountHavingRewrite d g g' → AggQueryIn.evaluateAnnotated g' d = q'.evaluateAnnotated hq' d → (Multiset.map Prod.fst (q'.evaluateAnnotated hq' d)).Nodup → GenCountHavingRewrite d (genCountHavingSite ts' op C g) ((joinCountQueryPadded q' op C).toAgg ⋯)
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.