Building Relational Circuits

We start with a very general definition that serves as a starting point before restricting it into more interesting classes of circuits. A $\{\bowtie ,\overline{\cup }\}\text{-circuit}$ $C$ on attributes $X$ and domain $D$ is defined as a labeled direct acyclic multi-graph (that is, there may be more than one edge between two vertices of the graph) with one distinguished vertex called the output of $C$ and denoted by $\mathrm{𝗈𝗎𝗍}(C)$. The vertices of the underlying DAG of $C$ are called gates. If two gates $g,g^{\prime }$ are connected by a directed edge $g\to g^{\prime }$, we say that $g$ is an input of $g^{\prime }$ and that $g^{\prime }$ is an output of $g$. The gates of $C$ are labeled as follows:

• $\mathrm{■}$

  Every gate $g$ without input (that is, without any incoming edge) is called an input of the circuit and is labeled by either $\perp$, $\top$ or $x/d$ for some attribute $x\in X$ and domain value $d\in D$. If $g$ is labeled by $\top$ or $\perp$, we say that $g$ is a constant input.

• $\mathrm{■}$

  Every other gate (that is, every gate with at least one input) is labeled by either $\overline{\cup }$ or $\bowtie$.

The attributes $\mathrm{attr}(g)$ of a gate $g$ of $C$ are defined to be the set of attributes appearing in at least one input of the subcircuit rooted at $g$. In other words, $\mathrm{attr}(g)=\mathrm{\varnothing }$ if $g$ is labeled by $\top$ or $\perp$, $\mathrm{attr}(g)=\{x\}$ if $g$ is labeled by $x/d$ for some $d\in D$, and $\mathrm{attr}(g)={\bigcup }_{i=1}^k\mathrm{attr}(g_i)$ if $g_1,\mathrm{\dots },g_k$ are the inputs of $g$.

Each gate $g$ computes a relation $\mathrm{𝗋𝖾𝗅}(g)\subseteq D^{\mathrm{attr}(g)}$ defined inductively as:

• $\mathrm{■}$

  If $g$ is an input then: either it is labeled by $\perp$ and $\mathrm{𝗋𝖾𝗅}(g)=\mathrm{\varnothing }$, or by $\top$ and $\mathrm{𝗋𝖾𝗅}(g)=\{⟨⟩\}$, or by $x/d$ then $\mathrm{𝗋𝖾𝗅}(g)=\{⟨x/d⟩\}$.

• $\mathrm{■}$

  If $g$ has input $g_1,\mathrm{\dots },g_k$ and is labeled by $\bowtie$ then $\mathrm{𝗋𝖾𝗅}(g)=\mathrm{𝗋𝖾𝗅}(g_1)\bowtie \mathrm{\dots }\bowtie \mathrm{𝗋𝖾𝗅}(g_k)$.

• $\mathrm{■}$

  If $g$ has input $g_1,\mathrm{\dots },g_k$ and is labeled by $\overline{\cup }$ then $\mathrm{𝗋𝖾𝗅}(g)=\mathrm{𝗋𝖾𝗅}(g_1)\overline{\cup }\mathrm{\dots }\overline{\cup }\mathrm{𝗋𝖾𝗅}(g_k)$.

The relation $\mathrm{𝗋𝖾𝗅}(C)$ computed by $C$ is defined as $\mathrm{𝗋𝖾𝗅}(C):=\mathrm{𝗋𝖾𝗅}(\mathrm{𝗈𝗎𝗍}(C))\times D^{X\setminus Z}$ where $Z=\mathrm{attr}(\mathrm{𝗈𝗎𝗍}(C))$. If $X$ is not made explicit, we simply let $\mathrm{𝗋𝖾𝗅}(C)=\mathrm{𝗋𝖾𝗅}(\mathrm{𝗈𝗎𝗍}(C))$.

The size $|C|$ of a $\{\bowtie ,\overline{\cup }\}\text{-circuit}$ is defined as the number of edges of its underlying graph. Sometimes, the size of circuits is defined as the number of gates, but this definition is often less natural. Indeed, an algorithm visiting every edge of the circuit is linear in the size of the input but no necessarely linear in the number of gates in the circuit since there may be $O(N^2)$ edges in a circuit with $N$ nodes.

The family of $\{\bowtie ,\overline{\cup }\}\text{-circuit}$s is not interesting from a complexity point of view as they are more general than join queries. We now restrict $\{\bowtie ,\overline{\cup }\}\text{-circuit}$s in order to find representations of relations that are more tractable than join queries.

The main syntactic restriction that we impose on relational circuits is the following: in a $\{\bowtie ,\overline{\cup }\}\text{-circuit}$, we say that a $\bowtie$-gate $g$ is a Cartesian product gate, or $\times$-gate for short, if $\mathrm{attr}(g_1)\cap \mathrm{attr}(g_2)=\mathrm{\varnothing }$ for every distinct input $g_1,g_2$ of $g$. Observe that in this case, if $g_1,\mathrm{\dots },g_k$ are the inputs of $g$, then $\mathrm{𝗋𝖾𝗅}(g)={\times }_{i=1}^k\mathrm{𝗋𝖾𝗅}(g_i)$. A $\{\times ,\overline{\cup }\}\text{-circuit}$ is a $\{\bowtie ,\cup \}\text{-circuit}$ where every $\bowtie$-gate is a $\times$-gate. Obviously, given a $\{\bowtie ,\cup \}\text{-circuit}$ $C$, we can check whether it is a $\{\times ,\overline{\cup }\}\text{-circuit}$ in time $O(|C|\cdot |X|)$ by computing $\mathrm{attr}(g)$ for every $g$.

