Congruence of predicate provenance under tie-block permutations #
The occurrence payload of an aggregate token is produced by Having.havingGroup,
which sorts the group by the canonical order on the tuple part and breaks ties
on equal tuple parts by an arbitrary fixed order on the annotations. Pushing a
semiring homomorphism through the annotated database can therefore reorder the
payload – but only within blocks of occurrences with equal tuple parts, hence
equal aggregated-term values.
This file proves that the predicate provenance of a token is invariant under exactly such reorderings. The invariance is genuinely limited to tie blocks: for an order-sensitive aggregate, exchanging two occurrences of equal value across an occurrence of a different value changes the predicate provenance.
TiePerm eqv– permutations generated by transposing adjacent elements related byeqv(here: pairs with equal first components), the guarded analogue ofList.Perm;tiePerm_of_perm_of_sorted– two lists that are permutations of each other and both sorted by a common key are related byTiePermon key equality;AggValue.predProvAux– a recursion form of the predicate provenance, with accumulators for the values kept so far, the annotations discarded so far, and whether the world is already non-empty;AggValue.predProvWith_eq_predProvAux– the world-sum of the predicate provenance equals the recursion form;AggValue.predProv_congr– the congruence: tokens with the same aggregate andTiePerm-related payloads have the same predicate provenance.
Tie-block permutations #
Permutations generated by transposing adjacent elements related by
eqv: the guarded analogue of List.Perm, whose swap constructor requires
the exchanged elements to be related. For eqv the equality of sort keys,
this captures exactly the reorderings a sort with an arbitrary tie-break can
introduce.
- nil {α : Type} {eqv : α → α → Prop} : TiePerm eqv [] []
- cons {α : Type} {eqv : α → α → Prop} (a : α) {l₁ l₂ : List α} : TiePerm eqv l₁ l₂ → TiePerm eqv (a :: l₁) (a :: l₂)
- swap {α : Type} {eqv : α → α → Prop} {a b : α} (h : eqv a b) {l₁ l₂ : List α} : TiePerm eqv l₁ l₂ → TiePerm eqv (a :: b :: l₁) (b :: a :: l₂)
- trans {α : Type} {eqv : α → α → Prop} {l₁ l₂ l₃ : List α} : TiePerm eqv l₁ l₂ → TiePerm eqv l₂ l₃ → TiePerm eqv l₁ l₃
Instances For
Dependency graph
Sorted permutations are tie-block permutations #
A sort determines a list up to a tie-block permutation as soon as the
relation it sorts by is total and transitive and its ties are exactly
equality of some key. The canonical case is key x ≤ key y for a key into a
linear order, but a window's frame is sorted by its ORDER BY, which is not
of that shape: it reads the order columns in the clause's direction and null
placement, and breaks the clause's ties by the canonical order.
Two lists that are permutations of each other and both sorted by the key
key differ only by a tie-block permutation on key equality: the sort order
determines everything except the arrangement inside blocks of equal keys.
Dependency graph
Position bookkeeping for the world split #
The recursion form of predicate provenance #
Recursion form of the predicate provenance of a token: acc accumulates
the values of the occurrences kept so far, ex the sum of the annotations of
the occurrences discarded so far, and started records whether an occurrence
has been kept (worlds must end up non-empty). Keeping an occurrence
contributes its annotation as a factor; discarding it moves its annotation
into the pending 𝟙 ⊖ Σ factor materialized at the end of the list.
Equations
Instances For
Dependency graph
The predicate provenance of a token is its recursion form.
Dependency graph
The comparison case.
Dependency graph
Tie-block permutation changes no value the token takes: its
swaps exchange occurrences of equal value, so the list of values is
untouched and AggValue.vals reads only that.
Dependency graph
The several-leaf recursion #
predProvAux walks the occurrence family of one token, carrying the
values kept so far. An aggregate expression reads several leaves over
one shared family, each on its own part of a world, so the walk carries
one accumulator per leaf and keeps an occurrence only for the leaves
that read it. The world condition becomes per leaf as well: a world must
meet the part of the family each grouped leaf reads.
The occurrence list carries, per occurrence, the value each leaf reads
there, the annotation, and which leaves read it – which is AggExpr's
occs together with reads, in the form a recursion over the list can
use. Since an AggExpr's occurrences carry their leaf flags,
AggExpr.leafSeq_eq_filter is the shape the walk reads, and
predProvWith_eq_exprProvAux specializes the walk to
AggExpr.predProvWith.
The several-leaf counterpart of AggValue.predProvAux: acc l the
values leaf l has kept, ex the annotations discarded so far, and
started l whether leaf l has kept an occurrence.