ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
Loading...
Searching...
No Matches
WhereCircuit.cpp
Go to the documentation of this file.
1/**
2 * @file WhereCircuit.cpp
3 * @brief WhereCircuit method implementations and where-provenance evaluation.
4 *
5 * Implements:
6 * - Gate creation methods: @c setGate(), @c setGateInput(),
7 * @c setGateProjection(), @c setGateEquality().
8 * - @c toString(): human-readable gate representation for debugging.
9 * - @c evaluate(): recursive DFS that computes the set of @c Locator
10 * values for each output column position, propagating provenance
11 * through TIMES (Cartesian product), PLUS (union), PROJECT
12 * (column selection), and EQ (equijoin merging) gates.
13 * - @c WhereCircuit::Locator::operator<() and @c toString().
14 */
15#include "WhereCircuit.h"
16
17extern "C" {
18#include "provsql_utils.h"
19#include <unistd.h>
20}
21
22#include <cassert>
23#include <string>
24#include <fstream>
25#include <sstream>
26#include <cstdlib>
27
28using namespace std;
29
31{
32 return Circuit::setGate(u, type);
33}
34
35gate_t WhereCircuit::setGateProjection(const uuid &u, vector<int> &&infos)
36{
37 auto id = setGate(u, WhereGate::PROJECT);
38 projection_info[id]=infos;
39 return id;
40}
41
42gate_t WhereCircuit::setGateEquality(const uuid &u, int pos1, int pos2)
43{
44 auto id = setGate(u, WhereGate::EQ);
45 equality_info[id]=make_pair(pos1,pos2);
46 return id;
47}
48
49gate_t WhereCircuit::setGateInput(const uuid &u, string table, int nb_columns)
50{
51 auto id = setGate(u, WhereGate::IN);
52 input_token[id]=u;
53 input_info[id]=make_pair(table, nb_columns);
54 return id;
55}
56
61
63{
64 std::string op;
65 string result;
66 auto gtype = getGateType(g);
67
68 switch(gtype) {
69 case WhereGate::IN:
70 return input_info.find(g)->second.first+":"+to_string(input_info.find(g)->second.second)+":"+input_token.find(g)->second;
72 op="?";
73 break;
75 return "cond";
77 op="⊗";
78 break;
79 case WhereGate::PLUS:
80 op="⊕";
81 break;
83 op="Π[";
84 {
85 bool first=true;
86 for(auto i : projection_info.find(g)->second) {
87 if(!first)
88 op+=",";
89 op+=to_string(i);
90 first=false;
91 }
92 }
93 op+="]";
94 break;
95 case WhereGate::EQ:
96 op="=["+to_string(equality_info.find(g)->second.first)+","+to_string(equality_info.find(g)->second.second)+"]";
97 }
98
99 for(auto s: getWires(g)) {
100 if(gtype==WhereGate::PROJECT || gtype==WhereGate::EQ)
101 result = op;
102 else if(!result.empty())
103 result+=" "+op+" ";
104 result+=toStringHelper(s, gtype);
105 }
106
107 // Parenthesis elision (mirrors BooleanCircuit::toStringHelper):
108 // * single-wire TIMES/PLUS: drop the now-meaningless wrap.
109 // * root call (parent = UNDETERMINED): drop the outer wrap.
110 // * same-op nesting (parent == gtype, TIMES/PLUS only): associative.
111 // PROJECT and EQ keep their parens so the prefix-bracketed shape
112 // (e.g., @c =[i,j](...)) renders unambiguously inside a parent gate.
113 bool single_join = (gtype==WhereGate::TIMES || gtype==WhereGate::PLUS)
114 && getWires(g).size()==1;
115 bool same_op_assoc = (gtype==WhereGate::TIMES || gtype==WhereGate::PLUS)
116 && parent==gtype;
117 if(single_join || parent==WhereGate::UNDETERMINED || same_op_assoc)
118 return result;
119 return "("+result+")";
120}
121
122vector<set<WhereCircuit::Locator> > WhereCircuit::evaluate(gate_t g) const
123{
124 vector<set<Locator> > v;
125
126 switch(getGateType(g)) {
127 case WhereGate::IN:
128 {
129 string table=input_info.find(g)->second.first;
130 uuid tid=input_token.find(g)->second;
131 int nb_columns=input_info.find(g)->second.second;
132 for(int i=0; i<nb_columns; ++i) {
133 set<Locator> s;
134 s.insert(Locator(table,tid,i+1));
135 v.push_back(s);
136 }
137 }
138 break;
139
141 // Only a factor of a product beside the row it filters is a condition
142 // (TIMES below skips it). A comparison anywhere else stands for the
143 // group it compares (a HAVING superseding the group's delta), whose
144 // columns the projection above expects: not supported.
145 throw CircuitException(
146 "Where-provenance does not support a comparison on an aggregate that "
147 "stands for its group (HAVING, or a comparison kept outside the "
148 "aggregation)");
149
150 case WhereGate::TIMES:
151 if(getWires(g).empty())
152 throw CircuitException("No wire connected to ⊗ gate");
153
154 {
155 // A comparison beside the row (the rank cut of ORDER BY ... LIMIT)
156 // decides whether the row is there, not where its values come from:
157 // it adds no column, so the columns beside it keep their positions.
158 // A product of comparisons alone has no row beside them.
159 bool row=false;
160 for(auto g2 : getWires(g))
162 row=true;
163 if(!row)
164 evaluate(*getWires(g).begin()); // throws, as for a lone comparison
165 }
166
167 for(auto g2 : getWires(g)) {
169 continue;
170 if(v.empty())
171 v=evaluate(g2);
172 else {
173 vector<set<Locator> > w=evaluate(g2);
174 v.insert(v.end(), w.begin(), w.end());
175 }
176 }
177 break;
178
179 case WhereGate::PLUS:
180 if(getWires(g).empty())
181 throw CircuitException("No wire connected to ⊕ gate");
182
183 for(auto g2 : getWires(g)) {
184 if(v.empty())
185 v=evaluate(g2);
186 else {
187 vector<set<Locator> > w=evaluate(g2);
188 if(w.size()!=v.size())
189 throw CircuitException("Incompatible inputs for ⊕ gate");
190
191 for(size_t k=0; k<v.size(); ++k) {
192 v[k].insert(w[k].begin(), w[k].end());
193 }
194 }
195 }
196 break;
197
199 if(getWires(g).size()!=1)
200 throw CircuitException("Not exactly one wire connected to Π gate");
201
202 {
203 vector<set<Locator> > w=evaluate(*getWires(g).begin());
204 vector<int> positions=projection_info.find(g)->second;
205 for(auto i : positions) {
206 if(i==0 || i>(int)w.size())
207 v.push_back(set<Locator>());
208 else
209 v.push_back(w[i-1]);
210 }
211 }
212 break;
213
214 case WhereGate::EQ:
215 if(getWires(g).size()!=1)
216 throw CircuitException("Not exactly one wire connected to = gate");
217
218 v=evaluate(*getWires(g).begin());
219 {
220 pair<int,int> positions=equality_info.find(g)->second;
221 if(positions.first>=1 && positions.first<=(int)v.size() &&
222 positions.second>=1 && positions.second<=(int)v.size()) {
223 // The two positions hold equal values: either may have been copied
224 // from the other. So may any position already known to hold that
225 // same value, which is one sharing a locator with them (an earlier
226 // equality merged it, or it projects the same cell): the merge is
227 // closed over those, so that a = b and b = c leave a, b and c with
228 // the same locators whatever the order of the two gates.
229 set<Locator> merged=v[positions.first-1];
230 merged.insert(v[positions.second-1].begin(), v[positions.second-1].end());
231 vector<bool> in_class(v.size(), false);
232 in_class[positions.first-1]=in_class[positions.second-1]=true;
233
234 bool changed=true;
235 while(changed) {
236 changed=false;
237 for(size_t k=0; k<v.size(); ++k) {
238 if(in_class[k])
239 continue;
240 bool shares=false;
241 for(const auto &l : v[k])
242 if(merged.find(l)!=merged.end()) {
243 shares=true;
244 break;
245 }
246 if(shares) {
247 merged.insert(v[k].begin(), v[k].end());
248 in_class[k]=true;
249 changed=true;
250 }
251 }
252 }
253 for(size_t k=0; k<v.size(); ++k)
254 if(in_class[k])
255 v[k]=merged;
256 }
257 }
258 break;
259
260 default:
261 throw CircuitException("Gate type not supported by where-provenance");
262 }
263
264 return v;
265}
266
268{
269 if(this->table != that.table)
270 return this->table < that.table;
271 if(this->tid != that.tid)
272 return this->tid < that.tid;
273 return this->position < that.position;
274}
275
277{
278 return table + ":" + tid + ":" +to_string(position);
279}
gate_t
Strongly-typed gate identifier.
Definition Circuit.h:53
std::string to_string(gate_t g)
Convert a gate_t to its decimal string representation.
Definition Circuit.h:458
Where-provenance circuit tracking column-level data origin.
WhereGate
Gate types for a where-provenance circuit.
@ PROJECT
Projection gate recording which attributes are kept.
@ EQ
Equijoin gate recording the joined attribute pair.
@ PLUS
Sum (disjunction) of child where-provenance sets.
@ CONDITION
A comparison beside the row it filters: no column, no value copied.
@ TIMES
Product (conjunction) of child where-provenance sets.
@ IN
Input gate for a single base-relation tuple.
@ UNDETERMINED
Placeholder; should not appear in a complete circuit.
Exception type thrown by circuit operations on invalid input.
Definition Circuit.h:382
std::string uuid
Definition Circuit.h:175
std::vector< gate_t > & getWires(gate_t g)
Definition Circuit.h:311
WhereGate getGateType(gate_t g) const
Definition Circuit.h:301
virtual gate_t setGate(const uuid &u, gateType type)
Create or update the gate associated with UUID u.
Definition Circuit.hpp:187
std::unordered_map< gate_t, std::pair< int, int > > equality_info
Joined attribute pair (pos1, pos2) for EQ gates.
std::unordered_map< gate_t, uuid > input_token
UUID of the source tuple for each IN gate.
std::unordered_map< gate_t, std::pair< std::string, int > > input_info
(table name, nb_columns) for each IN gate
std::unordered_map< gate_t, std::vector< int > > projection_info
Projected attribute positions for PROJECT gates.
gate_t setGateInput(const uuid &u, std::string table, int nb_columns)
Create an input gate for a specific table row.
gate_t setGateEquality(const uuid &u, int pos1, int pos2)
Create an equality (equijoin) gate for two attribute positions.
std::string toStringHelper(gate_t g, WhereGate parent) const
Recursive helper for toString that propagates the parent gate type for parenthesis elision.
gate_t setGate(const uuid &u, WhereGate type) override
Create or update the gate associated with UUID u.
std::string toString(gate_t g) const override
Return a textual description of gate g for debugging.
gate_t setGateProjection(const uuid &u, std::vector< int > &&infos)
Create a projection gate with column mapping.
std::vector< std::set< Locator > > evaluate(gate_t g) const
Evaluate the where-provenance circuit at gate g.
Core types, constants, and utilities shared across ProvSQL.
Describes the origin of a single attribute value.
std::string toString() const
Return a human-readable representation of this locator.
bool operator<(Locator that) const
Lexicographic ordering for use in std::set.
int position
Zero-based column index within the tuple.
std::string table
Name of the source relation.
uuid tid
UUID (row token) of the source tuple.