Another useful restriction regarding relational circuits is to restrict how $\overline{\cup }$-gates are operating. Indeed, $\overline{\cup }$-gates are cumbsersome to use because they force us to keep track of the attributes of each gate and to be explicit about the domain. We hence define a $\{\times ,\cup \}\text{-circuit}$ as a $\{\times ,\overline{\cup }\}\text{-circuit}$ such that for every $\overline{\cup }$-gate $g$ with input $g_1,\mathrm{\dots },g_k$, we have $\mathrm{attr}(g_1)=\mathrm{\cdots }=\mathrm{attr}(g_k)$. In this case, one can easily check that $\mathrm{𝗋𝖾𝗅}(g)={\bigcup }_{i=1}^k\mathrm{𝗋𝖾𝗅}(g_i)$.

While $\{\times ,\cup \}\text{-circuit}$s allow for enumeration, one can observe that they do not allow to efficiently compute statistics on $\mathrm{𝗋𝖾𝗅}(C)$. Indeed, one can easily see that it is #P-hard to compute $|\mathrm{𝗋𝖾𝗅}(C)|$ when $C$ is a $\{\times ,\cup \}\text{-circuit}$ given on the input, by a direct reduction to the problem #DNF, though, if one is interested in approximation, this problem admits an FPRAS [36]. The hardness of counting mainly stems from the fact that unions of relations in the circuit may overlap, which makes the cardinality of the union hard to estimate.

To avoid it, we need an extra property: given a $\{\times ,\cup \}\text{-circuit}$ $C$, we say that a $\cup$-gate $g$ with inputs $g_1,\mathrm{\dots },g_k$ is deterministic¹¹1We keep here the usual terminology from knowledge compilation [22] and from seminal work on factorized databases [43], though the naming is slightly misleading, as it is not deterministic in the usual sense. “Unambiguous” would be a better term. if for every , we have $\mathrm{𝗋𝖾𝗅}(g_i)\cap \mathrm{𝗋𝖾𝗅}(g_j)=\mathrm{\varnothing }$. In this case, observe that ${\bigcup }_{i=1}^k\mathrm{𝗋𝖾𝗅}(g_i)$ is a disjoint union, denoted by ${⨄}_{i=1}^k\mathrm{𝗋𝖾𝗅}(g_i)$. A deterministic $\cup$-gate will be denoted by $\uplus$. As for union, we also have ${\overline{\uplus }}_D$ to denote the union of relations on different attributes but having no common tuple on their shared attributes. A $\{\times ,\uplus \}\text{-circuit}$ is then a $\{\times ,\cup \}\text{-circuit}$ where every $\cup$-gate is deterministic.

Given a $\{\times ,\uplus \}\text{-circuit}$, we can now compute $|\mathrm{𝗋𝖾𝗅}(C)|$ with $O(|C|)$ arithmetic operations using a straightforward dynamic programming, see Section 3.2 for details.

One can see that checking whether a given $\cup$-gate is deterministic is not easy. Indeed, it is a semantic property on the relation computed by each gate and not an easy-to-check syntactic property. In practice, we know that a $\cup$-gate is deterministic because the algorithm which built the circuit formally guarantees that this is the case. While in some cases, determinism may depend on complex reasons, in every algorithm we will describe in this document, determinism is ensured because some attribute $x$ has a different value in each subcircuit. To model this very specific case, we introduce the notion of decision-gate: a decision-gate $g$ is a gate labeled by a variable $x$ and each incoming edge $e$ of $g$ is labeled by a value $d_e\in D$. Moreover, if $e_1=g_1\to g,\mathrm{\dots },e_k=g_k\to g$ are the incoming edges of $g$ respectively labeled by $d_1,\mathrm{\dots },d_k$, then for every , $d_i\ne d_j$ and $x\notin \mathrm{attr}(g_i)$. We define $\mathrm{𝗋𝖾𝗅}(g)={⨄}_{i=1}^k\{⟨x/d_i⟩\}\times \mathrm{𝗋𝖾𝗅}(g_i)$. Clearly, by definition, we could rewrite every decision-gate with $k$ incoming edges using only $\uplus$-gates and $\times$-gates²²2Observe that for this, we need the condition that $x\notin \mathrm{attr}(g_i)$. and at most $3k$ edges, hence decision-gates is only a useful syntactic sugar. A $\{\times ,\text{dec}\}\text{-circuit}$ $C$ is a circuit whose every gate are either Cartesian products or decision-gates.

