ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
Loading...
Searching...
No Matches
Tropical.h
Go to the documentation of this file.
1/**
2 * @file semiring/Tropical.h
3 * @brief Tropical (min-plus) m-semiring over @f$\mathbb{R} \cup \{+\infty\}@f$.
4 *
5 * The tropical m-semiring (@f$\mathbb{R} \cup \{+\infty\}@f$,
6 * @f$\min@f$, @f$+@f$, @f$+\infty@f$, 0) is used to model
7 * shortest-path/least-cost provenance: input gates carry edge weights
8 * (or costs), @f$\oplus = \min@f$ selects the cheapest derivation,
9 * and @f$\otimes = +@f$ accumulates cost along a derivation.
10 *
11 * Operations:
12 * - @c zero() → @f$+\infty@f$
13 * - @c one() → 0
14 * - @c plus() → minimum of all operands (empty list → @f$+\infty@f$)
15 * - @c times() → sum of all operands (empty list → 0)
16 * - @c monus() → @f$+\infty@f$ if @f$x \ge y@f$ in the usual order,
17 * @f$x@f$ otherwise (note this is the *reverse* of the
18 * natural semiring order; see Lean reference)
19 * - @c delta() → @f$+\infty@f$ if @c x is @f$+\infty@f$, else 0
20 *
21 * Absorptivity: `absorptive()` returns `false`. The Lean formalisation
22 * proves absorptivity only for canonically-ordered carriers (e.g.
23 * @f$\mathbb{N}@f$); over arbitrary @c double values (including
24 * negatives) @f$\mathbb{1} \oplus a = \min(0, a)@f$ is not always 0.
25 *
26 * @see https://provsql.org/lean-docs/Provenance/Semirings/Tropical.html
27 * Lean 4 verified instance: @c instSemiringWithMonusTropicalWithTop,
28 * with proofs of @c Tropical.absorptive (under
29 * @c CanonicallyOrderedAdd) and
30 * @c Tropical.mul_sub_left_distributive.
31 */
32#ifndef TROPICAL_H
33#define TROPICAL_H
34
35#include <algorithm>
36#include <limits>
37#include <numeric>
38#include <vector>
39
40#include "Semiring.h"
41
42namespace semiring {
43/**
44 * @brief Tropical (min-plus) m-semiring over @c double.
45 *
46 * Each gate evaluates to a real-valued cost (with @f$+\infty@f$ as
47 * the additive identity). Inputs are read from the mapping table as
48 * %float8 values; pass <tt>'Infinity'::%float8</tt> to encode the
49 * additive zero.
50 */
51class Tropical : public semiring::Semiring<double>
52{
53public:
54virtual value_type zero() const override {
55 return std::numeric_limits<double>::infinity();
56}
57virtual value_type one() const override {
58 return 0.0;
59}
60virtual value_type plus(const std::vector<value_type> &v) const override {
61 if(v.empty()) return zero();
62 return *std::min_element(v.begin(), v.end());
63}
64/** @brief @f$\min@f$ returns one of its arguments; absorptive only on
65 * nonnegative costs (@c TropicalNonneg). */
66virtual bool selective() const override {
67 return true;
68}
69/** @brief A cycle of nonnegative cost adds nothing to the best derivation
70 * (@f$a^* = 0@f$), one of negative cost makes it unbounded
71 * (@f$a^* = -\infty@f$). */
72virtual bool has_star() const override {
73 return true;
74}
75virtual value_type star(const value_type &a) const override {
76 return a >= 0 ? 0.0 : -std::numeric_limits<double>::infinity();
77}
78virtual value_type times(const std::vector<value_type> &v) const override {
79 return std::accumulate(v.begin(), v.end(), 0.0);
80}
81virtual value_type monus(value_type x, value_type y) const override
82{
83 return x>=y ? zero() : x;
84}
85virtual value_type delta(value_type x) const override
86{
87 return x==zero() ? zero() : one();
88}
89/**
90 * @brief @f$\otimes@f$ distributes over @f$\ominus@f$, so the HAVING
91 * @c MIN / @c MAX comparisons take the single-scan closed form
92 * (inherited by @c TropicalNonneg, the absorptive case where the
93 * scan applies).
94 *
95 * Lean: @c Provenance.Semirings.TropicalR.mul_sub_left_distributive (the
96 * real-valued instance of @c Tropical.mul_sub_left_distributive).
97 */
98virtual bool mul_sub_left_distributive() const override {
99 return true;
100}
101/**
102 * @brief No semiring homomorphism @c BoolFunc(Y) →+* Tropical exists
103 * (the min-plus structure cannot be made Boolean-functions
104 * compatible), so the safe-query Boolean rewrite is unsound
105 * under the tropical semiring. Inherits the @c false default
106 * from @c Semiring; this override exists for documentation.
107 *
108 * Lean: @c Provenance.Semirings.TropicalN.no_hom_from_BoolFunc
109 * (provenance-lean/Provenance/Semirings/Tropical.lean).
110 */
111virtual bool compatibleWithBooleanRewrite() const override {
112 return false;
113}
114value_type parse_leaf(const char *v) const {
115 return atof(v);
116}
117
118};
119
120/**
121 * @brief Tropical (min-plus) m-semiring restricted to *nonnegative*
122 * costs.
123 *
124 * Over @f$\mathbb{R}_{\ge 0} \cup \{+\infty\}@f$ the tropical semiring
125 * is absorptive (@f$\min(0, a) = 0@f$ for @f$a \ge 0@f$) -- the
126 * canonically-ordered case the Lean formalisation proves
127 * (@c Tropical.absorptive under @c CanonicallyOrderedAdd). Declaring
128 * it lets min-plus evaluation accept circuits carrying the
129 * @c 'absorptive' assumption marker -- notably the reachability
130 * circuits of the bounded-treewidth route, whose minimal derivations
131 * determine the min-cost exactly (negative costs would
132 * make cyclic min-cost genuinely unbounded, which is why the
133 * unrestricted @c Tropical declines). Negative input costs are
134 * rejected at leaf-parsing time.
135 */
136class TropicalNonneg : public Tropical {
137public:
138virtual bool absorptive() const override {
139 return true;
140}
141value_type parse_leaf(const char *v) const {
142 const value_type x = atof(v);
143 if (x < 0)
144 throw SemiringException(
145 "the nonnegative tropical semiring requires nonnegative "
146 "costs (use sr_tropical without nonnegative => true for "
147 "arbitrary costs, on acyclic provenance only)");
148 return x;
149}
150};
151}
152
153#endif /* TROPICAL_H */
Abstract semiring interface for provenance evaluation.
Exception thrown when a semiring operation is not supported.
Definition Semiring.h:55
Abstract base class for (m-)semirings.
Definition Semiring.h:119
Tropical (min-plus) m-semiring restricted to nonnegative costs.
Definition Tropical.h:136
virtual bool absorptive() const override
Return true if this semiring is absorptive ( for all ).
Definition Tropical.h:138
value_type parse_leaf(const char *v) const
Definition Tropical.h:141
Tropical (min-plus) m-semiring over double.
Definition Tropical.h:52
virtual value_type plus(const std::vector< value_type > &v) const override
Apply the additive operation to a list of values.
Definition Tropical.h:60
value_type parse_leaf(const char *v) const
Definition Tropical.h:114
virtual bool selective() const override
returns one of its arguments; absorptive only on nonnegative costs (TropicalNonneg).
Definition Tropical.h:66
virtual bool has_star() const override
A cycle of nonnegative cost adds nothing to the best derivation ( ), one of negative cost makes it un...
Definition Tropical.h:72
virtual bool compatibleWithBooleanRewrite() const override
No semiring homomorphism BoolFunc(Y) →+* Tropical exists (the min-plus structure cannot be made Boole...
Definition Tropical.h:111
virtual value_type star(const value_type &a) const override
, the sum of the powers of a.
Definition Tropical.h:75
virtual value_type delta(value_type x) const override
Apply the operator.
Definition Tropical.h:85
virtual bool mul_sub_left_distributive() const override
distributes over , so the HAVING MIN / MAX comparisons take the single-scan closed form (inherited by...
Definition Tropical.h:98
virtual value_type monus(value_type x, value_type y) const override
Apply the monus (m-semiring difference) operation.
Definition Tropical.h:81
virtual value_type one() const override
Return the multiplicative identity .
Definition Tropical.h:57
virtual value_type zero() const override
Return the additive identity .
Definition Tropical.h:54
virtual value_type times(const std::vector< value_type > &v) const override
Apply the multiplicative operation to a list of values.
Definition Tropical.h:78