Monotone HAVING conditions: absorptivity suffices #
The join-based rewriting of a HAVING condition is correct in every
absorptive commutative m-semiring – distributivity of ⊗ over ⊖ not
required – as soon as the condition is monotone: a Boolean combination,
by ∧ and ∨ only, of atoms whose validity is preserved when occurrences
are added to the group. The atoms covered are COUNT(*) ≥ C, COUNT(*) > C
(Query.joinCount_monotone_correct, Provenance.HavingQueryCorrectness),
and the existential comparisons MIN(t) ≤ c, MIN(t) < c,
MAX(t) ≥ c, MAX(t) > c, which hold in a world iff it contains a
qualifying occurrence (Having.Existential).
Existential atoms are rewritten as
ε(Π_{#0}(σ_{t op c}(q)))(existentialQuery): per group key, the⊕-sum of the annotations of the qualifying occurrences, which is the fused predicate provenance byHaving.havingProv_existential(existential_perKey); padded, the rewriting is the key-projected fused site as a multiset (existential_site_rewrite, with the four instancesminLe_site_rewrite,minLt_site_rewrite,maxGe_site_rewrite,maxGt_site_rewrite).Boolean closure. A conjunction is rewritten as the join of the two rewritings on the group key (
keyJoin, which multiplies the per-key annotations,keyJoin_perKeySum) and a disjunction as their set union (keyUnion, which adds them,keyUnion_perKeySum): exactly how the fused semanticsHavingPred.provinterprets∧and∨. The syntaxMonoCondof monotone conditions over the token columns of a grouping comes with its compositional rewritingMonoCond.rewrite, its readingMonoCond.toHavingPredas a Boolean combination of fused comparisons, and its readingMonoCond.toGenPredas a generalized selection predicate. The padded rewriting computesHavingPred.provfor every monotone condition (padded_correct). The general evaluator, however, reads a combination of comparisons of one group in one world of that group (GenPredIn.predsemJ), which is not⊗/⊕of the comparisons' provenances; the two agree on one comparison (MonoCond.isAtom,MonoCond.toGenPred_predsemJ). SoMonoCond.site_evaluateAnnotated, the closed form of the fused siteσ_ψ(γ_{#0}[ts : fs](q))in the general evaluator, andMonoCond.site_rewrite, the site substitution, are stated for a single comparison: there the key-projected fused site and the padded rewriting are the same multiset of annotated tuples, in every absorptive commutative m-semiring.
The base query has the (key, value, identifier) schema of
Provenance.HavingQueryCorrectness, with the group key in column #0.
Comparison atoms as selection predicates #
The Boolean term t op s.
Equations
- BoolTerm.ofCompOp CompOp.eq t s = BoolTerm.EQ t s
- BoolTerm.ofCompOp CompOp.ne t s = BoolTerm.NE t s
- BoolTerm.ofCompOp CompOp.lt t s = BoolTerm.LT t s
- BoolTerm.ofCompOp CompOp.le t s = BoolTerm.LE t s
- BoolTerm.ofCompOp CompOp.gt t s = BoolTerm.GT t s
- BoolTerm.ofCompOp CompOp.ge t s = BoolTerm.GE t s
- BoolTerm.ofCompOp CompOp.syneq t s = BoolTerm.SYNEQ t s
- BoolTerm.ofCompOp CompOp.synne t s = BoolTerm.SYNNE t s
Instances For
Dependency graph
Existential atoms: ε(Π_{#0}(σ_{t op c}(q))) #
The selection predicate t op c of an existential atom.
Equations
- atomSel t op c = Selection.BT (BoolTerm.ofCompOp op t (TermIn.const c))
Instances For
Dependency graph
The rewriting ε(Π_{#0}(σ_{t op c}(q))) of an existential comparison
f(t) op c: the group keys of the qualifying occurrences, duplicate-
eliminated.
Instances For
Dependency graph
Dependency graph
Existential atoms, per key. In an absorptive commutative
m-semiring, the existential rewriting gives every group key the fused
f(t) op c predicate provenance of its group, for any existential
comparison (MIN with ≤/<, MAX with ≥/>). No distributivity of
⊗ over ⊖ is assumed (Having.havingProv_existential).
Dependency graph
Site substitution for existential atoms. In every absorptive
commutative m-semiring, the key-projected fused HAVING f(t) op c site
and the padded rewriting ε(Π_{#0}(σ_{t op c}(q))) evaluate to the same
multiset of annotated tuples, for any existential comparison.
Dependency graph
MIN(t) ≤ c.
Dependency graph
MIN(t) < c.
Dependency graph
MAX(t) ≥ c.
Dependency graph
MAX(t) > c.
Dependency graph
Boolean closure: join on the group key and set union #
A conjunction of conditions is rewritten as the join of the two rewritings
on the group key, ε(Π_{#0}(σ_{#0 = #1}(Q₁ × Q₂))), and a disjunction as
their set union ε(Q₁ ⊎ Q₂). Per key, the join multiplies and the union
adds the annotations, which is exactly how the fused semantics
(HavingPred.prov) interprets ∧ and ∨.
The key-equality predicate #0 = #1 on a pair of one-column rows.
Equations
Instances For
Dependency graph
The projection of a pair of one-column rows to its first column.
Instances For
Dependency graph
The key-equality selection over the product, σ_{#0 = #1}(Q₁ × Q₂).
Equations
- keyJoinInner Q₁ Q₂ = σ joinSel (Q₁.Prod Q₂)
Instances For
Dependency graph
Join on the group key, ε(Π_{#0}(σ_{#0 = #1}(Q₁ × Q₂))).
Instances For
Dependency graph
Set union, ε(Q₁ ⊎ Q₂).
Instances For
Dependency graph
Dependency graph
Dependency graph
The row of a product: appended data parts, multiplied annotations.
Instances For
Dependency graph
Join on the key multiplies the per-key annotations.
Dependency graph
Set union adds the per-key annotations.
Dependency graph
Monotone conditions and their compositional rewriting #
Monotone HAVING conditions over the aggregate columns of a grouping:
COUNT(*) ≥ C + 1 and COUNT(*) > C + 1 on the token column l, an
existential comparison f(t) op c on the token column l, and
conjunctions and disjunctions. Negation is excluded: it flips
monotonicity.
- countGe {n₂ : ℕ} (l : Fin n₂) (C : ℕ) : MonoCond n₂
- countGt {n₂ : ℕ} (l : Fin n₂) (C : ℕ) : MonoCond n₂
- exist {n₂ : ℕ} (l : Fin n₂) (op : CompOp) (c : ℕ) : MonoCond n₂
- and {n₂ : ℕ} (ψ₁ ψ₂ : MonoCond n₂) : MonoCond n₂
- or {n₂ : ℕ} (ψ₁ ψ₂ : MonoCond n₂) : MonoCond n₂
Instances For
Dependency graph
Well-formedness with respect to the aggregates fs of the grouping:
the COUNT(*) atoms sit on COUNT(*) columns and the existential atoms
on existential aggregate/operator pairs (MIN with ≤/<, MAX with
≥/>, see Having.Existential).
Equations
- MonoCond.WF fs (MonoCond.countGe l C) = (fs l = SeqAggFunc.count)
- MonoCond.WF fs (MonoCond.countGt l C) = (fs l = SeqAggFunc.count)
- MonoCond.WF fs (MonoCond.exist l op c) = Having.Existential (fs l) op
- MonoCond.WF fs (ψ₁.and ψ₂) = (MonoCond.WF fs ψ₁ ∧ MonoCond.WF fs ψ₂)
- MonoCond.WF fs (ψ₁.or ψ₂) = (MonoCond.WF fs ψ₁ ∧ MonoCond.WF fs ψ₂)
Instances For
Dependency graph
The condition as a Boolean combination of fused aggregate comparisons,
whose provenance is HavingPred.prov (∧ ↦ ⊗, ∨ ↦ ⊕).
Equations
- MonoCond.toHavingPred ts fs (MonoCond.countGe l C) = HavingPred.cmp (ts l) (fs l) CompOp.ge (TermIn.const (C + 1))
- MonoCond.toHavingPred ts fs (MonoCond.countGt l C) = HavingPred.cmp (ts l) (fs l) CompOp.gt (TermIn.const (C + 1))
- MonoCond.toHavingPred ts fs (MonoCond.exist l op c) = HavingPred.cmp (ts l) (fs l) op (TermIn.const c)
- MonoCond.toHavingPred ts fs (ψ₁.and ψ₂) = (MonoCond.toHavingPred ts fs ψ₁).and (MonoCond.toHavingPred ts fs ψ₂)
- MonoCond.toHavingPred ts fs (ψ₁.or ψ₂) = (MonoCond.toHavingPred ts fs ψ₁).or (MonoCond.toHavingPred ts fs ψ₂)
Instances For
Dependency graph
The compositional positive rewriting Q_ψ: COUNT(*) atoms become
the join chains Q₂^{≥ C}, existential atoms ε(Π_{#0}(σ_{t op c}(q))),
a conjunction the join of the two rewritings on the group key, and a
disjunction their set union.
Equations
- MonoCond.rewrite ts (MonoCond.countGe l C) x✝ = joinChainQuery x✝ C
- MonoCond.rewrite ts (MonoCond.countGt l C) x✝ = joinChainQuery x✝ (C + 1)
- MonoCond.rewrite ts (MonoCond.exist l op c) x✝ = existentialQuery (ts l) op c x✝
- MonoCond.rewrite ts (ψ₁.and ψ₂) x✝ = keyJoin (MonoCond.rewrite ts ψ₁ x✝) (MonoCond.rewrite ts ψ₂ x✝)
- MonoCond.rewrite ts (ψ₁.or ψ₂) x✝ = keyUnion (MonoCond.rewrite ts ψ₁ x✝) (MonoCond.rewrite ts ψ₂ x✝)
Instances For
Dependency graph
Dependency graph
The fused site of a compound condition, in the general evaluator #
The condition as a generalized selection predicate over the output of
Gamma: each atom compares its token column against a constant
(GenPredIn.fusedCmp), and ∧/∨ are the Boolean connectives of
GenPred.
Equations
- (MonoCond.countGe l C).toGenPred = GenPredIn.fusedCmp CompOp.ge l (TermIn.const (C + 1))
- (MonoCond.countGt l C).toGenPred = GenPredIn.fusedCmp CompOp.gt l (TermIn.const (C + 1))
- (MonoCond.exist l op c).toGenPred = GenPredIn.fusedCmp op l (TermIn.const c)
- (ψ₁.and ψ₂).toGenPred = GenPredIn.and ψ₁.toGenPred ψ₂.toGenPred
- (ψ₁.or ψ₂).toGenPred = GenPredIn.or ψ₁.toGenPred ψ₂.toGenPred
Instances For
Dependency graph
A single comparison. The general evaluator reads a combination of
comparisons of one group in one world of that group
(GenPredIn.predsemJ), while HavingPred.prov reads ∧ as ⊗ and ∨
as ⊕; the two agree on one comparison (toGenPred_predsemJ), and that
is where the fused site is related to the evaluator.
Equations
Instances For
Dependency graph
The fused site σ_ψ(γ_{#0}[ts : fs](qg)) of a monotone condition, as a
general query.
Equations
- MonoCond.site ts fs ψ qg = AggQueryIn.Sel ψ.toGenPred (AggQueryIn.Gamma keyIdx ts fs qg) ⋯
Instances For
Dependency graph
On one comparison the evaluator's joint reading is the structural one.
Dependency graph
Closed form of the fused site of a monotone condition. The general
evaluator produces one row per group key of the subquery, carrying the
key followed by the whole-group aggregate values and annotated by the
fused provenance HavingPred.prov of the condition on the group's
occurrence sequence: the pending group factor introduced by Gamma is
superseded by the compared tokens (every atom compares a token of that
very group). Stated for one comparison (MonoCond.isAtom), where the
evaluator's joint reading of the condition is its fused provenance.
Dependency graph
Site substitution for monotone conditions: absorptivity suffices.
In every absorptive commutative m-semiring – distributivity of ⊗ over
⊖ not required – the key-projected fused site σ_ψ(γ_{#0}[ts : fs](q))
of a well-formed comparison ψ and the padded compositional
rewriting Q_ψ evaluate to the same multiset of annotated tuples: the
rewriting can be substituted for the key-projected fused operator inside
any surrounding query. The sole hypothesis on the instance is the global
row-distinctness of the base query's output (the occurrence identifiers
of the COUNT(*) join chains).