Different paths of decision-gates in a $\{\times ,\text{dec}\}\text{-circuit}$ may use different order. For example, we could have a path testing variable $x$ then $y$ then $z$ and another path testing $x$ then $z$ then $y$. That said, the algorithm we give in Section 4 will always test variables in the same order, and we will actually use this fact to recover some results on direct access. Let $\pi =(x_1,\mathrm{\dots },x_n)$ be an order on $X$. We say that a $\{\times ,\text{dec}\}\text{-circuit}$ on attributes $X$ respects order $\pi$ if for every decision-gate $g$ labeled by $x_i$ and $g^{\prime }$ an input of $g$, we have $\mathrm{attr}(g^{\prime })\subseteq \{x_{i+1},\mathrm{\dots },x_n\}$.

We observe here that some $\uplus$-gates are not decision-gates. For example, let $g_0,g_1$ be gates such that $\mathrm{𝗋𝖾𝗅}(g_0)=\{⟨x/0,y/0⟩,⟨x/1,y/1⟩\}$ and $\mathrm{𝗋𝖾𝗅}(g_1)=\{⟨x/0,y/1⟩,⟨x/1,y/0⟩\}$, then a $\cup$-gate with input $g_0,g_1$ is deterministic because $\mathrm{𝗋𝖾𝗅}(g_0)$ only contains tuples with an even number of ones and $\mathrm{𝗋𝖾𝗅}(g_1)$ with an odd number of ones but it cannot be seen as a decision-gate since both $x$ and $y$ can take values $0$ and $1$ in $\mathrm{𝗋𝖾𝗅}(g_0)$ and in $\mathrm{𝗋𝖾𝗅}(g_1)$. In this case, determinism is witnessed by a parity argument. Actually, this idea forms the base of the argument to show that $\{\times ,\uplus \}\text{-circuit}$ are exponentially more succinct than $\{\times ,\text{dec}\}\text{-circuit}$ [9].

While we can be flexible on the syntax of relational circuits, useless gates may induce complexity. In particular, constant gates ($\perp$-gates and $\top$-gates) may induce hidden costs. We observe that we can remove them in the circuit with a linear time procedure as follows: we remove every input of $\times$-gates labeled by $\top$ and every input of $\cup$-gate labeled by $\perp$ without changing the relation they compute. We also replace a $\times$-gates with a $\perp$-labeled input by a $\perp$-gate and a $\cup$-gate with a $\top$-labeled input by a $\top$-gate. Each change reduces the size of the circuit by at least one, hence applying these transformations iteratively finishes and returns a circuit without constant gates.

We also observe here that $\{\times ,\overline{\cup }\}\text{-circuit}$s may also be transformed into $\{\times ,\cup \}\text{-circuit}$ in time $O(|X|\cdot |C|)$: we can indeed precompute $\mathrm{attr}(g)$ for every gate of $C$ and, for each $\overline{\cup }$-gate $g$ of $C$ with input $g^{\prime }$, we can add a $\times$-gate $g^{\prime \prime }$ between $g^{\prime }$ and a circuit computing $D^{{\mathrm{\Delta }}_i}$ where $\mathrm{\Delta }=\mathrm{attr}(g)\setminus \mathrm{attr}(g^{\prime })$ and plug $g^{\prime \prime }$ into $g$ instead of $g^{\prime }$. This operation is known as smoothing in knowledge compilation [23] and can sometimes be costly if the number of variables is high. One can avoid it in some cases [46, 4]. In this work, the algorithm we will present naturally build $\{\times ,\text{dec}\}\text{-circuit}$ so we will not focus much on $\{\times ,\overline{\cup }\}\text{-circuit}$ nor $\{\times ,\overline{\uplus }\}\text{-circuit}$.

Given a $\{\times ,\cup \}\text{-circuit}$ $C$ on attributes $X$ and domain $D$, one of the first tasks one can do is to list every tuple of $\mathrm{𝗋𝖾𝗅}(C)$. To measure the complexity of such algorithm, it is customary to analyze the time spent between two outputs of the algorithm, which we call the delay. Sometimes, we need to precompute some values on the circuit before starting. This time will be accounted for as preprocessing time.

It is easy to see that we can find a tuple in $\mathrm{𝗋𝖾𝗅}(C)$ in time $O(|C|)$ by inductively constructing for each $g$, a tuple ${\tau }_g$ in $\mathrm{𝗋𝖾𝗅}(g)$ for every gate $g$ in the circuit, or report that $\mathrm{𝗋𝖾𝗅}(g)=\mathrm{\varnothing }$. But we can even output every tuple in $\mathrm{𝗋𝖾𝗅}(C)$ with delay $O(|X|\cdot |C|)$ as follows. The main idea is to observe that giving a tuple $\tau$ over $Y\subseteq X$ and $x\in X\setminus Y$, we can find in time $O(|C|)$ the subset $D^{\prime }\subseteq D$ such that $D^{\prime }$ is the set of domain values for which $\tau \times ⟨x/d⟩$ can be extended to a full tuple of $\mathrm{𝗋𝖾𝗅}(C)$. This can be done by plugging every variable in $Y$ to their value (ie, replace input $y/d$ by $\top$ if $d=\tau (y)$ and by $\perp$ otherwise) and every input in $z\in X\setminus (Y\cup \{x\})$ by $\top$. It gives a $\{\times ,\cup \}\text{-circuit}$ on variable $\{x\}$ whose computed relation is exactly $D^{\prime }$. By propagating constants in the circuit in time $O(|C|)$, it simplifies to a circuit where $D^{\prime }$ can be read directly as the remaining input of the form $x/d$. This is enough to implement a flashlight search to enumerate $\mathrm{𝗋𝖾𝗅}(C)$ by constructing each tuple one variable at a time, without never exploring partial tuples that cannot be extended to full solutions: we start by computing every possible values $D^{\prime }$ that $x_1$ can take in $\mathrm{𝗋𝖾𝗅}(C)$, then pick $d\in D^{\prime }$ and find every value of $x_2$ can take when $x_1$ is set to $d$ etc. This method ensures that every partial tuple we built can be extended to a full tuple in $\mathrm{𝗋𝖾𝗅}(C)$. Once such a tuple is found, we backtrack to the last variable for which it remains at least one unexplored value. Between two outputs, we do at most $|X|$ oracle calls to the previously describe procedure, hence a delay of $O(|C|\cdot |X|)$. This method can even be extended to the case where one wants to output the tuples by increasing weights, see [3] for details.

