ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
Loading...
Searching...
No Matches
BestPath.h File Reference

One least-cost derivation: its cost and its word of labels. More...

#include <limits>
#include <string>
#include <vector>
#include "Semiring.h"
#include "../Circuit.h"
Include dependency graph for BestPath.h:
This graph shows which files directly or indirectly include this file:

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

Detailed Description

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):

  • \(a \oplus b\) is the better of the two, so that the values form a chain, \(\oplus\) being its maximum;
  • \((c, w) \otimes (c', w') = (c + c', w \cdot w')\), the concatenation in the order of the query, so that this semiring does not commute;
  • \(\mathbb{1} = (0, \varepsilon)\), the best value, and \(\mathbb{0}\) the worst;
  • \(a \ominus b\) is \(a\) if \(a\) is strictly better than \(b\), \(\mathbb{0}\) otherwise.

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.

See also
https://provsql.org/lean-docs/Provenance/Semirings/BestPath.html Lean 4 verified m-semiring, for costs of any sign, with proofs of 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.