Documentation

Provenance.HavingMinMax

Scan-computable HAVING provenance for MIN, MAX and PICKFIRST #

For a HAVING predicate comparing an aggregate to a constant, the possible-world semantics sums the world annotations T_U(W) over the non-empty valid worlds W ⊆ U of a group, of which there are in general exponentially many. This file shows that for the aggregates MIN, MAX and PICKFIRST – those whose validity is decided occurrence by occurrence – that sum collapses, in an absorptive commutative m-semiring, to a closed form using O(|U|) semiring operations: the provenance is obtained by a single scan over the occurrences of the group, hence in polynomial time in data complexity.

The collapse #

Everything rests on one identity, meet_family_eq: for H ⊆ G ⊆ U,

⊕_{W ⊆ G, W ∩ H ≠ ∅} T_U(W) = (𝟙 ⊖ ⊕_{x ∈ U \ G} α x) ⊗ (⊕_{i ∈ H} α i),

i.e., the provenance of “the world stays inside G and meets H” is the product of two running sums. Both hypotheses of the absorptive setting are used: ≤ follows from A_W ≤ α i ≤ ⊕_H α (absorptivity makes A decreasing under inclusion), and ≥ from upward_expansion in the universe G, transported to U by T_eq_T_of_subset and sum_monus.

Where the hypotheses are used #

Absorptivity makes A decreasing under inclusion (A_le_of_subset_absorptive) and is used in both halves. mul_sub_left_distributive is used exactly twice: in the ≤ half, to pass from T_U(W) – defined in Provenance.Having as A_W ⊖ ⊕_x A_{W ∪ {x}} – to the factored form A_W ⊗ (𝟙 ⊖ ⊕_{U∖W} α) in which the possible-world semantics is stated; and in the ≥ half, to rewrite the right-hand side as ⊕_H α ⊖ (⊕_H α ⊗ ⊕_{U∖G} α), the shape sum_monus needs. The first use is not a proof convenience: in MaxMin TVL (absorptive but not mul_sub_left_distributive) the identity is false for T as defined here – U = {1,2}, G = H = {1} and α₁ = α₂ = unknown give 𝟘 on the left and unknown on the right – because that is precisely where the two forms of the world annotation part company.

The six comparison operators then instantiate this with the right pair (G, H); e.g., MIN(t) ≥ c keeps the worlds inside G = {i | t i ≥ c}, while MIN(t) ≤ c keeps the worlds meeting H = {i | t i ≤ c}, and MIN(t) = c uses both. PICKFIRST splits the worlds according to their first occurrence and applies the identity to each fiber.

Main results #

Unlike the COUNT/SUM cases, no world enumeration is involved: the scans are closed forms, and the absorptivity hypothesis is what makes them exist (in ℕ[X], for instance, the same provenance is a product rather than a sum of annotations).

Possible-world provenance of a selection predicate #

def Having.prov {ι : Type} [DecidableEq ι] {K : Type} [CommSemiringWithMonus K] (α : ι → K) (U : Finset ι) (P : Finset ι → Prop) [DecidablePred P] :
K

The possible-world provenance, at one group, of a selection predicate P on worlds: the ⊕-sum of the world annotations T_U(W) over the non-empty worlds satisfying P, in the possible-world semantics of HAVING predicates.

