Graded extensionality #
In which m-semirings does the annotation of a tuple depend on the query
alone and not on its spelling? Call K extensional for a class of
queries when any two queries of the class with regular output columns
and the same plain semantics on every instance give, on every
K-instance, the same K-relation after collapsing the copies of each
tuple by ⊕ – the K-relation of Green, Karvounarakis and Tannen
(AnnotatedRelation.annSum). The answer is graded along the first levels
of the chain of fragments of the sql-semantics paper, and the grading says
which construct asks for which axiom:
- (a) every commutative m-semiring is extensional for
F₀– projection, selection, product, apply, union and the constant relations (extensional_level0); and on the classical layer, where the evaluator is defined over every m-semiring, the commutativity of⊗is what a swapped product forces (mul_comm_of_extensional_swap); - (b)
Kis extensional forF₁–F₀with duplicate elimination and the semijoin, SQL'sEXISTSandIN– iff it is a lattice m-semiring:⊗idempotent andKabsorptive, so that(K, ⊕, ⊗)is a bounded distributive lattice (extensional_level1_iff); - (c)
Kis extensional forF₂– with the difference and the antijoin,EXCEPT,NOT EXISTSandNOT IN– iff it is a Boolean m-semiring, whatever itsδ(extensional_level2_iff); - (d)
Kis extensional for the whole recursion-free algebra – grouping, windows, nested aggregation included – iff it is a Boolean m-semiring whoseδis the identity (extensional_tame_iff).
Each axiom is forced by one pair of equivalent queries over a one-tuple
instance, written with the constructs of the level that forces it: the
two sides annotate the one output tuple by a and a ⊕ a, a and
a ⊗ a, a and a ⊕ a ⊗ b, 𝟘 and a ⊗ (𝟙 ⊖ a), a and δ(a). Conversely,
on F₀ a copy of an output tuple is annotated by a product of the
annotations it is derived from; over ℕ[K], the universal commutative
semiring, two queries with the same multiplicities on every instance
give each tuple the same polynomial, by a polynomial identity over ℕ
(FragQueryIn.semPlain_unfold, MvPolynomial.funext_set), and the
universal homomorphism carries that to K. Above F₀, a lattice
m-semiring has enough homomorphisms onto 𝔹 to separate its elements
(IsLatticeSemiring.eq_of_forall_point); those of a Boolean m-semiring
preserve the monus and, when δ is the identity, δ; and at each such
point the annotated semantics is the plain semantics of the support
(FragQueryIn.mem_support_sem, AggQueryIn.genRandomWorld_evaluate).
The levels F₀, F₁ and F₂ are the syntax FragQueryIn of
Provenance.FragQuery, read in the general syntax through
FragQueryIn.toAgg; the whole algebra is the general syntax under the
hygiene the metatheory asks of a query (AggQueryIn.Tame), without
recursion, so that nothing has to settle.
Extensionality #
K is extensional for the queries satisfying F: two such queries
with the same plain semantics on every instance collapse, on every
K-instance, to the same K-relation.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
The queries of F₀, in the general syntax: the translations of
the level-0 queries of the fragment syntax.
Equations
- AggQueryIn.InLevel0 q = ∃ (e : FragQuery T n), FragQueryIn.level0 e ∧ FragQueryIn.toAgg e = q
Instances For
Dependency graph
The queries of F₁.
Equations
- AggQueryIn.InLevel1 q = ∃ (e : FragQuery T n), FragQueryIn.level1 e ∧ FragQueryIn.toAgg e = q
Instances For
Dependency graph
The queries of F₂: every translation of the fragment syntax.
Equations
- AggQueryIn.InLevel2 q = ∃ (e : FragQuery T n), FragQueryIn.toAgg e = q
Instances For
Dependency graph
A tame query of the whole algebra: recursion-free, and with the
hygiene the metatheory asks – no provenance sum, hygienic, well-kinded,
with distinct labels, recorded reads, source columns and frames
containing their row. These are the hypotheses of the homomorphism
commutation (AggQueryIn.evaluateAnnotated_hom) and of the random-world
commutation (AggQueryIn.genRandomWorld_evaluate) of the general
evaluator.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
The levels are nested.
Dependency graph
Dependency graph
Extensionality is antitone in the class of queries.
Dependency graph
The plain equivalence of translated queries #
Two translated queries are plainly equivalent exactly when their closed-form plain semantics agree on every instance.
Dependency graph
The collapsed annotations of a translated query, in closed form.
Dependency graph
(a) Every commutative m-semiring is extensional for F₀ #
The argument is in ℕ[K], the polynomial semiring over the
annotations themselves, read as indeterminates: the instance d is the
image of the instance d₀ carrying X a where d carries a, under the
universal homomorphism sending X a to a. Over d₀ the collapsed
annotation of a tuple is a polynomial, and evaluating it at a valuation
n : K → ℕ is the multiplicity of the tuple on the plain instance in
which each copy carrying a is repeated n a times. Two queries with
the same plain semantics everywhere have the same multiplicities, so the
two polynomials agree on all of ℕ^K, and a polynomial identity
settles it.
Every commutative m-semiring is extensional for F₀.
Dependency graph
The forcing pairs #
Each axiom is forced by one pair of queries with the same plain
semantics on every instance, read on a one-tuple instance: R holding
![x] annotated a.
The instance with one relation R holding one tuple, annotated a.
Instances For
Dependency graph
The instance with two relations R and S, each holding the one
tuple ![x], annotated a and b.
Instances For
Dependency graph
(a) on the classical layer: the commutativity of ⊗ #
The general evaluator is defined over commutative m-semirings, so the
commutativity of ⊗ is not an axiom it can force. The classical evaluator
Query.evaluateAnnotated is defined over every m-semiring, and there the
swapped product does force it: Π₂,₁(R × S) and S × R have the same
plain semantics on every instance, and annotate the one tuple of a
two-relation instance by a ⊗ b and b ⊗ a.
Π₂,₁(R × S), in the classical syntax.
Instances For
Dependency graph
S × R.
Instances For
Dependency graph
Dependency graph
Dependency graph
The K-relation an annotated relation collapses to, over any
m-semiring: the ⊕-sum of the annotations of the copies of a tuple. On a
commutative m-semiring it is AnnotatedRelation.annSum.
Equations
- r.collapse u = (Multiset.map Prod.snd (Multiset.filter (fun (p : AnnotatedTuple T K₀ n) => p.1 = u) r)).sum
Instances For
Dependency graph
On a commutative m-semiring the collapse is annSum.
Dependency graph
The two sides of the pair have the same plain semantics on every instance.
Dependency graph
⊗ is commutative where the swapped product is extensional: an
m-semiring over which Π₂,₁(R × S) and S × R collapse to the same
annotations on every instance has a commutative multiplication.
Dependency graph
The base relation R of arity 1, in any context.
Equations
- FragQueryIn.relRIn c = FragQueryIn.Rel 1 "R"
Instances For
Dependency graph
The base relation R of arity 1.
Equations
- FragQueryIn.relR = FragQueryIn.Rel 1 "R"
Instances For
Dependency graph
The base relation S of arity 1.
Equations
- FragQueryIn.relS = FragQueryIn.Rel 1 "S"
Instances For
Dependency graph
The projection onto the first column of a relation of arity 2.
Instances For
Dependency graph
The pair forcing a ⊕ a = a: ε(R) against ε(R ⊎ R).
Instances For
Dependency graph
Instances For
Dependency graph
The pair forcing a ⊗ a = a: ε(R) against ε(Π₁(R × R)).
Instances For
Dependency graph
Equations
Instances For
Dependency graph
The pair forcing a ⊕ a ⊗ b = a, and with it 𝟙 ⊕ b = 𝟙: ε(R)
against ε(R ⊎ Π₁(R × S)).
Instances For
Dependency graph
Equations
Instances For
Dependency graph
The predicate matching the current row with a row of the subquery on
their one column: R.x IS NOT DISTINCT FROM S.x.
Equations
Instances For
Dependency graph
The pair forcing a ⊗ (𝟙 ⊖ a) = 𝟘: the antijoin of R with itself
on its column, WHERE NOT EXISTS, against the empty query.
Equations
- FragQueryIn.pairExcl₁ cnt hc = FragQueryIn.Antijoin cnt hc FragQueryIn.keyMatch FragQueryIn.relR (FragQueryIn.relRIn (1 + 0))
Instances For
Dependency graph
Instances For
Dependency graph
What the pairs annotate on the one-tuple instance #
The pairs are plainly equivalent #
What extensionality forces #
⊕ is idempotent where K is extensional for a class holding
ε(R) and ε(R ⊎ R).
Dependency graph
⊗ is idempotent where K is extensional for a class holding
ε(R) and ε(Π₁(R × R)).
Dependency graph
K is absorptive where it is extensional for a class holding
ε(R) and ε(R ⊎ Π₁(R × S)): the pair gives a ⊕ a ⊗ b = a, and
𝟙 ⊕ b = 𝟙 is its instance at a = 𝟙.
Dependency graph
K is exclusive where it is extensional for a class holding the
antijoin of R with itself and the empty query.
Dependency graph
A counting aggregate, for the antijoin pair: nonzero where the
sequence holds a non-null value, 𝟘 otherwise.
Equations
- SeqAggFunc.existsNonNull L = if (L.any fun (v : T) => !ValueType.isNull v) = true then ValueType.nonzero else 0
Instances For
Dependency graph
Dependency graph
(b) and (c): the converses, through the points #
Over a lattice m-semiring, two translated queries with the same
plain semantics collapse to the same annotations, provided the
translation reaches their semantics and the points pass through them.
The annotation of a tuple is determined by its images at the points of
K, and each image is a plain evaluation of the support.
Dependency graph
(b) K is extensional for F₁ iff it is a lattice m-semiring.
Dependency graph
(c) K is extensional for F₂ iff it is a Boolean m-semiring,
whatever its δ.
Dependency graph
(d) The whole recursion-free algebra #
The pair forcing δ(a) = a is ε(R) against Π₁(γ₁[count](R)), a
grouping that aggregates with its aggregate column projected away: the
first annotates the one tuple by a, the second by the group's
existence factor δ(a). Conversely, when K is Boolean with δ the
identity, every point of K is an m-semiring homomorphism onto 𝔹,
the general evaluator commutes with it, and over 𝔹 the annotated
evaluation is the plain evaluation of the support
(AggQueryIn.genRandomWorld_evaluate, read through the constant
embedding of 𝔹 into 𝔹[∅]).
The kinds of a grouping of arity-one key with one aggregate.
Equations
- gammaKinds = Fin.append (fun (x : Fin 1) => ColKind.reg) fun (x : Fin 1) => ColKind.agg
Instances For
Dependency graph
The projection reading the key column of such a grouping.
Equations
Instances For
Dependency graph
The grouping of the forcing pair: γ₁[count](R), with any
sequence aggregate for the count, its aggregate column projected away.
Equations
- pairDelta₂Raw cnt = AggQueryIn.Proj projKey (AggQueryIn.Gamma ![0] ![TermIn.const ValueType.nonzero] ![cnt] (AggQueryIn.Rel 1 "R"))
Instances For
Dependency graph
The same, with its kinds read as all regular.
Equations
- pairDelta₂ cnt = AggQueryIn.castKind ⋯ (pairDelta₂Raw cnt)
Instances For
Dependency graph
Duplicate elimination of R, the other side of the pair.
Equations
- pairDelta₁ = (AggQueryIn.Rel 1 "R").Dedup
Instances For
Dependency graph
δ is the identity where K is extensional for a class holding
ε(R) and Π₁(γ₁[count](R)).
Dependency graph
Tameness of the forcing pairs #
The converse: points are m-semiring homomorphisms #
A point of a Boolean m-semiring with δ the identity, into
𝔹[X]: the point followed by the constant embedding.
Equations
Instances For
Dependency graph
(d) K is extensional for the whole recursion-free algebra iff it
is a Boolean m-semiring whose δ is the identity.