The set recursion from the bag recursion and ε, in the annotated semantics #
A set recursion μ^∪R.(q₀, q₁) whose body reads R once and through no
union is linear in R, and duplicate elimination sums the annotations of
the copies of a tuple without applying δ, so its rounds are ε of the
truncated sums of the rounds of a bag recursion (PathSum). The bounded
simulation of the plain semantics (MuUnion) therefore carries over, with
one change: its counter must not multiply the derivations it is paired
with. Here it is a successor counter: where δ is the support map, a
grouping annotates a counter 𝟙 or 𝟘, and a round moves to the next
counter annotated 𝟙 (wt_ctrSucc, wt_ctrLeast), the others carrying
rows that weigh nothing (PathSum.SimSpec, with its two lists of
counters); the rounds settle within twice the size of a tuple set where
the semiring is absorptive, cancellative without zero divisors, or has ⊗
equal to ⊕ on non-zero values (PathSum.SettlesLinear), and
evaluate_simResultA is the simulation's correctness under those counts.
The construction takes the counter as a parameter ch: false for the
successor counter, true for the all-chains one, which serves where δ
is the identity. Its width is (2c + 2) n + 2 either way (ctrWidth). The
pass is correct wherever its node is (AggQueryIn.NodeCorrect), and so is
the basis theorem (generatesAnnOn_annEpsOps_of); the two nodes are
proved in Provenance.AnnotatedChains.
This module works on the annotated relation a query gives, ann, which
is all the construction reads: every relation it builds is all-regular.
The commutative semiring underlying a commutative m-semiring, which
PathSum speaks in.
Equations
- CommSemiringWithMonus.toCommSemiring' = { toSemiring := inferInstance, mul_comm := ⋯ }
Dependency graph
The annotated relation of a query in an environment: its rows, each read as a tuple of values with its finalized annotation.
Equations
- q.ann d γ E = Multiset.map GenRow.toAnnotated (q.evaluate d γ E)
Instances For
Dependency graph
A linear term reads its recursive relation row by row #
The recursive relation replaced by the current row #
The row a Param leaf reading pv gives, whatever its kinds say.
Equations
Instances For
Dependency graph
The successor counter #
The first half of a row strictly below its second half.
Equations
- AggQueryIn.halvesLt K = (OrderSpec.asc K).ltPredOn (fun (k : Fin K) => TermGIn.index (Fin.castAdd K k) ⋯) (fun (k : Fin K) => TermGIn.index (Fin.natAdd K k) ⋯) (List.finRange K)
Instances For
Dependency graph
The middle third of a row strictly between its first and last.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
The first half of a row equals the counter of the current row of an apply, read off its outer columns.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
The column of the first and the last third of a row of three counters.
Equations
- AggQueryIn.outerThirds K j = Fin.addCases (fun (i : Fin K) => Fin.castAdd K (Fin.castAdd K i)) (fun (i : Fin K) => Fin.natAdd (K + K) i) j
Instances For
Dependency graph
Keeping the columns cols of an all-regular relation.
Equations
- AggQueryIn.keepCols cols q = AggQueryIn.castKind ⋯ (AggQueryIn.Proj (fun (j : Fin m) => ProjColIn.term (TermGIn.index (cols j) ⋯)) q)
Instances For
Dependency graph
The counters: the K-tuples over the values of EQ, each once.
Instances For
Dependency graph
The pairs of counters, the first below the second.
Equations
- EQ.ctrLt K = AggQueryIn.Sel (AggQueryIn.halvesLt K) ((EQ.ctr K).prodA (EQ.ctr K)) ⋯
Instances For
Dependency graph
The pairs of counters with one counter strictly between, once per counter between.
Equations
- EQ.ctrMid K = AggQueryIn.keepCols (AggQueryIn.outerThirds K) (AggQueryIn.Sel (AggQueryIn.midLt K) (((EQ.ctr K).prodA (EQ.ctr K)).prodA (EQ.ctr K)) ⋯)
Instances For
Dependency graph
The successor relation: the pairs of counters, the first below the
second, annotated 𝟙 where nothing is between and 𝟘 elsewhere.
Instances For
Dependency graph
The least counter: every counter, annotated 𝟙 where none is
below it and 𝟘 elsewhere.
Equations
- EQ.ctrLeast K = (EQ.ctr K).Diff (AggQueryIn.keepCols (fun (j : Fin K) => Fin.natAdd K j) (EQ.ctrLt K))
Instances For
Dependency graph
The step relation of a counter: the successor relation, or, for the
all-chains counter (ch = true), every ordered pair of counters.
Equations
- AggQueryIn.ctrStep ch EQ K = bif ch then EQ.ctrLt K else EQ.ctrSucc K
Instances For
Dependency graph
The counters a simulation starts from: the least one, or, for the
all-chains counter (ch = true), every counter.
Equations
- AggQueryIn.ctrStart ch EQ K = bif ch then EQ.ctr K else EQ.ctrLeast K
Instances For
Dependency graph
The counters after the current row's, under an apply over the simulation's rows: the step relation's second halves, where the first half is the current row's counter.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
One round of the annotated simulation: for each row, the term at its tuple part, paired with the counter after the row's.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
The annotated simulation: a bag recursion over a tuple and a counter, from the base paired with the starting counters.
Equations
- AggQueryIn.simA s s' n K ch EQ BQ L = AggQueryIn.Mu s' (BQ.prodA (AggQueryIn.ctrStart ch EQ K)) (AggQueryIn.simBodyA s s' n K ch EQ L)
Instances For
Dependency graph
Its tuple parts, duplicates eliminated: the set recursion's value.
Equations
- AggQueryIn.simResultA s s' n K ch EQ BQ L = (AggQueryIn.keepCols (fun (i : Fin n) => Fin.castAdd K i) (AggQueryIn.simA s s' n K ch EQ BQ L)).Dedup
Instances For
Dependency graph
The K-tuples over a set of unary rows.
Equations
- AggQueryIn.powT V 0 = {fun (k : Fin 0) => k.elim0}
- AggQueryIn.powT V K.succ = Multiset.map (fun (p : Tuple T K × Tuple T 1) => Fin.append p.1 p.2) ((AggQueryIn.powT V K).product V)
Instances For
Dependency graph
The tuples of the ordered pairs of counters.
Equations
- AggQueryIn.ltPairs W = Multiset.map (fun (p : Tuple T K' × Tuple T K') => Fin.append p.1 p.2) (Multiset.filter (fun (p : Tuple T K' × Tuple T K') => ascLt K' p.1 p.2) (W.product W))
Instances For
Dependency graph
One round of the simulation, and its rounds #
The right side of one round of the simulation, at a row u: the term
at its tuple part, paired with the counters after its counter.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
The simulation, read as PathSum.SimSpec #
Splitting a row of the simulation into its tuple and its counter.
Equations
- AggQueryIn.splitRow p = ((AggQueryIn.leftPart n K' p.1, AggQueryIn.rightPart n K' p.1), p.2)
Instances For
Dependency graph
Settling #
The counter values: the leaves' values and the constants #
The unary relations the counter values are the union of: each column of each leaf, and each constant.
Equations
- AggQueryIn.valParts ls cs = List.flatMap (fun (p : ℕ × String) => List.map (AggQueryIn.Rel p.1 p.2).colRel (List.finRange p.1)) ls ++ List.map AggQueryIn.constRel cs
Instances For
Dependency graph
The counter values: the non-null values of the leaves ls and of
the constants cs. Unlike the plain counter relation it reads no context
value, so it is well-kinded under any context.
Equations
- AggQueryIn.valRel ls cs = AggQueryIn.Sel AggQueryIn.nonNullPred (AggQueryIn.listSum (AggQueryIn.valParts ls cs)) ⋯
Instances For
Dependency graph
Iterations that agree, and the settled set #
The node: a set recursion replaced by its simulation #
The leaves the counter of a set recursion reads.
Equations
- AggQueryIn.ctrLeaves s q₀ q₁ = (AggQueryIn.MuSet s q₀ q₁).leaves
Instances For
Dependency graph
The constants the counter of a set recursion reads: the recursion's own, and two more, so that there are at least two counter values.
Equations
- AggQueryIn.ctrConsts s q₀ q₁ = (AggQueryIn.MuSet s q₀ q₁).allConsts.toList ++ [0, ValueType.nonzero]
Instances For
Dependency graph
The width of the counter: (2c + 2) n + 2, which the values of the
rows alone bound (AggQueryIn.card_arith_chain), with room for twice as
many counters as tuples (AggQueryIn.card_arith_succ).
Instances For
Dependency graph
The query a set recursion is replaced by.
Equations
- AggQueryIn.muSetSim ch s s' q₀ q₁ q₀' q₁' = AggQueryIn.simResultA s s' n (AggQueryIn.ctrWidth c n) ch (AggQueryIn.valRel (AggQueryIn.ctrLeaves s q₀ q₁) (AggQueryIn.ctrConsts s q₀ q₁)) q₀' q₁'
Instances For
Dependency graph
What the simulation mentions, and that it explodes nothing #
The pass #
Every set recursion replaced by its simulation, the supply split in three at each node, the recursion's own fresh name the supply's first.
Equations
- One or more equations did not get rendered due to their size.
- AggQueryIn.muSetFreeA ch f (AggQueryIn.Rel x✝ s) = AggQueryIn.Rel x✝ s
- AggQueryIn.muSetFreeA ch f (AggQueryIn.Hole x✝¹ s x✝) = AggQueryIn.Hole x✝¹ s x✝
- AggQueryIn.muSetFreeA ch f (AggQueryIn.Param pv x✝) = AggQueryIn.Param pv x✝
- AggQueryIn.muSetFreeA ch f AggQueryIn.Empty = AggQueryIn.Empty
- AggQueryIn.muSetFreeA ch f (AggQueryIn.Proj ps q) = AggQueryIn.Proj ps (AggQueryIn.muSetFreeA ch f q)
- AggQueryIn.muSetFreeA ch f (AggQueryIn.Sel φ q hφ) = AggQueryIn.Sel φ (AggQueryIn.muSetFreeA ch f q) hφ
- AggQueryIn.muSetFreeA ch f (q₁.Prod q₂) = (AggQueryIn.muSetFreeA ch (AggQueryIn.tri f 1) q₁).Prod (AggQueryIn.muSetFreeA ch (AggQueryIn.tri f 2) q₂)
- AggQueryIn.muSetFreeA ch f (q₁.Apply q₂) = (AggQueryIn.muSetFreeA ch (AggQueryIn.tri f 1) q₁).Apply (AggQueryIn.muSetFreeA ch (AggQueryIn.tri f 2) q₂)
- AggQueryIn.muSetFreeA ch f (q₁.Sum q₂) = (AggQueryIn.muSetFreeA ch (AggQueryIn.tri f 1) q₁).Sum (AggQueryIn.muSetFreeA ch (AggQueryIn.tri f 2) q₂)
- AggQueryIn.muSetFreeA ch f q.Dedup = (AggQueryIn.muSetFreeA ch f q).Dedup
- AggQueryIn.muSetFreeA ch f (q₁.Diff q₂) = (AggQueryIn.muSetFreeA ch (AggQueryIn.tri f 1) q₁).Diff (AggQueryIn.muSetFreeA ch (AggQueryIn.tri f 2) q₂)
- AggQueryIn.muSetFreeA ch f (AggQueryIn.Explode k h q) = AggQueryIn.Explode k h (AggQueryIn.muSetFreeA ch f q)
- AggQueryIn.muSetFreeA ch f (AggQueryIn.Retag h q) = AggQueryIn.Retag h (AggQueryIn.muSetFreeA ch f q)
- AggQueryIn.muSetFreeA ch f (AggQueryIn.Mu s q₀ q₁) = AggQueryIn.Mu s (AggQueryIn.muSetFreeA ch (AggQueryIn.tri f 1) q₀) (AggQueryIn.muSetFreeA ch (AggQueryIn.tri f 2) q₁)
- AggQueryIn.muSetFreeA ch f (AggQueryIn.Gamma is ts fs q keep ord) = AggQueryIn.Gamma is ts fs (AggQueryIn.muSetFreeA ch f q) keep ord
- AggQueryIn.muSetFreeA ch f (AggQueryIn.GammaScalar ts fs q ord) = AggQueryIn.GammaScalar ts fs (AggQueryIn.muSetFreeA ch f q) ord
- AggQueryIn.muSetFreeA ch f (AggQueryIn.GammaNest is his p g q) = AggQueryIn.GammaNest is his p g (AggQueryIn.muSetFreeA ch f q)
- AggQueryIn.muSetFreeA ch f (AggQueryIn.ProvSum is his t q) = AggQueryIn.ProvSum is his t (AggQueryIn.muSetFreeA ch f q)
- AggQueryIn.muSetFreeA ch f (AggQueryIn.GammaTok is his ts fs a q keep) = AggQueryIn.GammaTok is his ts fs a (AggQueryIn.muSetFreeA ch f q) keep
- AggQueryIn.muSetFreeA ch f (AggQueryIn.Win P O o w t g q hrr dist keep) = AggQueryIn.Win P O o w t g (AggQueryIn.muSetFreeA ch f q) hrr dist keep
- AggQueryIn.muSetFreeA ch f (AggQueryIn.WinExpr P O o ws ts fs g q_1 keeps) = AggQueryIn.WinExpr P O o ws ts fs g (AggQueryIn.muSetFreeA ch f q_1) keeps
Instances For
Dependency graph
What the pass asks of its node: at the instances P admits, a set
recursion that settles is its simulation, given matches of its base and
body that agree with them wherever these settle.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
The classes the pass uses #
The classes the simulation is written with.
Equations
Instances For
Dependency graph
The signature of the pass's output #
The kinds of the pass's output #
The names of the pass's output #
Hygiene and the schema of the pass's output #
The annotated basis with ε and without μ^∪ #
The annotated basis with ε: {∅, Π, σ, apply, γ, win, μ^⊎, ε, −},
the classes other than ×, ⊎ and μ^∪.
Equations
Instances For
Dependency graph
A set of classes generates the annotated algebra over the instances
P admits: GeneratesAnn, with the instances restricted.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
The classes {∅, Π, σ, apply, γ, win, μ^⊎, ε, −} match every query
of the annotated algebra in the minimal universe, at the instances P
admits, wherever the simulation of a set recursion is correct there: the
products are written as applies, the unions as bag recursions, and every
set recursion as the counter simulation of AggQueryIn.muSetFreeA, whose
own unions are written as bag recursions in turn. The construction reads
no annotation, so one query serves every semiring at once, at the instances
where the counter ch simulates a set recursion.
Dependency graph
The classes {∅, Π, σ, apply, γ, win, μ^⊎, ε, −} match every query
of the annotated algebra in the minimal universe, at the instances P
admits, wherever the simulation of a set recursion is correct there.