Equations
Instances For
    Dependency graph

    The MIN and MAX aggregates #

    def Having.minAgg {ι V : Type} [LinearOrder V] (t : ι → V) (W : Finset ι) :

    MIN(t) over a world, as an element of WithTop V: the empty world has aggregate value ⊤ (it is excluded from the possible-world sum anyway).

    Equations
    Instances For
      Dependency graph
      def Having.maxAgg {ι V : Type} [LinearOrder V] (t : ι → V) (W : Finset ι) :

      MAX(t) over a world, as an element of WithBot V.

      Equations
      Instances For
        Dependency graph
        def Having.minScan {ι K : Type} [CommSemiringWithMonus K] {V : Type} [LinearOrder V] (α : ι → K) (U : Finset ι) (t : ι → V) (op : CompOp) (c : V) :
        K

        The MIN scan. Closed form for the provenance of MIN(t) op c: for each operator, at most two running ⊕-sums over the occurrences of the group, combined by one ⊖ and one ⊗. Computing it takes O(|U|) semiring operations, hence polynomial time in data complexity; minScan_correct proves it correct.

        Equations
        Instances For
          Dependency graph
          def Having.maxScan {ι K : Type} [CommSemiringWithMonus K] {V : Type} [LinearOrder V] (α : ι → K) (U : Finset ι) (t : ι → V) (op : CompOp) (c : V) :
          K

          The MAX scan, the mirror image of minScan; see maxScan_correct.

          Equations
          Instances For
            Dependency graph

            Provenance of the six MIN(t) op c predicates #

            Provenance of the six MAX(t) op c predicates #

            The two scans are correct #

            theorem Having.minScan_correct {ι : Type} [DecidableEq ι] {K : Type} [CommSemiringWithMonus K] {V : Type} [LinearOrder V] (h_abs : absorptive K) (h_distrib : mul_sub_left_distributive K) (α : ι → K) (U : Finset ι) (t : ι → V) (c : V) (op : CompOp) :
            (prov α U fun (W : Finset ι) => op.eval (minAgg t W) ↑c) = minScan α U t op c

            Correctness of the MIN scan. For every comparison operator, the possible-world provenance of the HAVING MIN(t) op c predicate is computed by the scan minScan.

            Dependency graph
            theorem Having.maxScan_correct {ι : Type} [DecidableEq ι] {K : Type} [CommSemiringWithMonus K] {V : Type} [LinearOrder V] (h_abs : absorptive K) (h_distrib : mul_sub_left_distributive K) (α : ι → K) (U : Finset ι) (t : ι → V) (c : V) (op : CompOp) :
            (prov α U fun (W : Finset ι) => op.eval (maxAgg t W) ↑c) = maxScan α U t op c

            Correctness of the MAX scan.

            Dependency graph

            The PICKFIRST aggregate #

            PICKFIRST is the non-commutative aggregate returning the value of the first occurrence of its input sequence. Here the occurrences are ordered by a linear order ≼ on ι (the order along which the group is enumerated), so the first occurrence of a world is its ≼-minimum.

            def Having.firstAgg {ι V : Type} [LinearOrder ι] (t : ι → V) (W : Finset ι) :

            PICKFIRST(t) over a world: the value of its ≼-first occurrence, with ⊤ for the empty world.

            Equations
            Instances For
              Dependency graph
              def Having.firstScan {ι K : Type} [CommSemiringWithMonus K] {V : Type} [LinearOrder V] [LinearOrder ι] (α : ι → K) (U : Finset ι) (t : ι → V) (op : CompOp) (c : V) :
              K

              The PICKFIRST scan. Closed form for the provenance of PICKFIRST(t) op c: one term per satisfying occurrence, each combining the annotation of that occurrence with the running sum of the annotations of the occurrences that precede it.

              Equations
              Instances For
                Dependency graph
                theorem Having.firstScan_correct {ι : Type} [DecidableEq ι] {K : Type} [CommSemiringWithMonus K] {V : Type} [LinearOrder V] [LinearOrder ι] (h_abs : absorptive K) (h_distrib : mul_sub_left_distributive K) (α : ι → K) (U : Finset ι) (t : ι → V) (c : V) (op : CompOp) :
                (prov α U fun (W : Finset ι) => op.eval (firstAgg t W) ↑c) = firstScan α U t op c

                Correctness of the PICKFIRST scan. The possible-world provenance of the HAVING PICKFIRST(t) op c predicate is computed by the scan firstScan: the worlds are partitioned according to their first occurrence.

                Dependency graph