ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
Loading...
Searching...
No Matches
WhereCircuit.h
Go to the documentation of this file.
1/**
2 * @file WhereCircuit.h
3 * @brief Where-provenance circuit tracking column-level data origin.
4 *
5 * Where-provenance records not just which base tuples contributed to a
6 * query result, but also *which attribute values* in those base tuples
7 * gave rise to each output column.
8 *
9 * @c WhereCircuit extends @c Circuit<WhereGate> with per-gate metadata
10 * that describes:
11 * - **Input gates** – the source table, row UUID, and number of columns.
12 * - **Projection gates** – the list of attribute positions being projected.
13 * - **Equality gates** – the pair of attribute positions being joined.
14 *
15 * The @c evaluate() method traverses the circuit and returns, for each
16 * output position, a set of @c Locator values identifying the base
17 * (table, tuple, column) triples that the value was copied from.
18 */
19#ifndef WHERE_CIRCUIT_H
20#define WHERE_CIRCUIT_H
21
22#include <set>
23#include <vector>
24#include <utility>
25
26#include "Circuit.hpp"
27
28/**
29 * @brief Gate types for a where-provenance circuit.
30 *
31 * - @c UNDETERMINED Placeholder; should not appear in a complete circuit.
32 * - @c TIMES Product (conjunction) of child where-provenance sets.
33 * - @c PLUS Sum (disjunction) of child where-provenance sets.
34 * - @c EQ Equijoin gate recording the joined attribute pair.
35 * - @c PROJECT Projection gate recording which attributes are kept.
36 * - @c IN Input gate for a single base-relation tuple.
37 */
38enum class WhereGate {
39 UNDETERMINED, ///< Placeholder; should not appear in a complete circuit
40 TIMES, ///< Product (conjunction) of child where-provenance sets
41 PLUS, ///< Sum (disjunction) of child where-provenance sets
42 EQ, ///< Equijoin gate recording the joined attribute pair
43 PROJECT, ///< Projection gate recording which attributes are kept
44 IN, ///< Input gate for a single base-relation tuple
45 CONDITION ///< A comparison beside the row it filters: no column, no value copied
46};
47
48/**
49 * @brief Circuit encoding where-provenance (column-level data origin).
50 *
51 * Stores extra per-gate metadata that relates each gate to its position
52 * in the original query plan (table name, row UUID, column index).
53 */
54class WhereCircuit : public Circuit<WhereGate> {
55 private:
56 std::unordered_map<gate_t, uuid> input_token; ///< UUID of the source tuple for each IN gate
57 std::unordered_map<gate_t, std::pair<std::string,int>> input_info; ///< (table name, nb_columns) for each IN gate
58 std::unordered_map<gate_t, std::vector<int>> projection_info; ///< Projected attribute positions for PROJECT gates
59 std::unordered_map<gate_t, std::pair<int,int>> equality_info; ///< Joined attribute pair (pos1, pos2) for EQ gates
60
61 public:
62 /** @copydoc Circuit::setGate(const uuid&, gateType) */
63 gate_t setGate(const uuid &u, WhereGate type) override;
64
65 /**
66 * @brief Create an input gate for a specific table row.
67 *
68 * @param u UUID of the source tuple (row token).
69 * @param table Name of the source relation.
70 * @param nb_columns Number of columns in the source tuple.
71 * @return Gate identifier.
72 */
73 gate_t setGateInput(const uuid &u, std::string table, int nb_columns);
74
75 /**
76 * @brief Create a projection gate with column mapping.
77 *
78 * @param u UUID to associate with this gate.
79 * @param infos List of attribute positions surviving the projection.
80 * @return Gate identifier.
81 */
82 gate_t setGateProjection(const uuid &u, std::vector<int> &&infos);
83
84 /**
85 * @brief Create an equality (equijoin) gate for two attribute positions.
86 *
87 * @param u UUID to associate with this gate.
88 * @param pos1 Left-side attribute position.
89 * @param pos2 Right-side attribute position.
90 * @return Gate identifier.
91 */
92 gate_t setGateEquality(const uuid &u, int pos1, int pos2);
93
94 /** @copydoc Circuit::toString() */
95 std::string toString(gate_t g) const override;
96
97 private:
98 /**
99 * @brief Recursive helper for @c toString that propagates the parent
100 * gate type for parenthesis elision.
101 *
102 * The @p parent parameter drives the wrap decision: at the root
103 * (parent set to @c UNDETERMINED) the outer parens are dropped, and
104 * when @p parent matches the current gate type (associative
105 * TIMES/PLUS) the wrap is dropped to flatten same-op nesting. A
106 * 1-wire TIMES/PLUS also bypasses the wrap and delegates to its
107 * single child.
108 */
109 std::string toStringHelper(gate_t g, WhereGate parent) const;
110 public:
111
112 /**
113 * @brief Describes the origin of a single attribute value.
114 *
115 * A @c Locator identifies a specific attribute of a specific tuple in a
116 * specific base table as the origin of an output value.
117 */
118 struct Locator {
119 std::string table; ///< Name of the source relation
120 uuid tid; ///< UUID (row token) of the source tuple
121 int position; ///< Zero-based column index within the tuple
122
123 /**
124 * @brief Construct a @c Locator.
125 * @param t Source table name.
126 * @param u Source tuple UUID.
127 * @param i Column position.
128 */
129 Locator(std::string t, uuid u, int i) : table(t), tid(u), position(i) {}
130 /**
131 * @brief Lexicographic ordering for use in @c std::set.
132 * @param that Other @c Locator.
133 * @return @c true if @c *this is less than @p that.
134 */
135 bool operator<(Locator that) const;
136 /**
137 * @brief Return a human-readable representation of this locator.
138 * @return String of the form "table[tid].position".
139 */
140 std::string toString() const;
141 };
142
143 /**
144 * @brief Evaluate the where-provenance circuit at gate @p g.
145 *
146 * Returns one set of @c Locator values per output column position.
147 * Each @c Locator in the set identifies a base-relation cell that
148 * contributed the value at that output position.
149 *
150 * @param g Root gate to evaluate.
151 * @return Vector (indexed by output column) of sets of @c Locator values.
152 */
153 std::vector<std::set<Locator>> evaluate(gate_t g) const;
154};
155
156#endif /* WHERE_CIRCUIT_H */
gate_t
Strongly-typed gate identifier.
Definition Circuit.h:53
Out-of-line template method implementations for Circuit<gateType>.
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.
std::string uuid
Definition Circuit.h:175
Circuit encoding where-provenance (column-level data origin).
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.
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.
Locator(std::string t, uuid u, int i)
Construct a Locator.