The one-best-derivation m-semiring (ProvSQL's sr_best_path) #
A value is ๐, or a cost c with a word w of labels โ one derivation
of a tuple, with its cost โ and a value is better than another when
its cost is lower or, at equal costs, when its word comes first in
shortlex order (shorter first, then lexicographic). sr_best_path
(src/semiring/BestPath.h, since 1.13.0) computes in it:
a โ bis the better of the two, so that the values form a chain with๐at the bottom andโits maximum (selective_of);(c, w) โ (c', w') = (c + c', w ยท w'), the concatenation in the order of the query, which does not commute (not_commutative);๐ = (0, ฮต);a โ bisawhereais strictly better thanb,๐otherwise.
The chain is the natural order of the semiring, better being greater:
the LinearOrder of BestPathVal is the dual of the shortlex-with-cost
key, with ๐ adjoined at the bottom. What makes the semiring laws hold
is that this key is compatible with concatenation on both sides
(key_mul_le_mul_right, key_mul_le_mul_left), strictly, which is also
what gives the distributivity of โ over the monus on both sides
(mul_sub_left_distributive_of, mul_sub_right_distributive_of) that
BestPath.h claims. ProvSQL's two further claims: with nonnegative
costs ๐ is the best value, so the semiring is absorptive on both
sides (absorptive_of, which asks 0 โค c of every cost โ ProvSQL
refuses a negative cost at the leaves, semiring-negative-cost), and
every star is then ๐. Without the cost hypothesis the semiring laws
still hold; only absorptivity does not.
The costs are any linearly ordered cancellative additive monoid
(โ, โโฅ0, โ), the labels any linearly ordered type (ProvSQL
compares them bytewise).
A cost and a word of labels: a value of sr_best_path other than
๐.
- cost : C
- word : List ฮ
Instances For
Dependency graph
The key a value is compared by: its cost, then the length of its word, then the word itself in lexicographic order. Smaller is better.
Instances For
Dependency graph
Dependency graph
The chain: better is greater.
Equations
- BestPathVal.instLinearOrder = LinearOrder.lift' (fun (p : BestPathVal C ฮ) => OrderDual.toDual p.key) โฏ
Dependency graph
Concatenation, with the costs added.
Instances For
Dependency graph
The empty derivation at cost 0.
Instances For
Dependency graph
The one-best-derivation semiring: a value of sr_best_path, with
๐ at the bottom of the chain. A structure of its own, so that the
chain's order and the operations below are found on it and not on
Option.
- val : Option (BestPathVal C ฮ)
Instances For
Dependency graph
The chain's key: โฅ for ๐, the dual of the value's key otherwise.
Instances For
Dependency graph
Dependency graph
Equations
Dependency graph
โ is the better of two values: the maximum of the chain.
Dependency graph
Dependency graph
Dependency graph
โ concatenates, adding the costs; ๐ absorbs.
Dependency graph
Equations
- BestPath.instOne = { one := { val := some BestPathVal.one } }
Dependency graph
Dependency graph
Dependency graph
Dependency graph
Dependency graph
โ r is monotone in the chain.
Dependency graph
Dependency graph
Equations
- One or more equations did not get rendered due to their size.
Dependency graph
Dependency graph
Dependency graph
ProvSQL's BestPath::delta: the indicator of being non-๐.
Instances For
Dependency graph
Dependency graph
Dependency graph
Dependency graph
The one-best-derivation semiring is an m-semiring: a โ b is
a where a is strictly better than b and ๐ otherwise, the least
c with a โค b โ c in a chain.
Equations
- One or more equations did not get rendered due to their size.