The delay of this algorithm may be too high to recover the existing enumeration bounds from the database literature, as we would like to have a complexity that only depends on the number of variables of $C$. We show that in the case of $\{\times ,\uplus \}\text{-circuit}$, we get better bounds. Indeed, to enumerate $\mathrm{𝗋𝖾𝗅}(g)$ when $g$ is a $\uplus$-gate with inputs $g_1,\mathrm{\dots },g_k$, one only needs to successively enumerate $\mathrm{𝗋𝖾𝗅}(g_i)$ for every $1\le i\le k$. The delay is thus $\max d_i$ where $d_i$ is the delay to enumerate $\mathrm{𝗋𝖾𝗅}(g_i)$. To enumerate $\mathrm{𝗋𝖾𝗅}(g)$ where $g$ is a $\times$-gate with input $g_1,\mathrm{\dots },g_k$, we enumerate one tuple from $\mathrm{𝗋𝖾𝗅}(g_1)$, then every tuple from $\mathrm{𝗋𝖾𝗅}(g_2)\times \mathrm{\cdots }\times \mathrm{𝗋𝖾𝗅}(g_k)$. The delay between two outputs is ${\sum }_i{d}_i$ since it is the time needed to find the first tuple. If we again ensure that each $\times$-gate has no trivial input, we can show that the delay is $O(nh)$ where $h$ is the depth of the circuit and $n$ the number of variables. Observe that in the worst-case, the depth $h$ could be of the order of $|C|$. We can however always rewrite into a circuit with depth at most $n$ by ensuring the every $\uplus$-gate has no other $\uplus$-gate as input. Doing it naively may however increase the size of the circuit quadratically. Amarilli, Bourhis, Jachiet and Mengel proposed a work-around in [4] to quickly find the gates that could be reached from a $\uplus$-gate in linear time allowing for enumeration with delay $O(n)$ after linear preprocessing.

Observe that in the particular case of $\{\times ,\text{dec}\}\text{-circuit}$, the previous algorithm directly gives $O(n)$ delay as long as for every $\times$-gate $g$ with input $g_1,\mathrm{\dots },g_k$, we have $\mathrm{attr}(g_i)\ne \mathrm{\varnothing }$, which can be ensured with linear time preprocessing by simply removing constants in the circuit.

Given a $\{\times ,\uplus \}\text{-circuit}$, we can now compute $|\mathrm{𝗋𝖾𝗅}(C)|$ with $O(|C|)$ arithmetic operations using a straightforward dynamic programming. For each gate $g$, we compute $|\mathrm{𝗋𝖾𝗅}(g)|$ inductively: if $g$ is an input, then $|\mathrm{𝗋𝖾𝗅}(g)|=0$ if $g$ is a $\perp$-gate and $|\mathrm{𝗋𝖾𝗅}(g)|=1$ otherwise. If $g$ is a $\times$-gate with input $g_1,\mathrm{\dots },g_k$ , then $|\mathrm{𝗋𝖾𝗅}(g)|={\prod }_{i=1}^k|\mathrm{𝗋𝖾𝗅}(g_i)|$. If $g$ is a $\uplus$-gate with input $g_1,\mathrm{\dots },g_k$ then $|\mathrm{𝗋𝖾𝗅}(g)|={\sum }_{i=1}^k|\mathrm{𝗋𝖾𝗅}(g_i)|$. Hence, we can compute $|\mathrm{𝗋𝖾𝗅}(C)|$ with $O(|C|)$ arithmetic operations. For every $g$, $|\mathrm{𝗋𝖾𝗅}(g)|$ does not exceed ${|D|}^{|X|}$, where $D$ is the domain of $C$ and $X$ its attributes. Hence, each number can be stored in at most $|X|$ registers in a RAM machine, and each arithmetic operation can be performed in time $O(|X|\log |X|)$, resulting in a final complexity of $O(|X|\log |X|\cdot |C|)$. For $\{\times ,\overline{\uplus }\}\text{-circuit}$, we have a similar result but we need to precompute $\mathrm{attr}(g)$ for every gate $g$. If $g$ is a $\overline{\cup }$-gate, we have $|\mathrm{𝗋𝖾𝗅}(g)|={\sum }_{i=1}^k|\mathrm{𝗋𝖾𝗅}(g_i)|\cdot {|D|}^{{\delta }_i}$ where ${\delta }_i=|\mathrm{attr}(g)\setminus \mathrm{attr}(g_i)|$.

