The min-cost-paths m-semiring (ProvSQL's sr_tropical_paths) #
A value is ๐, or a cost c with a language L over the labels of the
input tuples โ the least cost of a derivation of a tuple, with every
derivation of that cost. sr_tropical_paths (src/semiring/TropicalPaths.h,
since 1.13.0) computes in it:
(c, L) โ (c', L')keeps the lower cost with its derivations, and the union of the two languages on a tie;(c, L) โ (c', L') = (c + c', L ยท L'), the concatenation in the order of the query, which does not commute (not_commutative);๐is the absent value,๐ = (0, {ฮต}).
โ is the join of a partial order: the lexicographic order of the
costs reversed and the languages by inclusion (TropicalPathsVal.le_iff:
(c, L) โค (c', L') when c' < c, or c = c' and L โ L'), with ๐
adjoined at the bottom. That order is the natural order of the semiring,
and the monus it determines โ a where a has the lower cost, ๐
where b has, and the difference of the languages on a tie โ makes the
semiring an m-semiring (instSemiringWithMonus). ProvSQL refuses to
compute that monus (semiring-no-monus: on a tie it is a difference of
languages, which needs automata), so the refusal is a gap of the
implementation and not of the algebra, exactly as for sr_regex.
The star ProvSQL implements is verified against the fixpoint equation
s = ๐ โ a โ s it solves: for a positive cost the solution is ๐
(one_add_mul_one_of_pos: a cycle of positive cost never lies on a
shortest path), for a cost 0 it is (0, Lโ) (one_add_mul_kstar:
the cycle can be followed any number of times at no cost), and for a
negative cost there is none (no_fixpoint_of_neg: the least cost is
unbounded), which is what recursion-cycle-no-value refuses.
The costs are any linearly ordered cancellative additive monoid (โ
for ProvSQL), the labels any type.
A cost and the derivations of that cost: a value of
sr_tropical_paths other than ๐.
- cost : C
- paths : Language ฮ
Instances For
Dependency graph
The key the values are ordered by: the cost reversed, then the language by inclusion.
Instances For
Dependency graph
Dependency graph
Dependency graph
Dependency graph
โ on two values: the lower cost wins, a tie merges the languages.
Equations
Instances For
Dependency graph
Dependency graph
Dependency graph
Dependency graph
โ is the join of the order.
Equations
- TropicalPathsVal.instSemilatticeSup = { toPartialOrder := TropicalPathsVal.instPartialOrder, sup := TropicalPathsVal.sup, le_sup_left := โฏ, le_sup_right := โฏ, sup_le := โฏ }
Dependency graph
The min-cost-paths semiring: a value of sr_tropical_paths, with
๐ at the bottom.
- val : Option (TropicalPathsVal C ฮ)
Instances For
Dependency graph
The order's key: โฅ for ๐, the value's key otherwise.
Instances For
Dependency graph
Dependency graph
Dependency graph
Dependency graph
Dependency graph
Dependency graph
โ: ๐ is neutral, two values join.
Equations
Instances For
Dependency graph
Equations
- TropicalPaths.instAdd = { add := TropicalPaths.add }
Dependency graph
Dependency graph
Dependency graph
Dependency graph
โ is the join of the order with ๐ at the bottom.
Equations
- TropicalPaths.instSemilatticeSup = { toPartialOrder := TropicalPaths.instPartialOrder, sup := TropicalPaths.add, le_sup_left := โฏ, le_sup_right := โฏ, sup_le := โฏ }
Dependency graph
Dependency graph
Dependency graph
โ concatenates the languages, adding the costs; ๐ absorbs.
Equations
- One or more equations did not get rendered due to their size.
Dependency graph
Dependency graph
Dependency graph
Dependency graph
Dependency graph
Dependency graph
Distributivity on the right, value by value: the lower cost stays the lower after adding the same cost, and a tie's merged language concatenates as the union of the concatenations.
Dependency graph
And on the left.
Dependency graph
Equations
- One or more equations did not get rendered due to their size.
Dependency graph
Dependency graph
Dependency graph
ProvSQL's TropicalPaths::delta: the indicator of being non-๐.
Instances For
Dependency graph
Dependency graph
Dependency graph
Dependency graph
The monus: a where a has the lower cost, ๐ where b has,
and on a tie the difference of the languages, ๐ if that is empty.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
Dependency graph
The min-cost-paths semiring is an m-semiring.
Equations
- One or more equations did not get rendered due to their size.