Extensionality for every semantics that extends semiring provenance #
Provenance.Extensionality grades the m-semirings for one semantics, the
evaluator of the library. This module removes that dependence. A
semantics here is any function S from the closed queries of the
fragment syntax and the instances annotated in a semiring K to annotated
relations. It extends semiring provenance
(ExtendsSemiringProvenance) when base relations keep their annotations,
the unit is annotated 𝟙, a projection keeps annotations, a union is the
multiset sum, a product multiplies, and duplicate elimination sums each
class, on all arguments, negative ones included. Nothing is asked of the
difference, the semijoin, or the antijoin, nor of homomorphisms, nor of any
agreement with SQL, and K is not assumed to have a monus.
For such an S:
- extensionality for
F₀makes⊗commutative (ExtendsSemiringProvenance.mul_comm_of_level0); - extensionality for
F₁makes(K, ⊕, ⊗)a lattice (ExtendsSemiringProvenance.isLatticeRig_of_level1); - extensionality for
F₂gives every element a complement, whateverSdoes on negation (ExtendsSemiringProvenance.isBooleanRig_of_level2).
The complement comes from two pairs around a query E of arity 0 that
holds exactly when R is empty, its own annotation c being anything:
R × E against the empty query forces b ⊗ c = 𝟘, and E ⊎ ε(Π∅ R)
against the unit forces c ⊕ b = 𝟙. Neither compares values, so NULL plays
no part.
Over a commutative m-semiring the converse holds at F₂:
exists_semantics_extensional_iff says that a semantics extending semiring
provenance and extensional for F₂ exists iff K is a Boolean m-semiring,
whatever its δ.
The ⊕-sum of the annotations one tuple carries, over any semiring.
Equations
- FragQueryIn.annCollapse r u = (Multiset.map Prod.snd (Multiset.filter (fun (p : AnnotatedTuple T K n) => p.1 = u) r)).sum
Instances For
Dependency graph
A semantics extends semiring provenance when it follows the clauses of semiring provenance on the positive operators, for all arguments. The negative operators are left free.
- rel (n : ℕ) (s : String) (d : AnnotatedDatabase T K) : S n (Rel n s) d = (AnnotatedDatabase.find n s d).getD 0
- proj {n m : ℕ} (ts : Tuple (TermGIn T 0 (ColKind.allReg n)) m) (q : FragQuery T n) (d : AnnotatedDatabase T K) : S m (Proj ts q) d = Multiset.map (fun (p : AnnotatedTuple T K n) => (fun (j : Fin m) => (ts j).evalPlain p.1, p.2)) (S n q d)
- prod {n₁ n₂ : ℕ} (q₁ : FragQuery T n₁) (q₂ : FragQuery T n₂) (d : AnnotatedDatabase T K) : S (n₁ + n₂) (Prod q₁ q₂) d = Multiset.map (fun (xy : AnnotatedTuple T K n₁ × AnnotatedTuple T K n₂) => (Fin.append xy.1.1 xy.2.1, xy.1.2 * xy.2.2)) (Multiset.product (S n₁ q₁ d) (S n₂ q₂ d))
- dedup {n : ℕ} (q : FragQuery T n) (d : AnnotatedDatabase T K) : S n (Dedup q) d = Multiset.map (fun (u : Tuple T n) => (u, annCollapse (S n q d) u)) (Multiset.map Prod.fst (S n q d)).dedup
Instances For
Dependency graph
K is extensional under S for the queries satisfying F: two such
queries with the same plain semantics on every instance collapse, under S
and 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 lattice laws of a semiring.
- idempotent : _root_.idempotent K
- mulIdempotent : _root_.mulIdempotent K
- absorptive : _root_.absorptive K
Instances For
Dependency graph
A semiring that is a lattice in which every element has a complement.
Instances For
Dependency graph
The queries #
The swap of the two columns of a product of two relations of arity one.
Equations
Instances For
Dependency graph
The left column of a product with a relation of arity 0.
Instances For
Dependency graph
The projection of a relation of arity one on no column.
Equations
- FragQueryIn.noCol j = j.elim0
Instances For
Dependency graph
ε(Π∅ R): the one empty tuple, exactly when R is non-empty.
Instances For
Dependency graph
𝟏 − ε(Π∅ R): the one empty tuple, exactly when R is empty.
Instances For
Dependency graph
E tests that R is empty, on the plain semantics.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
The difference tests emptiness.
Dependency graph
The always-true match of a subquery row: 0 IS NOT DISTINCT FROM 0.
Equations
Instances For
Dependency graph
SELECT 1 WHERE NOT EXISTS (SELECT * FROM R), on the empty tuple.
Equations
- FragQueryIn.notExistsR cnt hc = FragQueryIn.Antijoin cnt hc FragQueryIn.matchAll FragQueryIn.Unit (FragQueryIn.relRIn (0 + 0))
Instances For
Dependency graph
NOT EXISTS tests emptiness.
Dependency graph
The computations under a semantics #
What extensionality forces #
⊗ is commutative where K is extensional for F₀ under S.
Dependency graph
(K, ⊕, ⊗) is a lattice where K is extensional for F₁ under S.
Dependency graph
The complement #
Every element has a complement where K is extensional for F₂
under S: the annotation S gives a query that tests the emptiness of R,
whatever it is, is the complement.
Dependency graph
Extensionality for F₂ under a semantics that extends semiring
provenance makes K a Boolean algebra, whatever the semantics does on
negation.
Dependency graph
Over a commutative m-semiring #
In a commutative m-semiring, a Boolean rig is a Boolean m-semiring: the
monus against 𝟙 is below the complement, hence disjoint from the element.
Dependency graph
The semantics of the fragment extends semiring provenance.
Dependency graph
Over a commutative m-semiring, a semantics extending semiring
provenance and extensional for F₂ exists iff K is a Boolean m-semiring,
whatever its δ.
Dependency graph
The copies themselves need not agree #
Collapsing is necessary from F₂ on. Splitting R on whether S is
non-empty returns R on every plain instance, without counting anything, and
gives one tuple two copies where R gives it one.
The base relation S of arity 1, in a context.
Equations
- FragQueryIn.relSIn c = FragQueryIn.Rel 1 "S"
Instances For
Dependency graph
The always-true match of a row of R with a row of S.
Equations
Instances For
Dependency graph
The split of R on whether S is non-empty:
SELECT x FROM R WHERE EXISTS (SELECT * FROM S) UNION ALL SELECT x FROM R WHERE NOT EXISTS (SELECT * FROM S).
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
The split of R is R on every plain instance.
Dependency graph
The copies of the split: on R = {x : a} and S = {x : s}, the tuple
has two copies, annotated a ⊗ s and a ⊗ (𝟙 ⊖ s), where R gives it one,
annotated a.
Dependency graph
The copies differ, even with 𝟘 set aside: R holds a copy annotated 𝟙
that the split does not, as soon as neither s nor 𝟙 ⊖ s is 𝟙, in
particular for a variable s of 𝔹[X].