![]() |
ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
|
One least-cost derivation: its cost and its word of labels. More...


Go to the source code of this file.
Classes | |
| struct | semiring::best_path_t |
| A cost and a derivation of that cost, as a word of labels. More... | |
| class | semiring::BestPath |
The one-best-derivation semiring over best_path_t. More... | |
Namespaces | |
| namespace | semiring |
One least-cost derivation: its cost and its word of labels.
Pairs \((c, w)\) of a nonnegative cost \(c\) and a word \(w\) over the labels of the input tuples, and \(\mathbb{0}\). A value is better than another if its cost is lower or, at equal costs, if its word comes first in shortlex order (shorter first, then lexicographic over the labels, compared bytewise):
Shortlex order is compatible with concatenation on both sides, strictly, and so is the order of costs: \(\otimes\) distributes over \(\oplus\) and over \(\ominus\) on both sides. With \(\mathbb{1}\) the best value, the semiring is absorptive on both sides ( \(a \otimes b \le a\) and \(b \otimes a \le a\)): a recursion is solved by Dijkstra's algorithm, every star being \(\mathbb{1}\), and a cycle is never followed. A negative cost would break this, and is refused.
Unlike TropicalPaths, which keeps every derivation of the least cost, this semiring keeps one, so that it needs no regular expression.
BestPath.not_commutative, BestPath.selective_of, BestPath.complemented_of, BestPath.mul_sub_left_distributive_of, BestPath.mul_sub_right_distributive_of and, for nonnegative costs only, BestPath.absorptive_of. Definition in file BestPath.h.