Representing Relations

Relations

Relation $R \subseteq D^X$ : set of tuples, over domain $D$ and variables $X$ .

$x$	$y$	$z$
1	2	1
2	0	1
0	0	1
1	2	0

Table representation
Explicit representation

$x$	$y$
1	2
2	0
0	0

$\bowtie$

$y$	$z$
2	1
0	1
2	0

Result of a (join) query
Implicit Representation

Using Relations

A relation $R$ represents data we want to use.

Enumerate

Stream every tuple to perform an action.

Agregate

Compute statistics on $R$ , compute the size $\#R$ , ratios $\#R[x=Alice]/\#R$ , aggregate with semiring operation etc.

Glimpse

(Uniform) sampling, enumerate representative tuples etc.

Access

Quickly output the $k^{th}$ tuple (assuming an order on $R$ ), find median tuple etc.

Everything is “easy” if $R$ is given as a table, but is it necessary to materialize it?

A bit of (combined) complexity

Complexity varies depending on the representation of $R \subseteq D^X$ .

Task	Table	Join Query
Output one tuple in $R$	$O(1)$	NP-complete
Output “largest” tuple in $R$	Linear $O(\#R)$	NP-complete
Compute $\#R$	$O(1)$	#P-complete

We are looking for succinctness/tractability tradeoffs!

Yannakakis Algorithm

A well behaved join

$Q = S(x,y,a) \bowtie R(x,y,z) \bowtie T(x,z,b)$

x	y	z
0	0	0
0	1	0
0	0	1
1	1	1

S	x	y	a
	0	0	1
	0	0	2
	0	1	1

x	z	b
0	0	1
0	0	3
0	1	2
1	1	1

$Q[xyz=000]$	$=S[xy=00] \times T[xz=00]$
	$=\{a=1,a=2\} \times \{b=1,b=3\}$

$Q[xyz=010]$	$=S[xy=01] \times T[xz=00]$
	$=\{a=1\} \times \{b=1, b=3\}$

$Q[xyz=001]$	$=S[xy=00] \times T[xz=01]$
	$=\{a=1, a=2\} \times \{b=2\}$

$Q[xyz=111]$	$=S[xy=11] \times T[xz=11]$
	$=\emptyset \times \{b=1\}$

Acyclic Join Query

A Join Query is acyclic iff it has a join tree.

Each variable is connected.
Well behaved at each node.
Bottom-up algorithm.

Bottom up construction

$Q = R \bowtie (S \bowtie Q_1) \bowtie (T \bowtie Q_2)$

At most $\times$ per tuple in $R$ .

At most one tree per tuple in $S$ .

At most one tree per tuple in $T$ .

x	y	z
0	0	0
0	1	0
0	0	1
1	1	1

S	x	y	a
	0	0	1
	0	0	2
	0	1	1

x	z	b
0	0	1
0	0	3
0	1	2
1	1	1

$Q_1$

$Q_2$

Acyclic Join Query Complexity

Given an acyclic join query $Q = (R_1 \bowtie \dots \bowtie R_m)$ and a join tree for $Q$ :

Bottom up construction gives a linear size representation of $rel(Q)$
Representation uses Cartesian products, decision nodes and factorization.

Factorized Databases Zoo

$\{\times, \cup\}$ -circuits

Introduced by Dan Olteanu and Jakub Závodný under the name d-representation.

✅ Find a tuple

✅ Find a tuple $\simeq \tau$

✅ Find “optimal” tuple

✅ Enumerate (delay $O(|C|)$ ).

❌ Counting

❌ Many Aggregation tasks.

Smoothness

Ambiguous value, two possible semantics:

“Don’t care”: $(x=0 \times y \in D) \cup (x \in D \times y=1)$
Zero suppressed semantics: $(x=0 \times y=DEF) \cup (x=DEF \times y=1)$ .

Smoothness: every $\cup$ is on same attributes relations.

purely syntactic
ensured in the algorithms presented today
can always be ensured by syntactic transformation

$\{\uplus,\times\}$ -circuit

Unions have disjoint tuples (sometimes called deterministic, or unambiguous unions).

✅ Find a tuple

✅ Enumerate: delay depth of $C$ .

We can do better, check [Amarilli, Bourhis, Jachiet, Mengel].

✅ Counting

✅ Counting with semiring weights

❌ coNP-hard to check.

$\{\times,\mathsf{dec}\}$ -circuits

Knowledge Compilation

Multi-domain generalization of well-studied Boolean circuits.

Gates	Boolean Domain	Enum	Count
$\{\bowtie, \cup\}$	NNF	❌	❌
$\{\cup, \times\}$	DNNF	☑	❌
$\{\uplus, \times\}$	d-DNNF	☑	✅
$\{\mathsf{dec}, \times\}$	dec-DNNF	✅	✅
$\{\mathsf{dec}\}$	FBDD	✅	✅

Removing constants

For convenience, we may allow constants:

$\bot$ for empty relation.
$\top$ for $\{\langle \rangle\}$ .
$\bot$ is annoying for enumeration purposes: remove it!

Solving Tasks on Circuits

Design algorithm on the circuit directly:

Size of the relation: $O(|C|)$
- $\#rel(g_1 \times \dots \times g_k) = \prod_{i=1}^k \#rel(g_i)$
- $\#rel(g_1 \uplus \dots \uplus g_k) = \sum_{i=1}^k \#rel(g_i)$
- works for any semi-ring

Enumeration: $O(\#vars)$ delay
- first tuple of $g$
- next tuple of $g$

Consequence for Acyclic Join Queries: counting in linear time (data complexity), enumeration in constant time after linear preprocessing.

Lower Bounds

Circuits useful to design algorithms, but also for lower bounds.

The answers of a JQ $Q$ can be enumerated with linear preprocessing and constant delay for every DB

iff $Q$ is acyclic assuming the Boolean Matrix Multiplication Conjecture.

[Bagan, Durand, Grandjean] Conditional lower bound, for any algorithm

If $Q$ is not acyclic, there exists $\varepsilon > 0$ s. t. for every $N$ , there is a database $D_N$ of size $N$ , such that any circuit computing the answers of $Q$ over $D_N$ is of size at least $N^{1+\varepsilon}$ .

Unconditional lower bound, but targeting a large class of algorithms.

Bedtime stories

Probabilistic database evaluation dichotomy vs circuit lower bounds:
- Exist tractable queries with no small $\{\times,\mathsf{dec}\}$ -circuits [Beame, Li, Roy, Suciu]
- Open for $\{\times, \uplus\}$ -circuits (ask Dan Olteanu)!
Dichotomy for JQ based on submodular width [Berkholz, Vinall-Smeeth]: go to the talk!!
Lower bounds for algebraic semi-ring circuits [Fan, Koutris, Zao]

Top-down Compilation

Recalling Bottom-up Compilation

$Q = R \bowtie (S \bowtie Q_1) \bowtie (T \bowtie Q_2)$

x	y	z
0	0	0
0	1	0
0	0	1
1	1	1

S	x	y	a
	0	0	1
	0	0	2
	0	1	1

x	z	b
0	0	1
0	0	3
0	1	2
1	1	1

$Q_1$

$Q_2$

Start fresh

Set $x,y,z$ to the first tuple in $R$

On the remaining variables, $Q$ has two connected components. Proceed with $S(0,0,a) \wedge Q_1$ before $T(0,0,b) \wedge Q_2$

Pick value $1$ for $a$ and continue with $Q_1$ .

Backtrack and pick $2$ for $a$ , continue with $Q_1$ .

Do the same with $T(0,0,b) \wedge Q_2$ .

Backtrack and set $z=1$ .

Recursive call on $S(0,0,a) \bowtie Q_1$ . AGAIN??! Better reuse!

Construct $T(0,1,b) \bowtie Q_2$ .

Draw the rest of the owl!

Breaking news

Use caching to “reverse” the dynamic programming :

Branch on tuples from the join tree node $t$ .
Branch one variable at a time, following prefix order of the tree.
Decompose on children of $t$ .
Detect connected components on remaining atoms and variables.
Construct the circuit recursively
one connected component at a time.
Keep a cache mapping subqueries with the gate computing it.

Wait, do we even need the join tree? No! Only an order

Enters Exhaustive DPLL

Exhaustive DPLL complexity

Fix an order $\pi = x_1,\dots,x_n$ on $var(Q)$ :

$EDPLL(Q, \pi)$ builds a circuit of size at most $O(N^{\iota(Q,\pi)})$ for some $\iota(Q,\pi) \in \mathbb{Q}$ .

In data complexity, but polynomial in combined complexity.

Case ι(Q,π)=1\iota(Q,\pi)=1 well studied, only possible with acyclic queries.
- Disruptive trio free [Carmeli, Tziavelis, Gatterbauer, Kimelfeld, Riedewald]
- Reverse of $\alpha$ -elimination order [Brault-Baron]

Projecting variables

Existentially project variables: $\exists Y. Q$

If $Y$ at the end of the order:

ACQ: free-connexity!
$Y$ tested at the bottom
Can be projected!
Example: project $a$ , project $y$

Exhaustive DPLL in Knowledge Compilation

Core algorithm in many practical #SAT-solvers: d4, sharpsat-td, ExactMC etc.
Differences :
- Binary domain only
- Use oracle calls to SAT solver to avoid unsatisfiable subcircuits.
- Leverage learnt clauses in SAT solvers calls.
- Lots of preprocessing techniques: vivification, B+E etc.
- Use Unit Propagation: clause $(x)$ propagates $x=1$ directly.
- Dynamic ordering via branching heuristics. Partially guided by tree decompositions.
- A clause $(x_1 \vee \dots \vee x_n)$ has $2^n-1$ tuples from $\{0,1\}^n$ in it: negative encoding.

Join Queries with Negated Atoms

Signed Join Queries

$Q = \bigwedge_{i=1}^k P_i(\mathbf{z_i})$ $\bigwedge_{i=1}^l \lnot N_i(\mathbf{z_i})$

Negation interpreted over a given domain $D$ :

$N$
$x_1$	$x_2$	$x_3$
0	1	0

$\lnot N$ on $\{0,1\}$
$x_1$	$x_2$	$x_3$
0	0	0
0	0	1
0	1	1
1	0	0
1	0	1
1	1	0
1	1	1

$\neg N(x_1,\dots,x_k)$ encoded with $|D|^{k}-\#N$ tuples.
Relation with SAT: $\neg N$ is $x_1 \vee \neg x_2 \vee x_3$

Positive Encoding not Optimal

$Q(x_1,\dots,x_n) = \neg N(x_1,\dots,x_n)$ , domain $\{0,1\}$ .

Positive encoding: preprocessing $O(2^n)$

N
$x$	$y$	$z$
0	0	0

Hardness of subqueries

$Q_1 = R(x_1, x_2, x_3) \land S(x_1, x_2) \land T(x_2, x_3) \land U(x_3, x_1)$

linear sized circuit

$Q_2 = S(x_1, x_2) \land T(x_2, x_3) \land U(x_3, x_1)$

non-linear sized circuit ( $|dom|^{3/2}$ )

Subqueries may be harder to solve than the query itself!

Subqueries and negative atoms

$Q_1' =$ $\lnot R(1, 2, 3)$ $\land S(1, 2) \land T(2, 3) \land U(3, 1)$

Equivalent to $Q_2$ if $R=\emptyset$

$Q_2 = S(1, 2) \land T(2, 3) \land U(3, 1)$

non-linear circuit

Circuit construction for $Q = P \wedge N$ implies circuit construction for $Q = P \wedge N'$ for every $N' \subseteq N$ !

Generalizing Exhaustive DPLL

Exhaustive DPLL works out of the box in this case, but can be improved:

Branch $x_1/0$ in $\neg R(x_1,\dots,x_k)$ : $\neg R(0,x_2,\dots,x_k)$ .
$R(0,x_2,\dots,x_k)$ may be empty.
We can remove atom $\neg R(0,x_2,\dots,x_k)$ .
Allows to discover smaller connected components!

A Star in a Negative Potatoe

$S_1$	$h$	$x_1$
	0	0
	1	0
	1	1

$S_2$	$h$	$x_2$
	0	0
	1	0
	1	1

$S_3$	$h$	$x_3$
	0	0
	1	0
	1	1

$K$	$h$	$x_1$	$x_2$	$x_3$
	1	1	1	1

$S_1 \bowtie S_2 \bowtie S_3 \bowtie \neg K$

Exhaustive DPLL Guarantees

$Q$ SJQ. Fix an order $\pi = x_1,\dots,x_n$ on $var(Q)$ :

$EDPLL(Q, \pi)$ builds a circuit of size at most $O(N^{\kappa(Q,\pi)})$ for some $\kappa(Q,\pi) \in \mathbb{Q}$ .

In data complexity but polynomial wrt combined complexity.

$\kappa(Q,\pi) = \iota(Q,\pi)$ if $Q$ is positive.
$\kappa(Q,\pi) = 1$ corresponds to signed acyclicity [Brault-Baron], [Zhao, Fan, Ouyang, Koutris]
$\kappa(Q,\pi)$ is basically the worst $\iota(Q',\pi)$ we can get where $Q'$ is obtained by turning some negative atoms from $Q$ positive and removing the others.

Building Relational Circuits