ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
Loading...
Searching...
No Matches
fix_system.cpp
Go to the documentation of this file.
1/**
2 * @file fix_system.cpp
3 * @brief Resolution of the equation system of a recursive query.
4 *
5 * @c eval_recursive_system records a recursion as one equation per derived
6 * tuple, x_i = f_i(x), gathered in a @c gate_fixsystem. Only the tuples
7 * derived through themselves need an unknown: a tuple outside every cycle
8 * of the dependency graph has a value that its right-hand side gives once
9 * the tuples it reads have theirs. @c resolve_fix_system walks the
10 * strongly connected components of that graph in solving order and gives
11 * each tuple its final token:
12 *
13 * - a tuple outside every cycle gets its right-hand side rebuilt with the
14 * unknowns replaced by the tokens of the tuples they stand for, by the
15 * rewriter's own gate builders: the gates, and their content addresses,
16 * are those a fixpoint iteration of the recursion would reach;
17 * - the tuples of a cyclic component get a @c gate_fixsystem of their own,
18 * whose right-hand sides read the tokens already resolved, and each a
19 * @c gate_fixpoint over it, solved at evaluation time.
20 *
21 * A right-hand side with a gate the builders cannot rebuild leaves the
22 * system as it was: one @c gate_fixpoint per tuple over the whole system,
23 * which evaluation solves all the same.
24 */
25extern "C" {
26#include "postgres.h"
27#include "fmgr.h"
28#include "catalog/pg_type.h"
29#include "utils/array.h"
30#include "utils/uuid.h"
31#include "provsql_utils.h"
32#include "provsql_mmap.h"
33#include "gate_builders.h"
34
35PG_FUNCTION_INFO_V1(resolve_fix_system);
36}
37
38#include <algorithm>
39#include <functional>
40#include <string>
41#include <unordered_map>
42#include <vector>
43
45#include "CircuitFromMMap.h"
46#include "FixSystemGraph.h"
47#include "GenericCircuit.h"
48#include "provsql_interrupt.h"
49#include "provsql_utils_cpp.h"
50
51namespace {
52
53/** A gate the rewriter's builders cannot rebuild. */
54struct NotRebuildable {};
55
56/** Address of the @c gate_fixpoint reading component @p i (1-based) of
57 * system @p sys; the same as the SQL @c fixpoint_token. */
58pg_uuid_t fixpoint_address(const pg_uuid_t &sys, std::size_t i)
59{
60 return provsqlUuidV5("fixpoint:" + uuid2string(sys) + ":" +
61 std::to_string(i));
62}
63
64/** Create a system over @p unknowns and @p rhs, and its fixpoint gates;
65 * @return the address of each fixpoint gate, in order. */
66std::vector<pg_uuid_t> make_system(const std::vector<pg_uuid_t> &unknowns,
67 const std::vector<pg_uuid_t> &rhs)
68{
69 std::vector<pg_uuid_t> wires(unknowns);
70 wires.insert(wires.end(), rhs.begin(), rhs.end());
71 std::string name = "fixsystem{";
72 for(std::size_t k = 0; k < wires.size(); ++k)
73 name += (k ? "," : "") + uuid2string(wires[k]);
74 name += "}";
75 const pg_uuid_t sys = provsqlUuidV5(name);
77 wires.data());
78
79 std::vector<pg_uuid_t> result;
80 for(std::size_t k = 0; k < unknowns.size(); ++k) {
81 const pg_uuid_t p = fixpoint_address(sys, k + 1);
83 k + 1, 0, nullptr);
84 result.push_back(p);
85 }
86 return result;
87}
88
89std::vector<pg_uuid_t> resolve(pg_uuid_t sys_token)
90{
91 /* The circuit as stored: the load-time simplifications would rewrite the
92 * right-hand sides, which are to be rebuilt as the rewriter built them. */
93 const bool s1 = provsql_simplify_on_load;
94 const bool s2 = provsql_boolean_provenance;
95 const bool s3 = provsql_absorptive_provenance;
100 try {
101 c = getGenericCircuit(sys_token);
102 } catch(...) {
106 throw;
107 }
111
112 const gate_t sys = c.getGate(uuid2string(sys_token));
113 const auto &w = c.getWires(sys);
114 const std::size_t n = w.size() / 2;
115
116 std::unordered_map<gate_t, std::size_t> unknown;
117 for(std::size_t i = 0; i < n; ++i)
118 unknown.emplace(w[i], i);
119
120 /* For each gate depending on an unknown, the unknowns it reads (an
121 * iterative post-order: the sub-circuits that read none can be as deep
122 * as the data). */
123 std::unordered_map<gate_t, std::vector<std::size_t> > reads;
124 std::unordered_map<gate_t, bool> dep;
125 {
126 std::vector<gate_t> st(w.begin() + n, w.end());
127 while(!st.empty()) {
128 const gate_t u = st.back();
129 if(dep.count(u)) { st.pop_back(); continue; }
130 auto it = unknown.find(u);
131 if(it != unknown.end()) {
132 dep.emplace(u, true);
133 reads[u] = {it->second};
134 st.pop_back();
135 continue;
136 }
137 bool ready = true;
138 for(const auto &ch : c.getWires(u))
139 if(!dep.count(ch)) { st.push_back(ch); ready = false; }
140 if(!ready) continue;
141 std::vector<std::size_t> r;
142 for(const auto &ch : c.getWires(u))
143 if(dep.at(ch)) {
144 const auto &rc = reads.at(ch);
145 r.insert(r.end(), rc.begin(), rc.end());
146 }
147 std::sort(r.begin(), r.end());
148 r.erase(std::unique(r.begin(), r.end()), r.end());
149 dep.emplace(u, !r.empty());
150 if(!r.empty())
151 reads.emplace(u, std::move(r));
152 st.pop_back();
153 }
154 }
155
156 std::vector<std::vector<std::size_t> > out(n);
157 std::vector<bool> self_loop(n, false);
158 for(std::size_t i = 0; i < n; ++i)
159 if(dep.at(w[n + i]))
160 for(const auto j : reads.at(w[n + i])) {
161 out[j].push_back(i);
162 if(j == i)
163 self_loop[i] = true;
164 }
165 const auto comps = fixSystemComponents(out);
166
167 std::vector<pg_uuid_t> token(n);
168 std::vector<bool> resolved(n, false);
169
170 /* The right-hand side @p g rebuilt with the resolved unknowns replaced by
171 * their tokens; the others, those of the component being resolved, are
172 * kept. Memoised per component, the replacement being fixed there. */
173 std::unordered_map<gate_t, pg_uuid_t> memo;
174 std::function<pg_uuid_t(gate_t)> rebuild = [&](gate_t g) -> pg_uuid_t {
175 if(!dep.at(g))
176 return string2uuid(c.getUUID(g));
177 auto m = memo.find(g);
178 if(m != memo.end())
179 return m->second;
180 pg_uuid_t r;
181 auto it = unknown.find(g);
182 if(it != unknown.end())
183 r = resolved[it->second] ? token[it->second] : string2uuid(c.getUUID(g));
184 else {
185 std::vector<pg_uuid_t> ch;
186 for(const auto &x : c.getWires(g))
187 ch.push_back(rebuild(x));
188 switch(c.getGateType(g)) {
189 case gate_plus:
190 r = provsql_build_plus(ch.data(), ch.size());
191 break;
192 case gate_times:
193 r = provsql_build_times(ch.data(), ch.size());
194 break;
195 case gate_monus:
196 if(ch.size() != 2)
197 throw NotRebuildable();
198 r = provsql_build_monus(&ch[0], &ch[1]);
199 break;
200 case gate_delta:
201 if(ch.size() != 1)
202 throw NotRebuildable();
203 r = provsql_build_delta(&ch[0]);
204 break;
205 default:
206 throw NotRebuildable();
207 }
208 }
209 memo.emplace(g, r);
210 return r;
211 };
212
213 try {
214 for(const auto &comp : comps) {
216 memo.clear();
217 if(comp.size() == 1 && !self_loop[comp[0]]) {
218 const std::size_t i = comp[0];
219 token[i] = rebuild(w[n + i]);
220 resolved[i] = true;
221 continue;
222 }
223 std::vector<pg_uuid_t> unknowns, rhs;
224 for(const auto i : comp) {
225 unknowns.push_back(string2uuid(c.getUUID(w[i])));
226 rhs.push_back(rebuild(w[n + i]));
227 }
228 const auto fix = make_system(unknowns, rhs);
229 for(std::size_t k = 0; k < comp.size(); ++k) {
230 token[comp[k]] = fix[k];
231 resolved[comp[k]] = true;
232 }
233 }
234 } catch(const NotRebuildable &) {
235 /* Keep the whole system: one fixpoint gate per tuple over it. */
236 for(std::size_t i = 0; i < n; ++i) {
237 token[i] = fixpoint_address(sys_token, i + 1);
239 &sys_token, true, i + 1, 0, nullptr);
240 }
241 }
242 return token;
243}
244
245}
246
247/**
248 * @brief The token of each tuple of the equation system @p sys, in order.
249 *
250 * SQL: @c resolve_fix_system(sys uuid) @c RETURNS @c uuid[]. See the file
251 * documentation.
252 */
253Datum resolve_fix_system(PG_FUNCTION_ARGS)
254{
255 try {
256 provsql_interrupt_scope interrupt_scope;
257 const pg_uuid_t sys = *DatumGetUUIDP(PG_GETARG_DATUM(0));
258 const std::vector<pg_uuid_t> tokens = resolve(sys);
259
260 Datum *elems = (Datum *) palloc(sizeof(Datum) * (tokens.size() ? tokens.size() : 1));
261 for(std::size_t i = 0; i < tokens.size(); ++i) {
262 pg_uuid_t *u = (pg_uuid_t *) palloc(sizeof(pg_uuid_t));
263 *u = tokens[i];
264 elems[i] = UUIDPGetDatum(u);
265 }
266 PG_RETURN_ARRAYTYPE_P(construct_array(elems, tokens.size(), UUIDOID,
267 UUID_LEN, false, 'c'));
268 } catch(const std::exception &e) {
270 provsql_error("resolve_fix_system: %s", e.what());
271 } catch(...) {
273 provsql_error("resolve_fix_system: Unknown exception");
274 }
275 PG_RETURN_NULL();
276}
pg_uuid_t provsqlUuidV5(const std::string &name)
RFC 4122 version-5 UUID in the ProvSQL namespace.
Content-addressed materialisation of a certified d-D into the mmap provenance store.
GenericCircuit getGenericCircuit(pg_uuid_t token)
Build a GenericCircuit from the mmap store rooted at token.
Build in-memory circuits from the mmap-backed persistent store.
gate_t
Strongly-typed gate identifier.
Definition Circuit.h:53
Strongly connected components of the dependency graph of an equation system (a recursive query,...
std::vector< std::vector< std::size_t > > fixSystemComponents(const std::vector< std::vector< std::size_t > > &out)
Strongly connected components of a directed graph, in the order in which equations along its edges ca...
Semiring-agnostic in-memory provenance circuit.
std::vector< gate_t > & getWires(gate_t g)
Return a mutable reference to the child-wire list of gate g.
Definition Circuit.h:311
gateType getGateType(gate_t g) const
Return the type of gate g.
Definition Circuit.h:301
uuid getUUID(gate_t g) const
Return the UUID string associated with gate g.
Definition Circuit.hpp:65
gate_t getGate(const uuid &u)
Return (or create) the gate associated with UUID u.
Definition Circuit.hpp:50
The SIGINT handler installed for the lifetime of the object, the previous one restored as it ends (a ...
Datum resolve_fix_system(PG_FUNCTION_ARGS)
The token of each tuple of the equation system sys, in order.
pg_uuid_t provsql_build_delta(const pg_uuid_t *token)
δ(token), with δ(𝟘) = 𝟘 and δ(𝟙) = 𝟙.
pg_uuid_t provsql_build_monus(const pg_uuid_t *token1, const pg_uuid_t *token2)
token1 ⊖ token2, with X ⊖ X = 𝟘 ⊖ X = 𝟘 and X ⊖ 𝟘 = X.
pg_uuid_t provsql_build_plus(const pg_uuid_t *tokens, int n)
⊕ of n tokens: 𝟘 dropped, none gives 𝟘, one is returned.
pg_uuid_t provsql_build_times(const pg_uuid_t *tokens, int n)
⊗ of n tokens: 𝟙 dropped, none gives 𝟙, one is returned.
The gate builders of the query rewriter, for C/C++ callers.
bool provsql_absorptive_provenance
Derived flag: the session's provenance class is 'absorptive' or 'boolean' – licenses constructions so...
Definition provsql.c:154
bool provsql_simplify_on_load
Run universal cmp-resolution passes when getGenericCircuit returns; controlled by the provsql....
Definition provsql.c:138
bool provsql_boolean_provenance
Derived flag: the session's provenance class is 'boolean' – enables the Boolean-only machinery (safe-...
Definition provsql.c:153
#define provsql_error(fmt,...)
Report a fatal ProvSQL error and abort the current transaction.
void provsql_cancel_if_interrupted(void)
Raise PG's cancel if the evaluation stopped for one; nothing otherwise.
Cancellation of the long C++ evaluation loops.
void provsql_poll_interrupt()
Throw where an evaluation is to stop, its query cancelled.
void provsql_internal_create_gate(const pg_uuid_t *token, gate_type type, unsigned nb_children, const pg_uuid_t *children_data)
Internal entry point behind create_gate(): cache + worker IPC.
void provsql_internal_create_gate_with(const pg_uuid_t *token, gate_type type, unsigned nb_children, const pg_uuid_t *children, bool has_infos, unsigned info1, unsigned info2, const char *extra)
Create a gate together with its infos and its text, in one message that is not answered.
Background worker and IPC primitives for mmap-backed circuit storage.
Core types, constants, and utilities shared across ProvSQL.
@ gate_fixpoint
Component of the least solution of an equation system: one wire to a gate_fixsystem,...
@ gate_fixsystem
Linear equation system x_i = f_i(x) of a recursive query, one equation per derived tuple: wires [x_1,...
pg_uuid_t string2uuid(const string &source)
Parse a UUID string into a pg_uuid_t.
string uuid2string(pg_uuid_t uuid)
Format a pg_uuid_t as a std::string.
C++ utility functions for UUID manipulation.