ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
Loading...
Searching...
No Matches
BestPath.h
Go to the documentation of this file.
1/**
2 * @file semiring/BestPath.h
3 * @brief One least-cost derivation: its cost and its word of labels.
4 *
5 * Pairs @f$(c, w)@f$ of a nonnegative cost @f$c@f$ and a word @f$w@f$
6 * over the labels of the input tuples, and @f$\mathbb{0}@f$. A value is
7 * better than another if its cost is lower or, at equal costs, if its word
8 * comes first in shortlex order (shorter first, then lexicographic over the
9 * labels, compared bytewise):
10 * - @f$a \oplus b@f$ is the better of the two, so that the values form a
11 * chain, @f$\oplus@f$ being its maximum;
12 * - @f$(c, w) \otimes (c', w') = (c + c', w \cdot w')@f$, the
13 * concatenation in the order of the query, so that this semiring does
14 * not commute;
15 * - @f$\mathbb{1} = (0, \varepsilon)@f$, the best value, and
16 * @f$\mathbb{0}@f$ the worst;
17 * - @f$a \ominus b@f$ is @f$a@f$ if @f$a@f$ is strictly better than
18 * @f$b@f$, @f$\mathbb{0}@f$ otherwise.
19 *
20 * Shortlex order is compatible with concatenation on both sides, strictly,
21 * and so is the order of costs: @f$\otimes@f$ distributes over
22 * @f$\oplus@f$ and over @f$\ominus@f$ on both sides. With
23 * @f$\mathbb{1}@f$ the best value, the semiring is absorptive on both
24 * sides (@f$a \otimes b \le a@f$ and @f$b \otimes a \le a@f$): a
25 * recursion is solved by Dijkstra's algorithm, every star being
26 * @f$\mathbb{1}@f$, and a cycle is never followed. A negative cost would
27 * break this, and is refused.
28 *
29 * Unlike @c TropicalPaths, which keeps every derivation of the least cost,
30 * this semiring keeps one, so that it needs no regular expression.
31 *
32 * @see https://provsql.org/lean-docs/Provenance/Semirings/BestPath.html
33 * Lean 4 verified m-semiring, for costs of any sign, with proofs of
34 * @c BestPath.not_commutative,
35 * @c BestPath.selective_of, @c BestPath.complemented_of,
36 * @c BestPath.mul_sub_left_distributive_of,
37 * @c BestPath.mul_sub_right_distributive_of and, for nonnegative
38 * costs only, @c BestPath.absorptive_of.
39 */
40#ifndef BEST_PATH_H
41#define BEST_PATH_H
42
43#include <limits>
44#include <string>
45#include <vector>
46
47#include "Semiring.h"
48#include "../Circuit.h"
49
50namespace semiring {
51
52/** @brief A cost and a derivation of that cost, as a word of labels. */
54 double cost = std::numeric_limits<double>::infinity(); ///< +∞ for 𝟘
55 std::vector<std::string> word; ///< Its labels
56
57 /** @brief Whether this is @f$\mathbb{0}@f$. */
58 bool is_zero() const {
59 return cost == std::numeric_limits<double>::infinity();
60 }
61 /** @brief Equality of the cost and the word. */
62 bool operator==(const best_path_t &o) const {
63 return cost == o.cost && word == o.word;
64 }
65 /** @brief Inequality. */
66 bool operator!=(const best_path_t &o) const {
67 return !(*this == o);
68 }
69};
70
71/**
72 * @brief The one-best-derivation semiring over @c best_path_t.
73 *
74 * Its leaves combine two mappings, costs and labels (see
75 * @c sr_best_path), so they are built by the caller with @c leaf.
76 */
77class BestPath : public semiring::Semiring<best_path_t>
78{
79public:
80/** @brief Whether @p a is strictly better than @p b. */
81static bool better(const best_path_t &a, const best_path_t &b) {
82 if(a.cost != b.cost)
83 return a.cost < b.cost;
84 if(a.word.size() != b.word.size())
85 return a.word.size() < b.word.size();
86 return a.word < b.word;
87}
88
89/** @brief The value of an input of cost @p cost and label @p label, no
90 * label being the empty word, and an infinite cost @f$\mathbb{0}@f$. */
91static best_path_t leaf(double cost, const std::string *label) {
92 if(!(cost >= 0.))
93 throw CircuitRefusal(
94 PROVSQL_DELIBERATE, "semiring-negative-cost",
95 "sr_best_path requires nonnegative costs: with a negative one, "
96 "the empty derivation is no longer the best, and a cycle may "
97 "improve a derivation without end.");
99 if(cost == std::numeric_limits<double>::infinity())
100 return r; // 𝟘, whatever its label
101 r.cost = cost;
102 if(label != nullptr)
103 r.word.push_back(*label);
104 return r;
105}
106
107virtual value_type zero() const override {
108 return best_path_t();
109}
110virtual value_type one() const override {
111 return best_path_t{0., {}};
112}
113virtual value_type plus(const std::vector<value_type> &v) const override {
114 value_type r;
115 for(const auto &x : v)
116 if(better(x, r))
117 r = x;
118 return r;
119}
120virtual value_type times(const std::vector<value_type> &v) const override {
121 value_type r = one();
122 for(const auto &x : v) {
123 if(x.is_zero())
124 return zero();
125 r.cost += x.cost;
126 r.word.insert(r.word.end(), x.word.begin(), x.word.end());
127 }
128 return r;
129}
130virtual value_type monus(value_type x, value_type y) const override {
131 return better(x, y) ? x : zero();
132}
133virtual value_type delta(value_type x) const override {
134 return x.is_zero() ? zero() : one();
135}
136/** @brief @f$\mathbb{1}@f$ is the best value, on both sides of a
137 * product. */
138virtual bool absorptive() const override {
139 return true;
140}
141/** @brief The sum is the better of two values. */
142virtual bool selective() const override {
143 return true;
144}
145/** @brief Concatenation does not commute. */
146virtual bool commutative() const override {
147 return false;
148}
149/**
150 * @brief @f$\otimes@f$ distributes over @f$\ominus@f$, on both sides.
151 *
152 * Read only by the HAVING evaluation, which refuses a non-commutative
153 * semiring for now.
154 *
155 * Lean: @c Provenance.Semirings.BestPath.mul_sub_left_distributive_of.
156 */
157virtual bool mul_sub_left_distributive() const override {
158 return true;
159}
160/** @brief Every star is @f$\mathbb{1}@f$, by absorption. */
161virtual value_type star(const value_type &) const override {
162 return one();
163}
164};
165
166}
167
168#endif /* BEST_PATH_H */
Generic directed-acyclic-graph circuit template and gate identifier.
Abstract semiring interface for provenance evaluation.
A refusal by design, or a known gap, rather than an error.
Definition Circuit.h:409
The one-best-derivation semiring over best_path_t.
Definition BestPath.h:78
virtual value_type monus(value_type x, value_type y) const override
Apply the monus (m-semiring difference) operation.
Definition BestPath.h:130
virtual bool absorptive() const override
is the best value, on both sides of a product.
Definition BestPath.h:138
static best_path_t leaf(double cost, const std::string *label)
The value of an input of cost cost and label label, no label being the empty word,...
Definition BestPath.h:91
virtual value_type one() const override
Return the multiplicative identity .
Definition BestPath.h:110
virtual value_type zero() const override
Return the additive identity .
Definition BestPath.h:107
virtual bool selective() const override
The sum is the better of two values.
Definition BestPath.h:142
virtual value_type delta(value_type x) const override
Apply the operator.
Definition BestPath.h:133
virtual bool mul_sub_left_distributive() const override
distributes over , on both sides.
Definition BestPath.h:157
virtual bool commutative() const override
Concatenation does not commute.
Definition BestPath.h:146
virtual value_type times(const std::vector< value_type > &v) const override
Apply the multiplicative operation to a list of values.
Definition BestPath.h:120
virtual value_type plus(const std::vector< value_type > &v) const override
Apply the additive operation to a list of values.
Definition BestPath.h:113
virtual value_type star(const value_type &) const override
Every star is , by absorption.
Definition BestPath.h:161
static bool better(const best_path_t &a, const best_path_t &b)
Whether a is strictly better than b.
Definition BestPath.h:81
Abstract base class for (m-)semirings.
Definition Semiring.h:119
#define PROVSQL_DELIBERATE
What kind of limit a refusal or a freezing is.
A cost and a derivation of that cost, as a word of labels.
Definition BestPath.h:53
double cost
+∞ for 𝟘
Definition BestPath.h:54
bool operator==(const best_path_t &o) const
Equality of the cost and the word.
Definition BestPath.h:62
bool operator!=(const best_path_t &o) const
Inequality.
Definition BestPath.h:66
bool is_zero() const
Whether this is .
Definition BestPath.h:58
std::vector< std::string > word
Its labels.
Definition BestPath.h:55