Interestingly the previous algorithm can be leveraged into a uniform sampling algorithm. Assume $|\mathrm{𝗋𝖾𝗅}(g)|$ has been precomputed for every gate $g$ of $C$. If one wants to draw a tuple $\tau \in \mathrm{𝗋𝖾𝗅}(g)$ uniformly, we can do this simple procedure:

• $\mathrm{■}$

  If $g$ is a $\perp$-gate, then fail (this case should not happen unless $\mathrm{𝗋𝖾𝗅}(C)=\mathrm{\varnothing }$).

• $\mathrm{■}$

  If $g$ is a $\top$-gate or a gate labeled by $x/d$, then return the only tuple in $\mathrm{𝗋𝖾𝗅}(g)$.

• $\mathrm{■}$

  If $g$ is a $\uplus$-gate with input $g_1,\mathrm{\dots },g_k$, then draw $1\le i\le k$ with probability $\frac{|\mathrm{𝗋𝖾𝗅}(g_i)|}{|\mathrm{𝗋𝖾𝗅}(g)|}$ and uniformly sample in $\mathrm{𝗋𝖾𝗅}(g_i)$.

• $\mathrm{■}$

  If $g$ is a $\times$-gate with input $g_1,\mathrm{\dots },g_k$ then return ${\tau }_1\times \mathrm{\cdots }\times {\tau }_k$ where ${\tau }_i$ is sampled uniformly from $\mathrm{𝗋𝖾𝗅}(g_i)$.

In the case of $\{\times ,\uplus \}\text{-circuit}$, without further assumptions, we can show that this procedure runs in time $O(|X|\cdot h)$ where $h$ is the depth of the circuit, that is, the longest path from the output to an input of $C$. If $C$ is a $\{\times ,\text{dec}\}\text{-circuit}$ and if we have removed trivial inputs from $\times$-gate (that is, for every $\times$-gate $g$, $\mathrm{attr}(g)\ne \mathrm{\varnothing }$), then we can show that this procedure runs in time $O(|X|)$.

We can go one step further and compute a numbering on $\mathrm{𝗋𝖾𝗅}(C)$ so that we can efficiently access $\mathrm{𝗋𝖾𝗅}(C)[i]$, as if it was a table. This kind of algorithm have been called “direct access algorithm” [8, 16, 25, 17, 14]. We define an order on $\mathrm{𝗋𝖾𝗅}(C)$ by inductively defining, for every gate $g$ of $C$, a one-to-one mapping $I_g:\mathrm{𝗋𝖾𝗅}(g)\to [0,N_g-1]$ where $N_g=|\mathrm{𝗋𝖾𝗅}(g)|$. We call $I_g$ an index on $\mathrm{𝗋𝖾𝗅}(g)$. We first assume for every gate $g$, its input $g_1,\mathrm{\dots },g_k$ are listed in some arbitrary order. We now define the index functions inductively.

• $\mathrm{■}$

  If $g$ is an input, not labeled by $\perp$, we define $I_g(\tau )=0$, for $\tau$ the only assignment in $\mathrm{𝗋𝖾𝗅}(g)$.

• $\mathrm{■}$

  If $g$ is a $\uplus$-gate with input $g_1,\mathrm{\dots },g_k$, let $\tau \in \mathrm{𝗋𝖾𝗅}(g)$. We define $I_g(\tau )={\sum }_{i=1}^{j-1}{N}_i+I_{g_j}(\tau )$ where $N_i=|\mathrm{𝗋𝖾𝗅}(g_i)|$ for every $i\le k$ and $j$ is the only value in $[k]$ such that $\tau \in \mathrm{𝗋𝖾𝗅}(g_j)$. In other words, we order $\mathrm{𝗋𝖾𝗅}(g)$ by first taking every tuple from $g_1$, then $g_2$ etc.

• $\mathrm{■}$

  If $g$ is a $\times$-gate with input $g_1,\mathrm{\dots },g_k$, let $\tau \in \mathrm{𝗋𝖾𝗅}(g)$. Let ${\tau }_i={\tau |}_{\mathrm{attr}(g_i)}$ and $N_i=|\mathrm{𝗋𝖾𝗅}(g_i)|$. We by ${\tau }_i\in \mathrm{𝗋𝖾𝗅}(g_i)$ for every $i\le k$. We define

  $$I_g(\tau ){=}_{\mathrm{𝖽𝖾𝖿}}\sum _{j=1}^k{I}_{g_j}({\tau }_j)\prod _{i=j+1}^k{N}_i,$$

  that is $I_g(\tau )$ is the rank of $(I_{g_1}({\tau }_1),\mathrm{\dots },I_{g_k}({\tau }_k))$ in $[N_1]\times \mathrm{\cdots }\times [N_k]$ ordered lexicographically.

