ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
Loading...
Searching...
No Matches
Counting.h
Go to the documentation of this file.
1/**
2 * @file semiring/Counting.h
3 * @brief Counting semiring (ℕ, +, ×, 0, 1).
4 *
5 * The counting semiring (@f$\mathbb{N}@f$, @f$+@f$, @f$\times@f$, 0, 1)
6 * counts the number of distinct derivations (proof witnesses) of each
7 * query result tuple.
8 *
9 * Operations:
10 * - @c zero() → 0
11 * - @c one() → 1
12 * - @c plus() → sum of all operands
13 * - @c times() → product of all operands
14 * - @c monus() → truncated subtraction: max(0, x − y)
15 * - @c delta() → 1 if x ≠ 0, else 0
16 *
17 * This semiring is **not** absorptive.
18 *
19 * @see https://provsql.org/lean-docs/Provenance/Semirings/Nat.html
20 * Lean 4 verified instance: @c instSemiringWithMonusNat, with
21 * proofs of @c Nat.mul_sub_left_distributive, @c Nat.not_idempotent,
22 * and @c Nat.not_absorptive.
23 */
24#ifndef COUNTING_H
25#define COUNTING_H
26
27#include <cstdlib>
28#include <limits>
29#include <numeric>
30#include <vector>
31#include <stdexcept>
32
33#include "Semiring.h"
34
35namespace semiring {
36/**
37 * @brief The counting semiring over @c unsigned.
38 *
39 * Each gate evaluates to the number of distinct derivations of the
40 * corresponding sub-formula.
41 */
42class Counting : public semiring::Semiring<unsigned>
43{
44public:
45/** @brief @f$\infty@f$: the count of a tuple derived through a cycle.
46 * @f$0 \cdot \infty = 0@f$, and @f$\infty@f$ absorbs every other sum
47 * and product. A finite count reaching it is an overflow, refused. */
48static constexpr value_type INFINITE = std::numeric_limits<value_type>::max();
49
50virtual value_type zero() const override {
51 return 0;
52}
53virtual value_type one() const override {
54 return 1;
55}
56virtual value_type plus(const std::vector<value_type> &v) const override {
57 value_type r = 0;
58 for(const auto x : v) {
59 if(x == INFINITE || r == INFINITE) {
60 r = INFINITE;
61 continue;
62 }
63 if(x >= INFINITE - r)
64 throw SemiringException("The number of derivations exceeds the counting range.");
65 r += x;
66 }
67 return r;
68}
69virtual value_type times(const std::vector<value_type> &v) const override {
70 value_type r = 1;
71 bool infinite = false;
72 for(const auto x : v) {
73 if(x == 0)
74 return 0;
75 if(x == INFINITE) {
76 infinite = true;
77 continue;
78 }
79 if(!infinite && r > (INFINITE - 1) / x)
80 throw SemiringException("The number of derivations exceeds the counting range.");
81 if(!infinite)
82 r *= x;
83 }
84 return infinite ? INFINITE : r;
85}
86virtual value_type monus(value_type x, value_type y) const override
87{
88 if(x == INFINITE)
89 return y == INFINITE ? 0 : INFINITE;
90 return x<=y ? 0 : x-y;
91}
92/** @brief @f$0^* = 1@f$; any other count repeats without end. */
93virtual bool has_star() const override {
94 return true;
95}
96virtual value_type star(const value_type &a) const override {
97 return a == 0 ? 1 : INFINITE;
98}
99virtual value_type delta(value_type x) const override
100{
101 return x!=0 ? 1 : 0;
102}
103/** @brief Exclusive: @f$a \otimes (\mathbb{1} \ominus a) = \mathbb{0}@f$
104 * (Lean @c Nat.exclusive); @f$\otimes@f$ is not idempotent
105 * (@c Nat.not_mulIdempotent). */
106virtual bool exclusive() const override {
107 return true;
108}
109/**
110 * @brief @f$\otimes@f$ distributes over @f$\ominus@f$ (truncated
111 * subtraction on the naturals). Recorded for completeness: the
112 * HAVING single-scan closed form also needs absorptivity, which
113 * the counting semiring lacks.
114 *
115 * Lean: @c Provenance.Semirings.Nat.mul_sub_left_distributive.
116 */
117virtual bool mul_sub_left_distributive() const override {
118 return true;
119}
120/**
121 * @brief No semiring homomorphism @c BoolFunc(X) →+* ℕ exists: any
122 * such map would force @c 1 + a = 1 in ℕ (from @c var + 1 = 1
123 * in @c BoolFunc), contradicting the non-absorptivity of ℕ.
124 * The safe-query Boolean rewrite is therefore unsound under
125 * the counting semiring (read-once factoring loses derivation
126 * multiplicities). Inherits the @c false default from
127 * @c Semiring; this override exists for documentation.
128 *
129 * Lean: @c Provenance.Semirings.Nat.no_hom_from_BoolFunc
130 * (provenance-lean/Provenance/Semirings/Nat.lean).
131 */
132virtual bool compatibleWithBooleanRewrite() const override {
133 return false;
134}
135value_type parse_leaf(const char *v) const {
136 return atoi(v);
137}
138
139};
140}
141
142#endif /* COUNTING_H */
Abstract semiring interface for provenance evaluation.
The counting semiring over unsigned.
Definition Counting.h:43
virtual value_type zero() const override
Return the additive identity .
Definition Counting.h:50
virtual value_type plus(const std::vector< value_type > &v) const override
Apply the additive operation to a list of values.
Definition Counting.h:56
static constexpr value_type INFINITE
: the count of a tuple derived through a cycle.
Definition Counting.h:48
virtual bool mul_sub_left_distributive() const override
distributes over (truncated subtraction on the naturals).
Definition Counting.h:117
value_type parse_leaf(const char *v) const
Definition Counting.h:135
virtual value_type times(const std::vector< value_type > &v) const override
Apply the multiplicative operation to a list of values.
Definition Counting.h:69
virtual bool has_star() const override
; any other count repeats without end.
Definition Counting.h:93
virtual bool exclusive() const override
Exclusive: (Lean Nat.exclusive); is not idempotent (Nat.not_mulIdempotent).
Definition Counting.h:106
virtual value_type star(const value_type &a) const override
, the sum of the powers of a.
Definition Counting.h:96
virtual bool compatibleWithBooleanRewrite() const override
No semiring homomorphism BoolFunc(X) →+* ℕ exists: any such map would force 1 + a = 1 in ℕ (from var ...
Definition Counting.h:132
virtual value_type one() const override
Return the multiplicative identity .
Definition Counting.h:53
virtual value_type monus(value_type x, value_type y) const override
Apply the monus (m-semiring difference) operation.
Definition Counting.h:86
virtual value_type delta(value_type x) const override
Apply the operator.
Definition Counting.h:99
Exception thrown when a semiring operation is not supported.
Definition Semiring.h:55
Abstract base class for (m-)semirings.
Definition Semiring.h:119