The first levels of the chain of fragments, as a syntax of their own #
The extensionality theorem of Provenance.Extensionality grades the
m-semirings along the first levels of the chain of SQL fragments of the
sql-semantics paper: F₀ (projection, selection, product, apply, union,
the constant relations), F₁ (F₀ with duplicate elimination, EXISTS
and IN) and F₂ (F₁ with EXCEPT, NOT EXISTS and NOT IN); the
projections and selections carry the library's terms, so the level F₃
of the paper, which adds expressions, is F₂ here as well. Each
construct of these levels is an operator of the kind-indexed syntax, or
a query it abbreviates (Provenance.Derived); but the levels are not
sets of operator classes – EXISTS is an apply, a scalar count and a
selection on an aggregate atom, which AggQueryIn.usesOnly charges to
three classes – so they are given here as a syntax of their own,
FragQueryIn T c n, with a translation FragQueryIn.toAgg into the
general syntax and the levels as predicates on it (FragQueryIn.level0,
FragQueryIn.level1; F₂ is the whole syntax).
Every output column is regular, so the translation's annotated
evaluation produces plain annotated tuples, and the file gives it in
closed form: FragQueryIn.sem is the annotated semantics operator by
operator – multiset operations and the m-semiring's ⊕, ⊗ and ⊖ – and
FragQueryIn.toAgg_evaluateAnnotated says the general evaluator computes
it. The same for the plain semantics, FragQueryIn.semPlain and
FragQueryIn.toAgg_evaluatePlain. The one closed form that costs a
hypothesis is the semijoin's, α ⊗ ⊕β in an absorptive m-semiring
(AggValue.predProvScalar_count_ne_zero), which is why the bridge asks
absorptivity of a query with a semijoin and nothing of the others.
An EXISTS or IN counts, in SQL's scalar convention, the rows of its
subquery that match the current row; the count is over a constant that is
not null (ValueType.nonzero), so that it is 𝟘 exactly where nothing
matches, and any aggregate that counts (SeqAggFunc.Counts) may do the
counting.
The syntax of the first levels of the chain. The context c is
the arity of the row an apply's right side reads, as in AggQueryIn;
every output column is regular.
- Rel
{T : Type}
[ValueType T]
{c : ℕ}
(n : ℕ)
: String → FragQueryIn T c n
A base relation.
- Empty
{T : Type}
[ValueType T]
{c : ℕ}
: FragQueryIn T c 0
The empty relation of arity
0. - Unit
{T : Type}
[ValueType T]
{c : ℕ}
: FragQueryIn T c 0
The unit: one empty tuple, annotated
𝟙. A row of constants is a projection of it, andVALUESa union of such rows. - Proj
{T : Type}
[ValueType T]
{c n m : ℕ}
(ts : Tuple (TermGIn T c (ColKind.allReg n)) m)
: FragQueryIn T c n → FragQueryIn T c m
Generalized projection, every column a term.
- Sel
{T : Type}
[ValueType T]
{c n : ℕ}
(φ : GenPredIn T c (ColKind.allReg n))
: FragQueryIn T c n → FragQueryIn T c n
Selection by a predicate on regular columns.
- Prod
{T : Type}
[ValueType T]
{c n₁ n₂ : ℕ}
: FragQueryIn T c n₁ → FragQueryIn T c n₂ → FragQueryIn T c (n₁ + n₂)
Cartesian product.
- Apply
{T : Type}
[ValueType T]
{c n₁ n₂ : ℕ}
: FragQueryIn T c n₁ → FragQueryIn T (n₁ + c) n₂ → FragQueryIn T c (n₁ + n₂)
Apply, SQL's
LATERAL: the right side is read once per row of the left, in a context extended by that row. - Sum
{T : Type}
[ValueType T]
{c n : ℕ}
: FragQueryIn T c n → FragQueryIn T c n → FragQueryIn T c n
Union (all).
- Dedup
{T : Type}
[ValueType T]
{c n : ℕ}
: FragQueryIn T c n → FragQueryIn T c n
Duplicate elimination.
- Diff
{T : Type}
[ValueType T]
{c n : ℕ}
: FragQueryIn T c n → FragQueryIn T c n → FragQueryIn T c n
Difference: the rows of the left side with no equal row on the right, copies kept – the
NOT INdifference on whole rows (t ∉ r₂), notEXCEPT ALL, which subtracts multiplicities. - Semijoin
{T : Type}
[ValueType T]
{c k l : ℕ}
(cnt : SeqAggFunc T)
: cnt.Counts →
(φ : GenPredIn T (k + c) (ColKind.allReg l)) → FragQueryIn T c k → FragQueryIn T (k + c) l → FragQueryIn T c k
Semijoin,
WHERE EXISTSandIN: the rows of the left side that the predicate matches with some row of the right side, read in the context of the left row. The aggregate counts the matches. - Antijoin
{T : Type}
[ValueType T]
{c k l : ℕ}
(cnt : SeqAggFunc T)
: cnt.Counts →
(φ : GenPredIn T (k + c) (ColKind.allReg l)) → FragQueryIn T c k → FragQueryIn T (k + c) l → FragQueryIn T c k
Antijoin,
WHERE NOT EXISTSandNOT IN: the rows of the left side that the predicate matches with no row of the right side.
Instances For
Dependency graph
A closed query of the fragment syntax.
Equations
- FragQuery T n = FragQueryIn T 0 n
Instances For
Dependency graph
A predicate over regular columns has no aggregate atom: an aggregate atom names a column of aggregate kind, and there is none.
Dependency graph
The levels #
Level F₀: no duplicate elimination, no difference, no semijoin
and no antijoin.
Equations
- (FragQueryIn.Rel x✝ a).level0 = True
- FragQueryIn.Empty.level0 = True
- FragQueryIn.Unit.level0 = True
- (FragQueryIn.Proj ts q).level0 = q.level0
- (FragQueryIn.Sel φ q).level0 = q.level0
- (q₁.Prod q₂).level0 = (q₁.level0 ∧ q₂.level0)
- (q₁.Apply q₂).level0 = (q₁.level0 ∧ q₂.level0)
- (q₁.Sum q₂).level0 = (q₁.level0 ∧ q₂.level0)
- a.Dedup.level0 = False
- (a.Diff a_1).level0 = False
- (FragQueryIn.Semijoin cnt a φ a_1 a_2).level0 = False
- (FragQueryIn.Antijoin cnt a φ a_1 a_2).level0 = False
Instances For
Dependency graph
Level F₁: F₀ with duplicate elimination and the semijoin, and
without the negated forms.
Equations
- (FragQueryIn.Rel x✝ a).level1 = True
- FragQueryIn.Empty.level1 = True
- FragQueryIn.Unit.level1 = True
- (FragQueryIn.Proj ts q).level1 = q.level1
- (FragQueryIn.Sel φ q).level1 = q.level1
- (q₁.Prod q₂).level1 = (q₁.level1 ∧ q₂.level1)
- (q₁.Apply q₂).level1 = (q₁.level1 ∧ q₂.level1)
- (q₁.Sum q₂).level1 = (q₁.level1 ∧ q₂.level1)
- a.Dedup.level1 = a.level1
- (a.Diff a_1).level1 = False
- (FragQueryIn.Semijoin cnt a φ a_1 a_2).level1 = (a_1.level1 ∧ a_2.level1)
- (FragQueryIn.Antijoin cnt a φ a_1 a_2).level1 = False
Instances For
Dependency graph
Whether a query has a semijoin somewhere: the one construct whose closed form asks absorptivity of the m-semiring.
Equations
- (FragQueryIn.Rel x✝ a).hasSemijoin = False
- FragQueryIn.Empty.hasSemijoin = False
- FragQueryIn.Unit.hasSemijoin = False
- (FragQueryIn.Proj ts q).hasSemijoin = q.hasSemijoin
- (FragQueryIn.Sel φ q).hasSemijoin = q.hasSemijoin
- (q₁.Prod q₂).hasSemijoin = (q₁.hasSemijoin ∨ q₂.hasSemijoin)
- (q₁.Apply q₂).hasSemijoin = (q₁.hasSemijoin ∨ q₂.hasSemijoin)
- (q₁.Sum q₂).hasSemijoin = (q₁.hasSemijoin ∨ q₂.hasSemijoin)
- a.Dedup.hasSemijoin = a.hasSemijoin
- (a.Diff a_1).hasSemijoin = (a.hasSemijoin ∨ a_1.hasSemijoin)
- (FragQueryIn.Semijoin cnt a φ a_1 a_2).hasSemijoin = True
- (FragQueryIn.Antijoin cnt a φ a_1 a_2).hasSemijoin = (a_1.hasSemijoin ∨ a_2.hasSemijoin)
Instances For
Dependency graph
A query of F₀ has no semijoin.
Dependency graph
F₀ ⊆ F₁.
Dependency graph
The two semantics, in closed form #
The rows of the right side of a semijoin that match a left row u:
the right side read in the context u extended by the outer one, cut by
the predicate.
Equations
- FragQueryIn.matchesAnn φ S d γ u = Multiset.filter (fun (p : AnnotatedTuple T K l) => φ.holdsPlain p.1 (Fin.append u γ)) (S d (Fin.append u γ))
Instances For
Dependency graph
The annotated semantics, operator by operator. A duplicate
elimination sums the annotations of the copies of a tuple, a difference
subtracts from each copy on the left the sum of the copies on the right,
a semijoin multiplies each left row by the sum of the annotations of its
matches and an antijoin by 𝟙 ⊖ that sum.
Equations
- One or more equations did not get rendered due to their size.
- (FragQueryIn.Rel x✝² s).sem x✝¹ x✝ = (AnnotatedDatabase.find x✝² s x✝¹).getD 0
- FragQueryIn.Empty.sem x✝¹ x✝ = 0
- FragQueryIn.Unit.sem x✝¹ x✝ = {(fun (j : Fin 0) => j.elim0, 1)}
- (FragQueryIn.Proj ts q).sem x✝¹ x✝ = Multiset.map (fun (p : AnnotatedTuple T K n) => (fun (j : Fin x✝²) => (ts j).evalPlain p.1 x✝, p.2)) (q.sem x✝¹ x✝)
- (FragQueryIn.Sel φ q).sem x✝¹ x✝ = Multiset.filter (fun (p : AnnotatedTuple T K x✝²) => φ.holdsPlain p.1 x✝) (q.sem x✝¹ x✝)
- (q₁.Sum q₂).sem x✝¹ x✝ = q₁.sem x✝¹ x✝ + q₂.sem x✝¹ x✝
- q.Dedup.sem x✝¹ x✝ = Multiset.map (fun (u : Tuple T x✝²) => (u, (q.sem x✝¹ x✝).annSum u)) (Multiset.map Prod.fst (q.sem x✝¹ x✝)).dedup
- (q₁.Diff q₂).sem x✝¹ x✝ = Multiset.map (fun (p : AnnotatedTuple T K x✝²) => (p.1, p.2 - (q₂.sem x✝¹ x✝).annSum p.1)) (q₁.sem x✝¹ x✝)
- (FragQueryIn.Semijoin cnt a φ q₁ q₂).sem x✝¹ x✝ = Multiset.map (fun (p : AnnotatedTuple T K x✝²) => (p.1, p.2 * (FragQueryIn.matchesAnn φ q₂.sem x✝¹ x✝ p.1).annTotal)) (q₁.sem x✝¹ x✝)
- (FragQueryIn.Antijoin cnt a φ q₁ q₂).sem x✝¹ x✝ = Multiset.map (fun (p : AnnotatedTuple T K x✝²) => (p.1, p.2 * (1 - (FragQueryIn.matchesAnn φ q₂.sem x✝¹ x✝ p.1).annTotal))) (q₁.sem x✝¹ x✝)
Instances For
Dependency graph
The rows of the right side of a semijoin that match a left row, in the plain semantics.
Equations
- FragQueryIn.matchesPlain φ S D γ u = Multiset.filter (fun (v : Tuple T l) => φ.holdsPlain v (Fin.append u γ)) (S D (Fin.append u γ))
Instances For
Dependency graph
The plain semantics, operator by operator.
Equations
- One or more equations did not get rendered due to their size.
- (FragQueryIn.Rel x✝² s).semPlain x✝¹ x✝ = (Database.find x✝² s x✝¹).getD 0
- FragQueryIn.Empty.semPlain x✝¹ x✝ = 0
- FragQueryIn.Unit.semPlain x✝¹ x✝ = {fun (j : Fin 0) => j.elim0}
- (FragQueryIn.Proj ts q).semPlain x✝¹ x✝ = Multiset.map (fun (u : Tuple T n) (j : Fin x✝²) => (ts j).evalPlain u x✝) (q.semPlain x✝¹ x✝)
- (FragQueryIn.Sel φ q).semPlain x✝¹ x✝ = Multiset.filter (fun (u : Tuple T x✝²) => φ.holdsPlain u x✝) (q.semPlain x✝¹ x✝)
- (q₁.Prod q₂).semPlain x✝¹ x✝ = Multiset.map (fun (xy : Tuple T n₁ × Tuple T n₂) => Fin.append xy.1 xy.2) (Multiset.product (q₁.semPlain x✝¹ x✝) (q₂.semPlain x✝¹ x✝))
- (q₁.Apply q₂).semPlain x✝¹ x✝ = Multiset.bind (q₁.semPlain x✝¹ x✝) fun (u : Tuple T n₁) => Multiset.map (fun (v : Fin n₂ → T) => Fin.append u v) (q₂.semPlain x✝¹ (Fin.append u x✝))
- (q₁.Sum q₂).semPlain x✝¹ x✝ = q₁.semPlain x✝¹ x✝ + q₂.semPlain x✝¹ x✝
- q.Dedup.semPlain x✝¹ x✝ = Multiset.dedup (q.semPlain x✝¹ x✝)
- (q₁.Diff q₂).semPlain x✝¹ x✝ = Multiset.filter (fun (u : Tuple T x✝²) => u ∉ have this := q₂.semPlain x✝¹ x✝; this) (q₁.semPlain x✝¹ x✝)
Instances For
Dependency graph
The translation into the general syntax #
The projection that keeps the left arm's columns of a match-count row and drops the count, in a context.
Equations
- FragQueryIn.dropCountIn c k i = ProjColIn.term (TermGIn.index (Fin.castAdd 1 i) ⋯)
Instances For
Dependency graph
The match count of a semijoin in a context: the left side, each row extended by the token counting, over a non-null constant, the rows of the right side the predicate matches it with.
Equations
- FragQueryIn.matchCountIn cnt φ R Q = R.Apply (AggQueryIn.GammaScalar ![TermIn.const ValueType.nonzero] ![cnt] (AggQueryIn.Sel φ Q ⋯))
Instances For
Dependency graph
The count site of a semijoin or an antijoin in a context: the
match count compared against 𝟘, projected back onto the left side.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
The translation into the general syntax. Each construct is the
operator of the same name, a semijoin or an antijoin the count site that
Provenance.Derived gives it, and the unit a scalar aggregation of
nothing over the empty relation.
Equations
- (FragQueryIn.Rel x✝ a).toAgg = AggQueryIn.Rel x✝ a
- FragQueryIn.Empty.toAgg = AggQueryIn.Empty
- FragQueryIn.Unit.toAgg = AggQueryIn.castKind FragQueryIn.toAgg._proof_2 (AggQueryIn.GammaScalar (fun (j : Fin 0) => j.elim0) (fun (j : Fin 0) => j.elim0) AggQueryIn.Empty)
- (FragQueryIn.Proj ts q).toAgg = AggQueryIn.Proj (fun (j : Fin x✝) => ProjColIn.term (ts j)) q.toAgg
- (FragQueryIn.Sel φ q).toAgg = AggQueryIn.Sel φ q.toAgg ⋯
- (q₁.Prod q₂).toAgg = AggQueryIn.castKind ⋯ (q₁.toAgg.Prod q₂.toAgg)
- (q₁.Apply q₂).toAgg = AggQueryIn.castKind ⋯ (q₁.toAgg.Apply q₂.toAgg)
- (q₁.Sum q₂).toAgg = q₁.toAgg.Sum q₂.toAgg
- a.Dedup.toAgg = a.toAgg.Dedup
- (a.Diff a_1).toAgg = a.toAgg.Diff a_1.toAgg
- (FragQueryIn.Semijoin cnt a φ a_1 a_2).toAgg = FragQueryIn.countSiteIn CompOp.ne cnt φ a_1.toAgg a_2.toAgg
- (FragQueryIn.Antijoin cnt a φ a_1 a_2).toAgg = FragQueryIn.countSiteIn CompOp.eq cnt φ a_1.toAgg a_2.toAgg
Instances For
Dependency graph
The plain semantics of the translation #
The general evaluator computes the plain semantics of the fragment.
Dependency graph
The annotated semantics of the translation #
The rows the general evaluator produces on a translated query are embedded annotated tuples: regular values, and nothing pending. The lemmas below read each operator on such rows.
The token a count site builds on a left row u: the scalar count,
over the non-null constant, of the rows of the right side that match
u.
Equations
- FragQueryIn.countToken cnt M u γ = AggValue.ofScalarGroup cnt (TermIn.const ValueType.nonzero) (Having.havingGroup (fun (i : Fin 0) => i.elim0) M fun (i : Fin 0) => i.elim0) (Fin.append u γ)
Instances For
Dependency graph
The general evaluator computes the annotated semantics of the
fragment, row for row: on a translated query it produces the embedded
rows of FragQueryIn.sem, in every context and every environment.
Absorptivity is asked only of a query with a semijoin, whose closed form
needs it.
Dependency graph
The general evaluator computes the annotated semantics of the fragment.