Annotations of the derived operators #
The annotations of the operators of Provenance.Derived follow from their
definitions, being the annotations the basis gives the query each one
abbreviates. Some are worth computing, because they are what the choice of
definition is answerable for.
Intersection is the first. q₁ ∩ q₂ annotates a shared tuple by
(⊕ α) ⊗ (⊕ β), the sums ranging over its copies on each side: the
provenance of a conjunction of the two memberships. The other definition
that comes to mind, ε(q₁ - (q₁ - q₂)), has the same rows and the same
support over 𝔹, and annotates them by a difference of differences
instead.
The ⊕-sum of the annotations a query gives one tuple: what
duplicate elimination accumulates on it.
Equations
- AggQueryIn.annSum q d u = (Multiset.map Prod.snd (Multiset.filter (fun (p : AnnotatedTuple T K n) => p.1 = u) (AggQueryIn.evaluateAnnotated q d))).sum
Instances For
Dependency graph
The ⊕-sum of the annotations one tuple carries in an annotated
relation.
Equations
- r.annSum u = (Multiset.map Prod.snd (Multiset.filter (fun (p : AnnotatedTuple T K n) => p.1 = u) r)).sum
Instances For
Dependency graph
Outer joins #
The ⊕-sum of the annotations of a row's matches, over the matches
of every copy of its tuple – the difference the padded copy goes through
is per tuple and syntactic.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
The ⊕-sum of the annotations of the matches of a row of the right
arm.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
Semijoin and antijoin #
The ⊕-sum of every annotation of an annotated relation: the
provenance of “there is a row here”, which is what an existential
subquery asks for.
Equations
- r.annTotal = (Multiset.map Prod.snd r).sum
Instances For
Dependency graph
The token a match count builds on a row u of the left arm: the
scalar count, over the column kap, of the rows of Q that φ matches
u with. Its family is the count's, and records the values of u the
count reads.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
What a semijoin and an antijoin annotate #
The FILTER clause #
The clause changes nothing about a group: the token carries all of its occurrences, so the group's key and its existence factor are those of all of them, and a filtered-out occurrence still witnesses it. What changes is the value the token takes in a world, and it changes there in the same way as over plain relations – the input policy drops what the clause nulls out, so the aggregate reads exactly the occurrences of that world the clause keeps.
Why a null-keeping aggregate has to be told about the clause #
On a null-skipping aggregate and on a count, FILTER is a term: nulling
the rejected occurrences out and letting the input policy drop them is
cutting them from the sequence (aggValOn_filterTerm_sqlOf,
aggValOn_filterTerm_counting). On a null-keeping aggregate it is not a
term, and here is why: such an aggregate reads the null as a value, so it
reads the rejected occurrences too, and the clause has to cut the
sequence itself (Having.aggValOnWhen).
The value domain of the counterexample: ℕ with a null adjoined.
Equations
Instances For
Dependency graph
A null-keeping aggregate: the length of the sequence, nulls
included. This is ARRAY_AGG's input policy – every value is read – in
the one shape a ValueType affords, there being no array in the domain:
what the aggregate returns is how many values it was given.
Equations
Instances For
Dependency graph
A group of two occurrences, carrying the values 1 and 2.
Equations
- AggQueryIn.FilterCounterexample.U = [(fun (x : Fin 1) => WithNull.val 1, 1), (fun (x : Fin 1) => WithNull.val 2, 1)]
Instances For
Dependency graph
The clause x = 1, which keeps the first occurrence and rejects the
second.
Equations
Instances For
Dependency graph
Its right-hand side.
Equations
Instances For
Dependency graph
The token a filtered aggregation builds #
Constant relations, annotated #
The unit relation's row and each row of a constant relation carry 𝟙: a
constant relation is part of the query, so no instance weighs it.