Interestingly , we can revert this indexing structure. Indeed, given $I\in \{0,\mathrm{\dots },|\mathrm{𝗋𝖾𝗅}(g)|-1\}$, we can efficiently compute $I_g^{-1}(I)$, that is, the tuple $\tau \in \mathrm{𝗋𝖾𝗅}(g)$ such that $I_g(\tau )=I$. Indeed, assume we have precomputed, for every $\uplus$-gate $g$ with input $g_1,\mathrm{\dots },g_k$ and $j\le k$, the value $l_j={\sum }_{i=1}^j|\mathrm{𝗋𝖾𝗅}(g_i)|$ and stored them in an ordered table $L_g=[l_1,\mathrm{\dots },l_k]$. We also precompute $|\mathrm{𝗋𝖾𝗅}(g)|$ for every $\times$-gate $g$.

First assume $g$ is a $\uplus$-gate and let $I\le |\mathrm{𝗋𝖾𝗅}(g)|$. To find the $I^{th}$ tuple of $\mathrm{𝗋𝖾𝗅}(g)$, we need look for the smallest $j$ such that $l_j\le I$ which can be done via a binary search with $O(\log k)=O(\log |C|)$ comparisons, each comparison being on integers smaller than ${|D|}^{|X|}$. Then we inductively output the $I_{g_i}^{-1}(I-l_j)$ tuple of $g_i$.

Now assume $g$ is a $\times$-gate with input $g_1,\mathrm{\dots },g_k$ and let $I\le |\mathrm{𝗋𝖾𝗅}(g)|$. We are looking for $\tau ={\tau }_1\times \mathrm{\cdots }\times {\tau }_k\in \mathrm{𝗋𝖾𝗅}(g_1)\times \mathrm{\cdots }\times \mathrm{𝗋𝖾𝗅}(g_k)$ such that

where $N_i=|\mathrm{𝗋𝖾𝗅}(g_i)|$ has been precomputed already. Observe that $I_{g_k}({\tau }_k)=Imod{N}_k$ since every other term of the sum can be divided by $N_k$. Similarly, $I_{g_{k-1}}({\tau }_{k-1})=(I/N_k)mod{N}_{k-1}$ where $I/N_k$ is the quotient of the division of $I$ by $N_k$. We similarly have $I_{g_j}({\tau }_j)=(I/{\prod }_{i=j+1}^k{N}_i)mod{N}_j$. Hence we can compute inductively ${\tau }_j$ as $I_{g_j}^{-1}((I/{\prod }_{i=j+1}^k{N}_i)mod{N}_j)$.

Hence, after a precomputation step of $O(|X|\cdot |C|)$, we can, on input $I$, fail if $I>|\mathrm{𝗋𝖾𝗅}(C)|$, and otherwise, output $\tau =I_{\mathrm{𝗈𝗎𝗍}(C)}^{-1}(I)$ with $O(h|X|\log |C|)$ comparisons or arithmetic operations on integers smaller than ${|D|}^{|X|}$, where $h$ is the depth of $C$. Hence, in total time $O(h{|X|}^2\cdot (\log |X|)\cdot (\log |C|)\cdot (\log |D|))$.

This direct access algorithm has interesting consequences. It allows to enumerate $\mathrm{𝗋𝖾𝗅}(C)$ in a uniformly chosen order, or, equivalently, perform sampling without replacement: we sample or randomly enumerate values in $\{1,\mathrm{\dots },|\mathrm{𝗋𝖾𝗅}(C)|\}$, and output the corresponding tuple in $\mathrm{𝗋𝖾𝗅}(C)$. This can be done efficiently by adapting the Fisher-Yates shuffle algorithm in a lazy way, as in [17].

We again get better complexity bounds for $\{\times ,\text{dec}\}\text{-circuit}$s. Indeed, in this case, we can bound the arity of $\uplus$-gates (in the form of decision-gates) by the size of the domain $D$ and we can show that we can recover the $I^{th}$ element of $\mathrm{𝗋𝖾𝗅}(C)$ with $O(|X|\log |D|)$ arithmetic operations because each recursive call is done on gates having strictly less attributes, hence a total time of $O({|X|}^2\cdot (\log |X|)\cdot (\log |D|))$. More interestingly, if the circuit respects order $(x_1,\mathrm{\dots },x_n)$, then we can actually solve the direct access problem for the lexicographical order induced by $(x_1,\mathrm{\dots },x_n)$ on $D^X$ with a slightly more involved access technique that can still be executed with $O(|X|\log |D|)$ arithmetic operations and comparisons. Indeed, in this case, given a tuple $\tau$ over attributes $\{x_1,\mathrm{\dots },x_k\}$ with $k\le n$, we can find how many tuple from $\mathrm{𝗋𝖾𝗅}(C)$ are smaller than $\tau$ in the lexicographical order. We can use it to build the $I^{th}$ element of $\mathrm{𝗋𝖾𝗅}(C)$ by discovering it one variable at a time, using counting queries to find the value of the next variable with a binary search, see [14] for details.

We conclude this section by summarizing the results we will use the most in the context of databases:

