Documentation

Provenance.HavingJoinCompositional

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).

@[instance_reducible]

AnnotatedRelation is an opaque def over Multiset, so instance search does not see the multiset membership through it; register it.

Equations
Dependency graph

The padded join query #

def keyIdx :
Tuple (Fin 3) 1

The canonical key selector of the (key, value, identifier) base schema.

Equations
Instances For
    Dependency graph

    The key column, as a projection term.

    Equations
    Instances For
      Dependency graph
      def keyOf {K : Type} (p : AnnotatedTuple β„• K 3) :

      The group key of an annotated base row.

      Equations
      Instances For
        Dependency graph

        One row per distinct group key, annotated by the βŠ•-sum of the group's annotations.

        Equations
        Instances For
          Dependency graph

          One 𝟘-annotated row per distinct group key: the self-difference of the key query (Ξ± βŠ– Ξ± = 𝟘).

          Equations
          Instances For
            Dependency graph
            def keyPadded (Q : Query β„• 3 β†’ Query β„• 1) (q : Query β„• 3) :

            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
            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
              Instances For
                Dependency graph
                theorem keyPadded_source (Q : Query β„• 3 β†’ Query β„• 1) (q : Query β„• 3) (hQ : (Q q).source) (hq : q.source) :
                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.

                Dependency graph