ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
Loading...
Searching...
No Matches
Subset.h
Go to the documentation of this file.
1/**
2 * @file semiring/Subset.h
3 * @brief The Boolean algebra of the subsets of a PostgreSQL @c enum type.
4 *
5 * An annotation is a set of labels of a user enum (at most 63 of them),
6 * stored as a bitmask: bit @f$i@f$ stands for the label of rank @f$i@f$ in
7 * @c pg_enum.enumsortorder. The operations are those of the powerset
8 * Boolean algebra:
9 * - @c zero() → the empty set
10 * - @c one() → every label (and, for consent, the unrestricted element)
11 * - @c plus() → union
12 * - @c times() → intersection
13 * - @c monus() → set difference
14 * - @c delta() → identity
15 *
16 * Evaluating a circuit here is evaluating it in every one of the worlds the
17 * labels stand for at once: the annotation of a result is the set of labels
18 * whose world contains it. Three front-ends read the labels differently,
19 * selected by @c Mode:
20 * - @c SUBSET: a mapping value is a set of labels (an enum array), or a
21 * single label standing for itself;
22 * - @c CLEARANCE: the labels are clearance levels in increasing order, and a
23 * single label stands for itself and every level above it (the levels at
24 * which a tuple of that clearance may be seen); an array is any set
25 * (compartments);
26 * - @c CONSENT: the labels are purposes, a mapping value is the set of
27 * purposes a tuple is consented for, and every tuple also belongs to the
28 * unrestricted world, an extra element (bit 63) standing for the whole
29 * database.
30 *
31 * Being a Boolean algebra, the semiring is absorptive, idempotent for both
32 * operations, exclusive, and its product distributes over its monus: every
33 * property the evaluators look for holds, so negation (@c EXCEPT,
34 * @c NOT @c EXISTS) gets its exact reading, which a single level
35 * (@c MinMax) cannot represent.
36 */
37#ifndef SUBSET_H
38#define SUBSET_H
39
40extern "C" {
41#include "postgres.h"
42#include "fmgr.h"
43#include "catalog/pg_enum.h"
44#include "catalog/pg_type.h"
45#include "utils/array.h"
46#include "utils/catcache.h"
47#include "utils/syscache.h"
48#include "utils/lsyscache.h"
49#include "access/htup_details.h"
50}
51
52#include <algorithm>
53#include <cstdint>
54#include <stdexcept>
55#include <string>
56#include <unordered_map>
57#include <utility>
58#include <vector>
59
60#include "Semiring.h"
61
62namespace semiring {
63
64/** @brief The labels of an enum type, in @c enumsortorder: their OIDs, and
65 * the rank of each OID. */
66struct EnumLabels {
67 std::vector<Oid> oids; ///< label OIDs, by rank
68 std::unordered_map<Oid, unsigned> rank; ///< rank of each label OID
69
70 explicit EnumLabels(Oid enum_oid) {
71 CatCList *list = SearchSysCacheList1(ENUMTYPOIDNAME, ObjectIdGetDatum(enum_oid));
72 std::vector<std::pair<float4, Oid> > labels;
73 for(int i = 0; i < list->n_members; ++i) {
74 HeapTuple tup = &list->members[i]->tuple;
75 Form_pg_enum en = (Form_pg_enum) GETSTRUCT(tup);
76#if PG_VERSION_NUM >= 120000
77 Oid label_oid = en->oid;
78#else
79 Oid label_oid = HeapTupleGetOid(tup);
80#endif
81 labels.emplace_back(en->enumsortorder, label_oid);
82 }
83 ReleaseCatCacheList(list);
84 std::sort(labels.begin(), labels.end());
85 for(const auto &l : labels) {
86 rank.emplace(l.second, oids.size());
87 oids.push_back(l.second);
88 }
89 }
90};
91
92/**
93 * @brief Subsets of the labels of an enum type, as a 64-bit mask.
94 */
95class Subset : public semiring::Semiring<uint64_t>
96{
97public:
98/** @brief How a mapping value is read (see the file comment). */
99enum class Mode { SUBSET, CLEARANCE, CONSENT };
100
101/** @brief The bit of the unrestricted world, in @c CONSENT mode. */
102static constexpr uint64_t UNRESTRICTED = uint64_t(1) << 63;
103
104private:
108uint64_t universe;
110
111uint64_t bit_of(Oid label) const {
112 auto it = labels.rank.find(label);
113 if(it == labels.rank.end())
114 throw std::runtime_error("Subset: value is not a label of the enum type");
115 return uint64_t(1) << it->second;
116}
117
118public:
119Subset(Oid enum_type_oid, Mode mode_)
120 : enum_oid(enum_type_oid), mode(mode_), labels(enum_type_oid)
121{
122 const std::size_t n = labels.oids.size();
123 if(n == 0)
124 throw std::runtime_error("Subset: enum type has no labels");
125 if(n > 63)
126 throw std::runtime_error("Subset: an enum type of at most 63 labels is "
127 "supported, one bit per label");
128 universe = n == 64 ? ~uint64_t(0) : (uint64_t(1) << n) - 1;
129 if(mode == Mode::CONSENT)
131
132 getTypeInputInfo(enum_oid, &in_func, &typioparam);
133 Oid array_type = get_array_type(enum_oid);
134 if(!OidIsValid(array_type))
135 throw std::runtime_error("Subset: enum type has no array type");
136 getTypeInputInfo(array_type, &array_in_func, &array_typioparam);
137}
138
139/** @brief The labels, in @c enumsortorder. */
140const std::vector<Oid> &label_oids() const {
141 return labels.oids;
142}
143
144virtual value_type zero() const override {
145 return 0;
146}
147virtual value_type one() const override {
148 return universe;
149}
150virtual value_type plus(const std::vector<value_type> &v) const override {
151 value_type r = 0;
152 for(auto x : v) r |= x;
153 return r;
154}
155virtual value_type times(const std::vector<value_type> &v) const override {
157 for(auto x : v) r &= x;
158 return r;
159}
160virtual value_type monus(value_type x, value_type y) const override {
161 return x & ~y;
162}
163virtual value_type delta(value_type x) const override {
164 return x;
165}
166virtual bool absorptive() const override {
167 return true;
168}
169virtual bool exclusive() const override {
170 return true;
171}
172virtual bool mul_idempotent() const override {
173 return true;
174}
175virtual bool mul_sub_left_distributive() const override {
176 return true;
177}
178/** @brief A Boolean algebra receives a homomorphism from the Boolean
179 * functions, so the safe-query rewriting is sound here. */
180virtual bool compatibleWithBooleanRewrite() const override {
181 return true;
182}
183
184/**
185 * @brief Parse a mapping value: a single label, or an array of labels.
186 *
187 * In @c CLEARANCE mode a single label stands for itself and every label
188 * above it; in @c CONSENT mode the unrestricted element is added to every
189 * value.
190 */
191value_type parse_leaf(const char *str) const {
192 uint64_t r = 0;
193 if(str[0] == '{') {
194 Datum arr = OidInputFunctionCall(array_in_func, const_cast<char *>(str),
195 array_typioparam, -1);
196 ArrayType *a = DatumGetArrayTypeP(arr);
197 Datum *elems;
198 bool *nulls;
199 int nelems;
200 int16 typlen;
201 bool typbyval;
202 char typalign;
203 get_typlenbyvalalign(enum_oid, &typlen, &typbyval, &typalign);
204 deconstruct_array(a, enum_oid, typlen, typbyval, typalign,
205 &elems, &nulls, &nelems);
206 for(int i = 0; i < nelems; ++i)
207 if(!nulls[i])
208 r |= bit_of(DatumGetObjectId(elems[i]));
209 } else {
210 Oid label = DatumGetObjectId(
211 OidInputFunctionCall(in_func, const_cast<char *>(str), typioparam, -1));
212 r = bit_of(label);
213 if(mode == Mode::CLEARANCE)
214 r = (universe & ~(r - 1)); // this level and every one above
215 }
216 if(mode == Mode::CONSENT)
217 r |= UNRESTRICTED;
218 return r;
219}
220
221};
222
223}
224
225#endif /* SUBSET_H */
Abstract semiring interface for provenance evaluation.
Abstract base class for (m-)semirings.
Definition Semiring.h:119
virtual bool absorptive() const override
Return true if this semiring is absorptive ( for all ).
Definition Subset.h:166
EnumLabels labels
Definition Subset.h:107
virtual bool mul_idempotent() const override
Return true if is idempotent: .
Definition Subset.h:172
virtual value_type monus(value_type x, value_type y) const override
Apply the monus (m-semiring difference) operation.
Definition Subset.h:160
virtual value_type times(const std::vector< value_type > &v) const override
Apply the multiplicative operation to a list of values.
Definition Subset.h:155
virtual bool exclusive() const override
Return true if the semiring is exclusive: .
Definition Subset.h:169
Mode
How a mapping value is read (see the file comment).
Definition Subset.h:99
Subset(Oid enum_type_oid, Mode mode_)
Definition Subset.h:119
Oid array_typioparam
Definition Subset.h:109
value_type parse_leaf(const char *str) const
Parse a mapping value: a single label, or an array of labels.
Definition Subset.h:191
virtual value_type plus(const std::vector< value_type > &v) const override
Apply the additive operation to a list of values.
Definition Subset.h:150
virtual value_type zero() const override
Return the additive identity .
Definition Subset.h:144
virtual value_type one() const override
Return the multiplicative identity .
Definition Subset.h:147
virtual bool mul_sub_left_distributive() const override
Return true if distributes over the monus on the left: for all .
Definition Subset.h:175
static constexpr uint64_t UNRESTRICTED
The bit of the unrestricted world, in CONSENT mode.
Definition Subset.h:102
uint64_t universe
Definition Subset.h:108
virtual value_type delta(value_type x) const override
Apply the operator.
Definition Subset.h:163
const std::vector< Oid > & label_oids() const
The labels, in enumsortorder.
Definition Subset.h:140
virtual bool compatibleWithBooleanRewrite() const override
A Boolean algebra receives a homomorphism from the Boolean functions, so the safe-query rewriting is ...
Definition Subset.h:180
uint64_t bit_of(Oid label) const
Definition Subset.h:111
The labels of an enum type, in enumsortorder: their OIDs, and the rank of each OID.
Definition Subset.h:66
EnumLabels(Oid enum_oid)
Definition Subset.h:70
std::vector< Oid > oids
label OIDs, by rank
Definition Subset.h:67
std::unordered_map< Oid, unsigned > rank
rank of each label OID
Definition Subset.h:68