Relational circuits originated under the name factorized databases in the seminal paper by Olteanu and Závodný [42]. In this document, we decided to use the name relational circuits to describe the object used to represent the relation, in contrast to the term factorized databases which, in our opinion, describe a set of techniques covering, in particular, the notion of relational circuit. In this work, the class of $\{\times ,\cup \}\text{-circuit}$s appears under the name factorized representation with definitions, or d-representations, while $\{\times ,\uplus \}\text{-circuit}$ have been introduced as deterministic d-representations. In [43], the definition explicitly enforces unions to be defined over gates having the same attributes. We decided to deviate from the original terminology because we think that $\{\times ,\cup \}\text{-circuit}$ is more natural than d-representation and it allows to be more precise on the syntactic restriction we want to enforce on the circuit, where the term d-representation is too general.

We want to clearly distinguished in this paper between the syntactic properties of relational circuits and the algorithm constructing the circuits. This is why, in this work, we decided to separate the notion of relational circuits that simply represent relations, sometimes with specific semantics or syntactic restrictions, and how such relational circuits are produced.

Syntactically restricted Boolean circuits have been used for representing Boolean functions since the 80s, at first through the lens of ordered binary decision diagrams [13] (which can be seen as $\{\text{dec}\}$-circuits) and then later generalized to restricted Boolean circuits under the name Decomposable Negation Normal Form (DNNF) [23, 21, 22] with decomposable $\wedge$-gates, corresponding to $\times$-gates, and deterministic $\vee$-gates, corresponding to $\overline{\uplus }$-gates on domain $\{0,1\}$. The similarity of knowledge compilation and factorized databases has been observed in [40] but the connections between classes of circuit is not covered. We provide a comparison in Table 1 using the circuit notations from the previous sections and the main classes studied in knowledge compilation. Previous work have been using DNNF in many areas of computer for enumeration by encoding database queries answers into DNNF [4, 3], probabilistic databases by representing the Boolean provenance a query with DNNFs [41, 10, 9, 48], for computing Shapley scores [6, 11], see [5] for a more detailed introduction on the applications of circuits in databases.

We do not include definitions of the Boolean counterpart of relational circuits and refer to [23]. that one can also recover them by simply taking the corresponding class of relational circuit and specializing them over domain $\{0,1\}$: indeed each line illustrates the correspondence between a Boolean circuit and relational circuits as follows: when considering circuits on the right column on domain $D=\{0,1\}$, it corresponds exactly to the Boolean circuit on the left.

The correspondence actually works both ways: for non-binary domain $D=\{d_0,\mathrm{\dots },d_{k-1}\}$, we can encode $D$ with bitstrings over $b=\lceil \log k\rceil$ bits by representing $d_i$ with the binary representation of $i$ over $b$ bits. Hence, given a $\{\bowtie ,\cup \}\text{-circuit}$ $C$ over attributes $X=\{x_1,\mathrm{\dots },x_n\}$ and domain $D=\{d_0,\mathrm{\dots },d_{k-1}\}$, we can convert it into an NNF over variables $\tilde{X}=\{x_1^0,\mathrm{\dots },x_1^{b-1},\mathrm{\dots },x_n^0,\mathrm{\dots },x_n^{b-1}\}$ by replacing every input $⟨x_i/d_j⟩$ by a circuit over variables $x_i^0,\mathrm{\dots },x_i^{b-1}$ accepting only the assignment encoding $j$ in binary. This can easily be done by $\{\text{dec}\}$-circuit of size $2b$. It can be encoded in any NNF subclass from Table 1, showing that every relation circuit on attributes $X$ and domain $D$ from the right column can be naturally casted into an NNF from the left column with an additional increase of at most $|X|\log |D|$ increase.

We conclude this section by observing that most relational circuits, with relevant syntactic restrictions, can be understood as automaton on finite language. For example, ordered $\{\text{dec}\}$-circuits correspond to finite state automaton without loop, hence on a finite language, while Context-Free grammar could be associated to restricted $\{\times ,\cup \}\text{-circuit}$ where $\times$-gates are only allowed to split variables according to some total order. Other syntactic restriction of $\{\times ,\cup \}\text{-circuit}$ not presented in this paper can also be shown to correspond to tree automaton. These connections have been studied in [33, 2].

Let $Q$ be a join query and $𝒯$ a join tree for $Q$. Assume $𝒯$ is rooted at an arbitrary node, and let $t$ be a node of $𝒯$. We let ${𝒯}_t$ be the subtree of $𝒯$ rooted in $t$ and $Q_{\le t}$ to be the join query whose atoms are exactly the atoms appearing in ${𝒯}_t$. The crux of Yannakakis algorithm is the following observation: if $t_1,t_2$ are two children of $t$, then $\mathrm{var}(Q_{\le t_1})\cap \mathrm{var}(Q_{\le t_2})\subseteq \mathrm{var}(R_t)$. Indeed, every path from ${𝒯}_{t_1}$ to ${𝒯}_{t_2}$ must go through $t$. Hence if $x$ appears on both side, by connectedness, it must be in $\mathrm{var}(R_t)$ too.

