JointEncoding.h File Reference

Phase A of the joint-width UCQ compiler: assemble the joint graph of the data and its correlation structure, and the per-fact gating information the homomorphism DP consumes. More...

#include <stdexcept>
#include <string>
#include <vector>
#include "Graph.h"

Include dependency graph for JointEncoding.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	JointCompilerException
	Exception thrown when joint-width compilation cannot proceed. More...
struct	FactRow
	One row of an atom's relation, as handed in by the SQL layer. More...
struct	SliceGate
	One node of the extracted circuit slice (correlated regime). More...
struct	Fact
	A deduplicated fact participating in the DP. More...
struct	Event
	One independent Bernoulli world variable. More...
class	JointEncoding
	The joint encoding of an instance: facts, world events, and the joint graph the screen and the DP run over. More...

Enumerations
enum class	FactGateKind { CERTAIN , INDEP , GATE }
	How a fact's presence is gated in a possible world. More...
enum class	SliceGateType { INPUT , AND , OR , NOT }
	Gate kind of a circuit-slice node (correlated regime). More...

Detailed Description

Phase A of the joint-width UCQ compiler: assemble the joint graph of the data and its correlation structure, and the per-fact gating information the homomorphism DP consumes.

The joint-width compiler (see UCQJointCompiler.h) evaluates an arbitrary UCQ – including the queries that are #P-hard under the Dalvi-Suciu dichotomy – exactly, in time tractable whenever the joint treewidth of the data and its correlation structure is bounded (Amarilli, PhD thesis tel-01345836, §4.2; Amarilli, Bourhis & Senellart, arXiv:1511.08723 App. D). The screen must run on the joint graph and nothing weaker: thesis Prop. 4.2.11 exhibits instances with tw(data)=1 and tw(circuit)=0 that are still #P-hard, all the hardness living in the fact-to-gate mapping.

JointEncoding builds that graph. In the data-graph regime (every fact gated by an independent gate_input, pairwise-distinct tokens – the §3.5 fast path) the joint graph is exactly the Gaifman graph of the facts and the screen is the data treewidth, which is the sound screen there (no correlation edges exist for Prop. 4.2.11 to exploit). Correlated inputs – facts whose provenance tokens are internal gates over shared events – additionally contribute the circuit slice's vertices and wires (handled by the gate machinery); their shared event leaves become real shared vertices, so the co-occurrence cliques of Prop. 4.3.2 arise automatically.

Definition in file JointEncoding.h.

Enumeration Type Documentation

FactGateKind

enum class FactGateKind

strong

How a fact's presence is gated in a possible world.

The data-graph fast path uses only CERTAIN and INDEP; the correlated regime adds GATE (presence is the value of an internal gate of the shared circuit slice).

Enumerator
CERTAIN	Always present: an untracked relation, constant-true token.
INDEP	Present iff its independent Bernoulli event is drawn (data-graph regime).
GATE	Present iff its slice gate evaluates true (correlated regime).

Definition at line 78 of file JointEncoding.h.

SliceGateType

enum class SliceGateType

strong

Gate kind of a circuit-slice node (correlated regime).

The slice is normalised to arity ≤ 2 (a fan-in-k AND/OR becomes a balanced binary tree of fresh gates), so AND/OR have exactly two children and NOT exactly one; INPUT leaves carry a probability.

Enumerator
INPUT
AND
OR
NOT

Definition at line 91 of file JointEncoding.h.