From Queries to Circuits

Florent Capelli

Université d’Artois - CRIL

Dagtsuhl Seminar
Representation, Provenance, and Explanations in Database Theory and Logic

January 17, 2024

Representing Relations

Relations from Queries and Databases

$Q(X)$ query with free variables $X$
$\mathbb{D}$ database on domain $D$

define the relation $Q(\mathbb{D}) \subseteq D^X$ of answers of $Q$ over $\mathbb{D}$

$(Q,\mathbb{D})$ is an implicit representation of a relation of $D^X$ .

Relations from Tables

A relation $R \subseteq D^X$ can also be explicitly represented as a table:

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

Problems defined on Relations

Given a representation of $R \subseteq D^X$ :

Emptiness: decide whether $R = \emptyset$
Totality: decide whether $R = D^X$
Size: output $\#R$
Sample: sample $\tau \in R$ uniformly
Enumeration: output every tuple in $R$ .
Direct Access: given $k$ , output the $k^{th}$ tuple of $R$ (assuming an order on $D^X$ ).
Aggregation: output $\bigoplus_{\tau \in R} f(\tau)$ for some $f \colon D^X \rightarrow (\mathbb{M}, \oplus)$

Representation and Complexity

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

Problem	(CQ, $\mathbb{D}$ )	Table
Emptiness	$NP$ -hard	$O(1)$
Totality	$O(\|Q\|\cdot\|\mathbb{D}\|)$	$O(1)$
Size	$\#P$ -hard	$O(1)$

A table is less succinct than a query but more tractable.

Looking for tradeoffs!

A Factorized Approach

$\{\times,\cup\}\text{-circuit}$ s

$X$ a finite set of variables.
$D$ a finite domain.

Smoothness

Interpret * either by as “any domain value” or “a default domain value” (zero suppressed semantics).

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

Syntactic unambiguity

Decision Gates:

Comparing circuits

Gates	Boolean Domain
$\{\bowtie, \cup\}$	NNF
$\{\cup, \times\}$	DNNF
$\{\uplus, \times\}$	d-DNNF
$\{\mathsf{dec}, \times\}$	dec-DNNF
$\{\mathsf{dec}\}$	FBDD

Tractability Map

$C$ a circuit on domain $D$ and variable $X$ with $n=|X|$ .

Gates	Emptiness	Totality	Size	Enumeration
$\{\bowtie, \cup\}$	NP-complete	coNP-complete	#P-complete	NP-hard
$\{\cup, \times\}$	$O(\|C\|)$	coNP-complete	#P-complete	$O(n\|C\|)$ -delay
$\{\uplus, \times\}$	$O(\|C\|)$	$O(\|C\|p(n))$	$O(\|C\|p(n))$	$O(\|C\|)$ -delay
$\{\mathsf{dec}, \times\}$	$O(\|C\|)$	$O(\|C\|p(n))$	$O(\|C\|p(n))$	$O(\|C\|)$ -preproc $O(p(n))$ -delay

Assuming manipulating integers of size $N$ is polynomial in $\frac{N}{\log|\mathbb{D}|}$ .

Complexity that only depends on $n$ is constant time in the data complexity model!

Compilation

Framework

Given a full conjunctive query $Q$ and a database $\mathbb{D}$ , construct a $\{\times,\mathsf{dec}\}\text{-circuit}$ $C$ representing $Q(\mathbb{D})$ .

Construction cannot be polynomial in $|Q|$ and $|\mathbb{D}|$ in the worst case (see lower bounds for DNNF).
There exists tractable family of CQs:
- Acyclic conjunctive queries have $\{\times,\mathsf{dec}\}\text{-circuit}$ of size $poly(|Q|) \times |\mathbb{D}|$ .
- Conjunctive queries have $\{\times,\mathsf{dec}\}\text{-circuit}$ of size $poly(|Q|) \times |\mathbb{D}|^{fhtw(Q)}$ .

Acyclic Conjunctive Query

A CQ $Q$ is acyclic iff it has a join tree.

Yannakakis and circuits

Trace of Yannakakis algorithm can be seen as a $\{\times,\mathsf{dec}\}\text{-circuit}$ , see [Olteanu, Závodný].

A DPLL-like procedure

DPLL size guarantees

If $x_0, \dots, x_n$ is “compatible with a join tree”, produced circuit has size linear in $|\mathbb{D}|$ .

Fixing $x_0, x_1$ :

decision tree with at most $\#R$ leaves
breaks $Q$ into two connected components
Caching: $Q[x_0=1,x_1=1]$ and $Q[x_0=1,x_1=0]$ yield the same recursive call on the left tree.

This is roughly the caching in Yannakakis seen from above.
Elimination order only, no join tree!

DPLL and Negated Atoms

DPLL Guarantees

$Q(x_1,\dots,x_n) = Q^+ \wedge Q^-$

For $N \subseteq Q^-$ , let $Q_N = Q^+ \wedge \bigwedge_{\neg S \in N} S$ .

If $x_1,\dots,x_n$ is good for every $Q_N$ then DPLL returns a circuit of size linear in $|\mathbb{D}|$ (and poly in $|Q|$ ).

In particular, $Q_N$ is acyclic for every $N$ .

If $x_1,\dots,x_n$ induces a fractional hypertree decomposition of width at most $k$ for every $Q_N$ then DPLL returns a circuit of size $O(|\mathbb{D}|^k)$ (and poly in $|Q|$ ).

Application

For a circuit $C$ on variables $X$ and $|X|=n$ :

Gates	Emptiness	Totality	Size	Enumeration
$\{\mathsf{dec}, \times\}$	$O(\|C\|)$	$O(\|C\|p(n))$	$O(\|C\|p(n))$	$O(\|C\|)$ -preproc $O(p(n))$ -delay
$\{\mathsf{dec}, \times\}$	$\|\mathbb{D}\|p(\|Q\|)$	$\|\mathbb{D}\|p(\|Q\|)$	$\|\mathbb{D}\|p(\|Q\|)$	$\|\mathbb{D}\|p(\|Q\|))$ -preproc $p(\|Q\|)$ -delay

where $Q$ contains negative atoms!

Bonus: circuit produced by DPLL have an extra structure allowing direct access for induced lexicographical order.

Circuit propaganda Conclusion

Circuit are a useful abstraction.
Hard-lifting is compilation, algorithms are usually elementary.
Unify results, similar ideas popped into many communities.
Downside: Structure of the query may be lost during the compilation.

Gates	Emptiness	Totality	Size	Enumeration
$\{\mathsf{dec}, \times\}$	$O(\|C\|)$	$O(\|C\|p(n))$	$O(\|C\|p(n))$	$O(\|C\|)$ -preproc $O(p(n))$ -delay
$\{\mathsf{dec}, \times\}$	$\|\mathbb{D}\|p(\|Q\|)$	$\|\mathbb{D}\|p(\|Q\|)$	$\|\mathbb{D}\|p(\|Q\|)$	$\|\mathbb{D}\|p(\|Q\|))$ -preproc $p(\|Q\|)$ -delay