Let $t_1,\mathrm{\dots },t_k$ be the children of $t$ in $𝒯$. An answer $\sigma$ of $Q_{\le t}$ have the following shape:

• $\mathrm{■}$

  Projected over $\mathrm{var}(R_t)$, they must be equal to some tuple $\tau$ in $R_t$.

• $\mathrm{■}$

  Projected over $\mathrm{var}(Q_{\le t_i})$, they must be an answer of $Q_{\le t_i}$ that extends $\tau$.

In other words, an answer of $Q_{\le t}$ is of the form $\tau \times {\tau }_1\times \mathrm{\cdots }\times {\tau }_k$ where ${(\tau \times {\tau }_i)|}_{V_i}\in \mathrm{𝖺𝗇𝗌}(Q_{\le t_i})$ where $V_i=\mathrm{var}(Q_{\le t_i})$. In other words, we have established:

If we further develop each term of the previous Cartesian product and if we let ${\mathrm{\Delta }}_i=\mathrm{var}(R_{t_i})\setminus \mathrm{var}(R_t)$, we have: µ

In the original Yannakakis algorithm, these relations are used to dynamically maintain the following information: does $Q_{\le t}$ have an answer extending $\tau \in R_t$? Indeed, Equation 1 tells us that $Q_{\le t}$ has an answer extending $\tau$ if and only if for every $i\le k$, $Q_{\le t_i}$ has an answer extending $\tau$, which by Equation 2 is equivalent to the fact that $Q_{\le t_i}$ has an answer extending $\sigma$ for some $\sigma \in R_{t_i}$ with $\sigma \simeq \tau$. In Yannakakis algorithm, the latter has been precomputed and hence, we can quickly decide in time $O(k\cdot |\mathrm{var}(R_t)|)$ whether $Q_{\le t}$ has an answer extending $\tau$ for every $\tau$. When the algorithm reaches the root $r$ of $𝒯$, $Q_{\le r}=Q$ and we can decide whether $Q$ has an answer.

But Equations 1 and 2 can also be seen as a way to build $\mathrm{𝖺𝗇𝗌}(Q_{\le t})/\tau$ for every $\tau \in R_t$ from the relations $\mathrm{𝖺𝗇𝗌}(Q_{\le t_i})/\sigma$ for every $\sigma \in R_{t_i}$, by using decision-gates and one Cartesian product gate. The circuit is build in a bottom-up fashion from the leaves of $𝒯$ to its root. We build a circuit having the following property: for each node $t$ of $𝒯$ and $\tau \in R_t$, there is a gate $v_t^{\tau }$ computing $\mathrm{𝖺𝗇𝗌}(Q_{\le t})/\tau$. If $t$ is a leaf of $𝒯$, $Q_{\le t}$ only has one atom $R_t$. Hence, for every $\tau \in R_t$, $\mathrm{𝖺𝗇𝗌}(Q_t)/\tau =\{⟨⟩\}$ is the relation containing only the empty tuple. Hence, we define $v_t^{\tau }$ as a $\top$-gate.

Now if $t$ has children $t_1,\mathrm{\dots },t_k$, we let $\tau \in R_t$. We first create gates to compute $\mathrm{𝖺𝗇𝗌}(Q_{\le t_i})/\tau$. By Equation 2, we can build a tree of decision-gates on attributes ${\mathrm{\Delta }}_i$, rooted in a gate $w_i^{\tau }$ whose leaves correspond to assignment ${\sigma }_{{\mathrm{\Delta }}_i}$ for every $\sigma \in R_{t_i}$ such that $\sigma \simeq \tau$. Each leaf is connected to the gate $v_{t_i}^{\sigma }$ that has been inductively constructed and computes, by induction, $\mathrm{𝖺𝗇𝗌}(Q_{\le t_i})/\sigma$. By Equation 2, $w_i^{\tau }$ computes $\mathrm{𝖺𝗇𝗌}(Q_{\le t_i})/\tau$. Now, we simply define $v_t^{\tau }$ as a Cartesian product gate ${\times }_{i=1}^k{w}_i^{\tau }$, and by Equation 2, it computes $\mathrm{𝖺𝗇𝗌}(Q_{\le t})/\tau$.

To be efficient, observe that if ${\tau }_1,{\tau }_2\in R_t$ and ${{\tau }_1|}_{\mathrm{var}(R_{t_i})}={{\tau }_2|}_{\mathrm{var}(R_{t_i})}$, then $\mathrm{𝖺𝗇𝗌}(Q_{\le t_i})/{\tau }_1=\mathrm{𝖺𝗇𝗌}(Q_{\le t_i})/{\tau }_2$, hence we can use $w_i^{{\tau }_1}$ for both, without duplicating the gates.

At the root $r$ of $𝒯$, we have for every $\tau \in R_r$, a gate $v_r^{\tau }$ computing $\mathrm{𝖺𝗇𝗌}(Q)/\tau$. We hence add a tree of decision-gates rooted in a gate $v_r$ whose leaves correspond to $\tau$ for every $\tau \in R_r$ and plug it to $v_r^{\tau }$ directly. Gate $v_r$ computes $\mathrm{𝖺𝗇𝗌}(Q)$ and we choose it to be the output of $C$.