The difference is necessary in the annotated algebra #
A set of classes that generates the annotated algebra contains −. The
witness semiring is ℕ × ℕ, ℕ read on two instances at once
(NatPair). The invariant is that, without a difference, every
annotation a query builds is zero in one coordinate exactly where it is in
the other (ZeroPat). That holds of sums and products, since ℕ has no
zero divisors, of δ, which is the support map, and of the 𝟙 ⊖ s a
world of an aggregate value is weighed with. It fails for a difference:
R − S, with R holding a annotated (1, 3) and S holding it twice
annotated (1, 1), gives (1, 3) ⊖ (2, 2) = (0, 1)
(diff_mem_of_generatesAnn).
The invariant is stated for any property Q of annotations closed under
those operations (AnnClosed), and proved of every annotation the
evaluator builds – a row's, the occurrences' of the tokens it carries,
and the predicate provenance of a selection on aggregate values
(annIn_evaluate).
Two copies of ℕ #
ℕ read on two instances at once: pairs, with every operation
componentwise.
Instances For
Dependency graph
Equations
- One or more equations did not get rendered due to their size.
Dependency graph
Equations
- One or more equations did not get rendered due to their size.
Dependency graph
Dependency graph
Equations
- NatPair.instSub = { sub := NatPair.instSub._aux_1 }
Dependency graph
Dependency graph
The two coordinates of a pair.
Instances For
Dependency graph
Dependency graph
Dependency graph
Dependency graph
Dependency graph
The support map, coordinate by coordinate.
Instances For
Dependency graph
Dependency graph
Equations
- One or more equations did not get rendered due to their size.
Dependency graph
Equations
- NatPair.instCommSemiringWithMonus = { toSemiringWithMonus := NatPair.instSemiringWithMonus, mul_comm := NatPair.instCommSemiringWithMonus._proof_1 }
Dependency graph
Equations
- One or more equations did not get rendered due to their size.
Dependency graph
The two coordinates vanish together.
Instances For
Dependency graph
Properties of annotations the operators keep, but for a difference #
A property of annotations every operator but the difference keeps:
𝟘, 𝟙, sums, products, δ, and 𝟙 ⊖ a.
- zero : Q 0
- one : Q 1
- add (a b : K) : Q a → Q b → Q (a + b)
- mul (a b : K) : Q a → Q b → Q (a * b)
- delta (a : K) : Q a → Q (SemiringWithMonus.delta a)
- one_sub (a : K) : Q a → Q (1 - a)
Instances For
Dependency graph
The annotations a token carries #
Every occurrence of an aggregate value is annotated within Q.
Equations
- AggValue.AnnsIn Q a = ∀ p ∈ a.occs, Q p.2
Instances For
Dependency graph
Every occurrence of an aggregate expression is annotated within Q.
Equations
- AggExpr.AnnsIn Q e = ∀ p ∈ e.occs, Q p.2.1
Instances For
Dependency graph
Every annotation of an inner value, at every storey, is within Q.
Equations
- NestInner.AnnsIn Q 0 e = AggExpr.AnnsIn Q e
- NestInner.AnnsIn Q j.succ (Sum.inl x_2) = NestInner.AnnsIn Q j x_2
- NestInner.AnnsIn Q j.succ (Sum.inr N) = ∀ o ∈ N.occs, Q o.2 ∧ NestInner.AnnsIn Q j o.1
Instances For
Dependency graph
Every occurrence of a nested value, and every inner one at every
storey, is annotated within Q.
Equations
- NestedValue.AnnsIn Q a = ∀ o ∈ a.occs, Q o.2 ∧ NestInner.AnnsIn Q a.lev o.1
Instances For
Dependency graph
Every annotation a token carries is within Q.
Equations
- AggTok.AnnsIn Q (AggTok.tok a) = AggValue.AnnsIn Q a
- AggTok.AnnsIn Q (AggTok.nest a) = NestedValue.AnnsIn Q a
- AggTok.AnnsIn Q (AggTok.expr e) = AggExpr.AnnsIn Q e
Instances For
Dependency graph
The predicate provenance #
Every annotation the evaluator builds #
A row's annotations are within Q: its concrete part, its pending
factors' occurrences, and every annotation the tokens it holds carry.
Equations
Instances For
Dependency graph
Every annotation a query without a difference builds is within any
Q the other operators keep, as soon as the instance's annotations,
the context's tokens and the rounds the holes are bound to are.
Dependency graph
The witness #
The schema of two unary relations, R and S.
Equations
Instances For
Dependency graph
Dependency graph
The instance it tells apart from every query without a difference:
R holds 0 annotated (1, 3), and S holds it twice, annotated
(1, 1).
Equations
Instances For
Dependency graph
− is in every set generating the annotated algebra over ℕ × ℕ:
without a difference, every annotation of a query's result is zero in one
coordinate exactly where it is in the other, and R − S gives (0, 1) on
dDiff.