ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
Loading...
Searching...
No Matches
JointEncoding.h
Go to the documentation of this file.
1/**
2 * @file JointEncoding.h
3 * @brief Phase A of the joint-width UCQ compiler: assemble the *joint
4 * graph* of the data and its correlation structure, and the
5 * per-fact gating information the homomorphism DP consumes.
6 *
7 * The joint-width compiler (see @c UCQJointCompiler.h) evaluates an
8 * arbitrary UCQ -- including the queries that are @c \#P-hard under the
9 * Dalvi-Suciu dichotomy -- exactly, in time tractable whenever the
10 * **joint treewidth** of the data and its correlation structure is
11 * bounded (Amarilli, PhD thesis tel-01345836, §4.2; Amarilli, Bourhis
12 * & Senellart, arXiv:1511.08723 App. D). The screen must run on the
13 * *joint* graph and nothing weaker: thesis Prop. 4.2.11 exhibits
14 * instances with @c tw(data)=1 and @c tw(circuit)=0 that are still
15 * @c \#P-hard, all the hardness living in the fact-to-gate mapping.
16 *
17 * @c JointEncoding builds that graph. In the data-graph regime
18 * (every fact gated by an independent @c gate_input, pairwise-distinct
19 * tokens -- the §3.5 fast path) the joint graph is exactly the Gaifman
20 * graph of the facts and the screen is the data treewidth, which is the
21 * sound screen there (no correlation edges exist for Prop. 4.2.11 to
22 * exploit). Correlated inputs -- facts whose provenance tokens are
23 * internal gates over shared events -- additionally contribute the
24 * circuit slice's vertices and wires (handled by the gate
25 * machinery); their shared event leaves become real shared
26 * vertices, so the co-occurrence cliques of Prop. 4.3.2 arise
27 * automatically.
28 */
29#ifndef JOINT_ENCODING_H
30#define JOINT_ENCODING_H
31
32#include <stdexcept>
33#include <string>
34#include <vector>
35
36#include "Graph.h"
37
38/**
39 * @brief Exception thrown when joint-width compilation cannot proceed.
40 *
41 * Raised on unsupported input shapes (a @c gate_input token shared by
42 * facts over different element tuples, an unsupported gate type in a
43 * circuit slice) so the SQL layer can fall back to the default cost-based
44 * probability evaluation.
45 * Joint width above the configured bound surfaces as the usual
46 * @c TreeDecompositionException instead.
47 */
48class JointCompilerException : public std::runtime_error {
49public:
50/** @brief Construct with a human-readable message. @param what Message. */
51explicit JointCompilerException(const std::string &what)
52 : std::runtime_error(what) {
53}
54};
55
56/**
57 * @brief One row of an atom's relation, as handed in by the SQL layer.
58 *
59 * Mirrors the columnar convention of @c reachability_evaluate: the SQL
60 * wrapper collects the post-selection rows of each relation, maps
61 * arbitrary SQL values to dense element ids **with a dictionary shared
62 * across relations** (so join-compatible values get the same id), and
63 * passes parallel arrays.
64 */
65struct FactRow {
66 unsigned relation_id = 0; ///< Dense id of the relation symbol.
67 std::vector<unsigned long> elements; ///< Dense ids of the row's domain elements.
68 std::string token; ///< Provenance gate (UUID); empty marks a certain (untracked) fact.
69 double prob = 1.0; ///< Tuple probability (for an independent @c gate_input token).
70};
71
72/**
73 * @brief How a fact's presence is gated in a possible world.
74 *
75 * The data-graph fast path uses only @c CERTAIN and @c INDEP; the
76 * correlated regime adds @c GATE (presence is the value of an internal
77 * gate of the shared circuit slice).
78 */
79enum class FactGateKind {
80 CERTAIN, ///< Always present: an untracked relation, constant-true token.
81 INDEP, ///< Present iff its independent Bernoulli event is drawn (data-graph regime).
82 GATE ///< Present iff its slice gate evaluates true (correlated regime).
83};
84
85/**
86 * @brief Gate kind of a circuit-slice node (correlated regime).
87 *
88 * The slice is normalised to arity ≤ 2 (a fan-in-@e k AND/OR becomes a
89 * balanced binary tree of fresh gates), so AND/OR have exactly two
90 * children and NOT exactly one; INPUT leaves carry a probability.
91 */
92enum class SliceGateType { INPUT, AND, OR, NOT };
93
94/**
95 * @brief One node of the extracted circuit slice (correlated regime).
96 */
97struct SliceGate {
99 std::vector<unsigned> children; ///< Child slice indices (≤ 2; empty for INPUT).
100 double prob = 1.0; ///< Marginal (INPUT only).
101 std::string token; ///< Provenance token of the leaf (INPUT only; for the d-D IN gate UUID).
102};
103
104/**
105 * @brief A deduplicated fact participating in the DP.
106 *
107 * Several @c FactRow occurrences of the same provenance token (a
108 * self-join scanning one relation, or duplicated provenance) collapse
109 * to a single @c Fact serving every matching atom -- treating the
110 * occurrences as independent would be silently wrong, so the encoding
111 * dedups by token.
112 */
113struct Fact {
114 unsigned relation_id = 0; ///< Dense id of the relation symbol.
115 std::vector<unsigned long> elements; ///< Dense element ids (the fact's tuple).
116 FactGateKind kind = FactGateKind::INDEP; ///< How the fact's presence is gated.
117 std::size_t event = 0; ///< Index into @c events (when @c INDEP).
118 std::size_t gate = 0; ///< Index into @c slice (when @c GATE).
119};
120
121/**
122 * @brief One independent Bernoulli world variable.
123 *
124 * In the data-graph regime each fact is its own event; the correlated
125 * regime makes events the leaves of the shared circuit slice.
126 */
127struct Event {
128 std::string token; ///< Provenance token (UUID) of the leaf.
129 double prob = 1.0; ///< Marginal probability.
130};
131
132/**
133 * @brief The joint encoding of an instance: facts, world events, and
134 * the joint graph the screen and the DP run over.
135 */
137public:
138std::vector<Fact> facts; ///< Deduplicated facts.
139std::vector<Event> events; ///< Independent world variables (data-graph regime).
140std::vector<SliceGate> slice;///< Circuit slice (correlated regime); gate vertex = @c n_elements + index.
141bool correlated = false; ///< @c true when the slice is present (correlated regime).
142unsigned long n_elements = 0;///< One past the largest domain element id (vertex ids @c [0,n_elements)).
143
144unsigned data_treewidth_lb = 0; ///< Degeneracy lower bound of the data-only graph (diagnostics).
145unsigned circuit_treewidth_lb = 0; ///< Degeneracy lower bound of the slice-only graph (0 in the data-graph regime).
146
147/**
148 * @brief Build the data-graph (§3.5 fast path) encoding from raw rows.
149 *
150 * Dedups facts by token (a token over identical element tuples serves
151 * many atoms; a @c gate_input token shared across *different* element
152 * tuples is rejected with @c JointCompilerException, routing the caller
153 * to the general path). Each independent fact becomes one Bernoulli
154 * event; certain facts (empty token) are always present. The joint
155 * graph is the Gaifman graph of the facts (one clique per fact over its
156 * elements).
157 *
158 * @param rows Per-atom relation rows (already dense-encoded).
159 * @return The assembled encoding.
160 */
161static JointEncoding fromFacts(const std::vector<FactRow> &rows);
162
163/**
164 * @brief Construct the correlated-regime encoding from facts and an
165 * already-extracted circuit slice.
166 *
167 * The caller (the SQL glue) walks the mmap circuit from the distinct
168 * fact tokens down to @c gate_input leaves and normalises the slice to
169 * arity ≤ 2, filling @p slice and, per fact, the index of its slice
170 * gate (or marking it certain for an untracked / constant-true token).
171 * This factory assembles the joint graph (element vertices, gate
172 * vertices, fact-to-gate and gate-wire cliques) and the diagnostics.
173 *
174 * @param facts Deduplicated facts (kind @c GATE carry a slice
175 * index in @c Fact::gate; kind @c CERTAIN are always
176 * present).
177 * @param slice The circuit slice (arity ≤ 2).
178 * @param n_elements One past the largest element id used.
179 * @return The assembled correlated encoding.
180 */
181static JointEncoding fromCorrelated(std::vector<Fact> facts,
182 std::vector<SliceGate> slice,
183 unsigned long n_elements);
184
185/**
186 * @brief Construct the joint graph for the screen and the DP.
187 *
188 * Data-graph regime: the Gaifman graph of the facts -- per-fact cliques
189 * over domain elements, isolated nodes for unary facts. Correlated
190 * regime: additionally the gate vertices @c [n_elements, n_elements +
191 * |slice|), with a clique over @c {elements} ∪ @c {fact gate} per fact
192 * (thesis Def. 4.2.5, rule 1) and a clique over @c {gate} ∪
193 * @c {children} per internal slice gate (the stronger ternary
194 * co-occurrence of arXiv:1511.08723, rule 2).
195 *
196 * @return The joint graph (a fresh copy; the decomposition consumes it).
197 */
198Graph buildGraph() const;
199};
200
201#endif /* JOINT_ENCODING_H */
Undirected graph used in tree-decomposition computations.
SliceGateType
Gate kind of a circuit-slice node (correlated regime).
FactGateKind
How a fact's presence is gated in a possible world.
@ GATE
Present iff its slice gate evaluates true (correlated regime).
@ CERTAIN
Always present: an untracked relation, constant-true token.
@ INDEP
Present iff its independent Bernoulli event is drawn (data-graph regime).
Mutable adjacency-list graph over unsigned-long node IDs.
Definition Graph.h:33
JointCompilerException(const std::string &what)
Construct with a human-readable message.
The joint encoding of an instance: facts, world events, and the joint graph the screen and the DP run...
static JointEncoding fromCorrelated(std::vector< Fact > facts, std::vector< SliceGate > slice, unsigned long n_elements)
Construct the correlated-regime encoding from facts and an already-extracted circuit slice.
Graph buildGraph() const
Construct the joint graph for the screen and the DP.
std::vector< Event > events
Independent world variables (data-graph regime).
bool correlated
true when the slice is present (correlated regime).
unsigned circuit_treewidth_lb
Degeneracy lower bound of the slice-only graph (0 in the data-graph regime).
std::vector< Fact > facts
Deduplicated facts.
std::vector< SliceGate > slice
Circuit slice (correlated regime); gate vertex = n_elements + index.
unsigned data_treewidth_lb
Degeneracy lower bound of the data-only graph (diagnostics).
static JointEncoding fromFacts(const std::vector< FactRow > &rows)
Build the data-graph (§3.5 fast path) encoding from raw rows.
unsigned long n_elements
One past the largest domain element id (vertex ids [0,n_elements)).
One independent Bernoulli world variable.
double prob
Marginal probability.
std::string token
Provenance token (UUID) of the leaf.
One row of an atom's relation, as handed in by the SQL layer.
unsigned relation_id
Dense id of the relation symbol.
double prob
Tuple probability (for an independent gate_input token).
std::string token
Provenance gate (UUID); empty marks a certain (untracked) fact.
std::vector< unsigned long > elements
Dense ids of the row's domain elements.
A deduplicated fact participating in the DP.
std::size_t gate
Index into slice (when GATE).
std::vector< unsigned long > elements
Dense element ids (the fact's tuple).
FactGateKind kind
How the fact's presence is gated.
unsigned relation_id
Dense id of the relation symbol.
One node of the extracted circuit slice (correlated regime).
SliceGateType type
Node kind.
std::vector< unsigned > children
Child slice indices (≤ 2; empty for INPUT).
double prob
Marginal (INPUT only).
std::string token
Provenance token of the leaf (INPUT only; for the d-D IN gate UUID).