ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
Loading...
Searching...
No Matches
TropicalPaths.h
Go to the documentation of this file.
1/**
2 * @file semiring/TropicalPaths.h
3 * @brief Min-cost derivations with the derivations of that cost.
4 *
5 * Pairs @f$(c, L)@f$ of a cost @f$c \in \mathbb{R} \cup \{+\infty\}@f$
6 * and a language @f$L@f$ over the labels of the input tuples, the
7 * derivations of cost @f$c@f$, written as a regular expression (@c
8 * Regex.h):
9 * - @f$(c, L) \oplus (c', L')@f$ keeps the lower cost, with its
10 * derivations, and both languages' union on a tie;
11 * - @f$(c, L) \otimes (c', L') = (c + c', L \cdot L')@f$, the
12 * concatenation in the order of the query, so that this semiring does
13 * not commute;
14 * - @f$\mathbb{0} = (+\infty, \emptyset)@f$, @f$\mathbb{1} = (0,
15 * \{\varepsilon\})@f$.
16 *
17 * On a path query, the value of a tuple is the cost of its shortest paths
18 * and those paths. A cycle of positive cost never lies on a shortest path
19 * (@f$(c, L)^* = \mathbb{1}@f$); one of cost zero can be followed any
20 * number of times at no cost (@f$(0, L)^* = (0, L^*)@f$), which a regular
21 * expression still writes finitely; one of negative cost makes the cost
22 * unbounded, and is refused.
23 *
24 * @see https://provsql.org/lean-docs/Provenance/Semirings/TropicalPaths.html
25 * Lean 4 verified m-semiring, whose monus (@c TropicalPaths.monus, a
26 * difference of languages on a tie of costs) this implementation does
27 * not compute; with proofs of
28 * @c TropicalPaths.not_commutative, @c TropicalPaths.not_exclusive,
29 * of the stars (@c TropicalPaths.one_add_mul_one_of_pos,
30 * @c TropicalPaths.one_add_mul_kstar) and of the absence of any
31 * solution on a cycle of negative cost
32 * (@c TropicalPaths.no_fixpoint_of_neg).
33 */
34#ifndef TROPICAL_PATHS_H
35#define TROPICAL_PATHS_H
36
37#include <limits>
38#include <string>
39#include <vector>
40
41#include "Regex.h"
42
43namespace semiring {
44
45/** @brief A cost, and the derivations of that cost. */
47 double cost = std::numeric_limits<double>::infinity(); ///< Least cost
48 regex_t paths; ///< Its derivations
49
50 /** @brief Syntactic equality, as for @c regex_t. */
51 bool operator==(const tropical_paths_t &o) const {
52 return cost == o.cost && paths == o.paths;
53 }
54 /** @brief Syntactic inequality. */
55 bool operator!=(const tropical_paths_t &o) const {
56 return !(*this == o);
57 }
58};
59
60/**
61 * @brief The min-cost-paths semiring over @c tropical_paths_t.
62 *
63 * Its leaves combine two mappings, costs and labels (see
64 * @c sr_tropical_paths), so they are built by the caller rather than
65 * parsed from one mapping value.
66 */
67class TropicalPaths : public semiring::Semiring<tropical_paths_t>
68{
69public:
70virtual value_type zero() const override {
71 return tropical_paths_t();
72}
73virtual value_type one() const override {
74 return tropical_paths_t{0., regex_ops::atom("")};
75}
76virtual value_type plus(const std::vector<value_type> &v) const override {
77 value_type r;
78 for(const auto &x : v)
79 if(x.cost < r.cost)
80 r.cost = x.cost;
81 if(r.cost == zero().cost)
82 return zero();
83 std::vector<regex_t> best;
84 for(const auto &x : v)
85 if(x.cost == r.cost)
86 best.push_back(x.paths);
87 r.paths = regex_ops::plus(best);
88 return r;
89}
90virtual value_type times(const std::vector<value_type> &v) const override {
91 value_type r = one();
92 std::vector<regex_t> words;
93 for(const auto &x : v) {
94 if(x.cost == zero().cost || x.paths.kind() == regex_t::EMPTY)
95 return zero();
96 r.cost += x.cost;
97 words.push_back(x.paths);
98 }
99 r.paths = regex_ops::times(words);
100 return r;
101}
102virtual value_type monus(value_type, value_type) const override {
103 throw CircuitRefusal(
104 PROVSQL_GAP, "semiring-no-monus",
105 "The min-cost-paths semiring computes no monus (outer joins, "
106 "EXCEPT and NOT EXISTS need one): on a tie of costs, its monus "
107 "is a difference of languages, which needs automata to "
108 "compute, and it would not register an absence (1 minus a "
109 "positive cost is 1).");
110}
111virtual value_type delta(value_type x) const override {
112 return x.cost == zero().cost ? zero() : one();
113}
114/** @brief A tie keeps the union of the derivations, itself idempotent. */
115virtual bool idempotent() const override {
116 return true;
117}
118/** @brief Concatenation does not commute. */
119virtual bool commutative() const override {
120 return false;
121}
122/** @brief Every value of nonnegative cost has a star. */
123virtual bool has_star() const override {
124 return true;
125}
126virtual value_type star(const value_type &a) const override {
127 if(a.cost > 0)
128 return one();
129 if(a.cost == 0)
131 throw CircuitRefusal(
132 PROVSQL_DELIBERATE, "recursion-cycle-no-value",
133 "A cycle of negative cost makes the least cost unbounded, with no "
134 "shortest derivation.");
135}
136/** @brief Equality of the derivations is syntactic. */
137virtual bool exact_equality() const override {
138 return false;
139}
140};
141
142}
143
144#endif /* TROPICAL_PATHS_H */
Regular-expression semiring: the derivations of a tuple as a language over the labels of its input tu...
A refusal by design, or a known gap, rather than an error.
Definition Circuit.h:409
Abstract base class for (m-)semirings.
Definition Semiring.h:119
The min-cost-paths semiring over tropical_paths_t.
virtual bool has_star() const override
Every value of nonnegative cost has a star.
virtual value_type times(const std::vector< value_type > &v) const override
Apply the multiplicative operation to a list of values.
virtual value_type monus(value_type, value_type) const override
Apply the monus (m-semiring difference) operation.
virtual value_type zero() const override
Return the additive identity .
virtual value_type one() const override
Return the multiplicative identity .
virtual value_type delta(value_type x) const override
Apply the operator.
virtual value_type star(const value_type &a) const override
, the sum of the powers of a.
virtual value_type plus(const std::vector< value_type > &v) const override
Apply the additive operation to a list of values.
virtual bool exact_equality() const override
Equality of the derivations is syntactic.
virtual bool commutative() const override
Concatenation does not commute.
virtual bool idempotent() const override
A tie keeps the union of the derivations, itself idempotent.
#define PROVSQL_GAP
#define PROVSQL_DELIBERATE
What kind of limit a refusal or a freezing is.
static regex_t atom(const std::string &label)
A one-letter language; for an empty label.
Definition Regex.h:180
static regex_t plus(const std::vector< regex_t > &v)
The union of v.
Definition Regex.h:185
static regex_t star(const regex_t &a)
The Kleene star of a.
Definition Regex.h:246
static regex_t times(const std::vector< regex_t > &v)
The concatenation of v, in this order.
Definition Regex.h:223
A regular expression: an immutable tree, shared between the expressions built from it.
Definition Regex.h:63
A cost, and the derivations of that cost.
bool operator==(const tropical_paths_t &o) const
Syntactic equality, as for regex_t.
regex_t paths
Its derivations.
bool operator!=(const tropical_paths_t &o) const
Syntactic inequality.