Compositional correctness of the JOIN rewriting for HAVING COUNT(*) #
Provenance.HavingQueryCorrectness proves the join-based rewriting of a
HAVING COUNT(*) op (C+1) correct extensionally: per group key, the sum
of the annotations of the join query's rows is the fused predicate
provenance. This file upgrades that to an intensional, multiset-level
equality, the form needed to substitute the rewriting for the fused
operator inside an arbitrary surrounding query.
The one obstruction to multiset-level equality is the failing groups: the
fused operator emits a π-annotated row for a group that fails the
comparison, while the join query emits no row at all. The rewriting is
therefore padded: joinCountQueryPadded adds to the join query the
self-difference keysQuery q β keysQuery q β one π-annotated row per
group key β and duplicate-eliminates the union, which merges everything
into exactly one row per group key carrying the summed annotation. The
result (joinCountQueryPadded_correct) is equal as a multiset of
annotated tuples to the key projection of the fused HAVING output
(fused_key_proj), so the substitution is transparent to every
surrounding operator β including annotation-sensitive ones like Diff
and further HAVINGs, which are not congruences for the naive
βequal up to π-rowsβ relation (a π-annotated row still changes the
deterministic aggregate values of an enclosing group).
AnnotatedRelation is an opaque def over Multiset, so instance
search does not see the multiset membership through it; register it.
Dependency graph
The padded join query #
The canonical key selector of the (key, value, identifier) base
schema.
Equations
- keyIdx xβ = β¨0, keyIdx._proof_2β©
Instances For
Dependency graph
The key column, as a projection term.
Instances For
Dependency graph
The group key of an annotated base row.
Equations
- keyOf p xβ = p.1 β¨0, keyIdx._proof_2β©
Instances For
Dependency graph
One row per distinct group key, annotated by the β-sum of the
group's annotations.
Instances For
Dependency graph
One π-annotated row per distinct group key: the self-difference of
the key query (Ξ± β Ξ± = π).
Equations
- zeroPadQuery q = (keysQuery q - keysQuery q)
Instances For
Dependency graph
Key padding of a one-column rewriting Q of a HAVING site over the
base query q: Q, padded with a π-annotated row per group key of q
and duplicate-eliminated into one row per group key.
Equations
- keyPadded Q q = Ξ΅ (Q q β zeroPadQuery q)
Instances For
Dependency graph
The padded join-based rewriting of HAVING COUNT(*) op (C + 1):
the join query, padded with a π-annotated row per group key and
duplicate-eliminated into one row per group key.
Equations
- joinCountQueryPadded q op C = keyPadded (fun (q : Query β 3) => q.joinCountQuery op C) q
Instances For
Dependency graph
Dependency graph
Dependency graph
Key bookkeeping #
Evaluation of the padding #
Site correctness: the padded rewriting, row for row #
Multiset-level correctness of the padded JOIN rewriting. In an
absorptive commutative m-semiring whose β distributes over β, the
padded join-based query evaluates to exactly β row for row, annotation
for annotation β one row per group key of the base query, annotated with
the fused COUNT(*) op (C + 1) predicate provenance. The sole hypothesis
is the injective per-group occurrence identifiers (global
row-distinctness of the base query's output).
Dependency graph
Padded rewriting of the monotone comparisons, without
distributivity. For op β {β₯, >}, joinCountQueryPadded_correct holds
in every absorptive commutative m-semiring
(Query.joinCount_monotone_correct).
Dependency graph
The COUNT(*) op (C + 1) instance of fused_key_proj_gen.
Dependency graph
Site substitution. The key-projected fused
HAVING COUNT(*) op (C + 1) site over the embedded classical query and
the padded join-based rewriting
evaluate to the same multiset of annotated tuples: substituting one for
the other inside any surrounding query preserves the annotated semantics
verbatim.
Dependency graph
Site substitution for the monotone comparisons, in every absorptive
commutative m-semiring: countHaving_site_rewrite for op β {β₯, >} with
the distributivity hypothesis dropped.