![]() |
ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
|
Min-cost derivations with the derivations of that cost. More...


Go to the source code of this file.
Classes | |
| struct | semiring::tropical_paths_t |
| A cost, and the derivations of that cost. More... | |
| class | semiring::TropicalPaths |
The min-cost-paths semiring over tropical_paths_t. More... | |
Namespaces | |
| namespace | semiring |
Min-cost derivations with the derivations of that cost.
Pairs \((c, L)\) of a cost \(c \in \mathbb{R} \cup \{+\infty\}\) and a language \(L\) over the labels of the input tuples, the derivations of cost \(c\), written as a regular expression (Regex.h):
On a path query, the value of a tuple is the cost of its shortest paths and those paths. A cycle of positive cost never lies on a shortest path ( \((c, L)^* = \mathbb{1}\)); one of cost zero can be followed any number of times at no cost ( \((0, L)^* = (0, L^*)\)), which a regular expression still writes finitely; one of negative cost makes the cost unbounded, and is refused.
TropicalPaths.monus, a difference of languages on a tie of costs) this implementation does not compute; with proofs of TropicalPaths.not_commutative, TropicalPaths.not_exclusive, of the stars (TropicalPaths.one_add_mul_one_of_pos, TropicalPaths.one_add_mul_kstar) and of the absence of any solution on a cycle of negative cost (TropicalPaths.no_fixpoint_of_neg). Definition in file TropicalPaths.h.