<p>It essentially depends on what you mean by "evaluating this join". If you want to compute the whole table, then the <span class="math-container">$2^n$</span> blow-up is unavoidable, just because you need to store all these values. </p>

<p>However, given an acyclic query, you can compute the "semi-join" in time linear in the size of the data and linear in the size of the query. The semi-join is the projection of the results on the variables you still need to finish the computation. In your case, you inductively compute a relation <span class="math-container">$B_i = \Pi_{A_i,A_{i+1}}(R_1 \bowtie \dots \bowtie R_i)$</span>. In the general case, you compute it inductively on the join tree in a bottom-up fashion and you only keep the variables that appears in the bag you are visiting. More details on this approach could be found in [1] or [2, Chapter 6].</p>

<p>Now you can also enumerate all tuples in the result with a polynomial time delay between two solutions. Even though you need an exponential time to enumerate all solutions, you can guarantee to have enumerated <span class="math-container">$t$</span> solutions after a time  <span class="math-container">$t \times poly(n)$</span>. You can even sometimes (with extra structure) guarantee a constant delay between two solutions. You can read more in [3] or in [4] for a more generic approach. </p>

<p>There is a lot more you can do on acyclic conjunctive queries in polynomial time such as counting the number of tuples in the result [5] (you need to be quantifier free however, or it becomes #P-complete again). One way of uniformly explains these tractability results is through the lens of factorized databases [6]. The paper is quite dense but the main idea boils down to the following: given an acyclic conjunctive query <span class="math-container">$Q$</span> and a database <span class="math-container">$D$</span>, you can compute in time linear in the size of <span class="math-container">$D$</span> and <span class="math-container">$Q$</span>, a circuit computing <span class="math-container">$Q(D)$</span>. This circuit only usess Cartesian products gates and disjoint union gates and its input are small relations. Given such a circuit, you can then show that it is tractable to enumerate the tuples of the relation it represents (you can also count and do many other interesting things).</p>

<h1>References</h1>

<p>[1] Flum, Jörg, Markus Frick, and Martin Grohe. "Query evaluation via tree-decompositions." Journal of the ACM (JACM) 49.6 (2002): 716-752.</p>

<p>[2] Libkin, Leonid. Elements of finite model theory. Springer Science &amp; Business Media, 2013.</p>

<p>[3] Bagan, Guillaume, Arnaud Durand, and Etienne Grandjean. "On acyclic conjunctive queries and constant delay enumeration." International Workshop on Computer Science Logic. Springer, Berlin, Heidelberg, 2007.</p>

<p>[4] Idris, Muhammad, Martín Ugarte, and Stijn Vansummeren. "The dynamic yannakakis algorithm: Compact and efficient query processing under updates." Proceedings of the 2017 ACM International Conference on Management of Data. 2017.</p>

<p>[5] Pichler, Reinhard, and Sebastian Skritek. "Tractable counting of the answers to conjunctive queries." Journal of Computer and System Sciences 79.6 (2013): 984-1001.</p>

<p>[6] Olteanu, Dan, and Jakub Závodný. "Size bounds for factorised representations of query results." ACM Transactions on Database Systems (TODS) 40.1 (2015): 1-44.</p>

CC BY-SA 4.0
2020-03-07T09:13:07.280Z
2020-03-07T09:13:07.280Z
holf
<p>I am quite new to relational algebra, but I realize that there are efficiency proofs for processing Acyclic joins. I have not been able to understand these results, but this particular problem is quite interesting to me. Given the following table, say <span class="math-container">$R_i$</span>, <span class="math-container">$i \in \{1..n\}$</span></p>

<p><span class="math-container">\begin{array}{|c|c|c|}
\hline
A_{i}&amp; A_{i+1} \\ \hline
0 &amp; 0 \\ \hline
0 &amp; 1 \\ \hline
1 &amp; 0 \\ \hline
1 &amp; 1 \\ \hline
\end{array}</span>
Now, I want to evaluate <span class="math-container">$R_{1}\bowtie_{A_2}R_{2}\bowtie_{A_3} ... R_{n-2}\bowtie_{A_{n-1}}R_{n-1}$</span>, which is going to be a table with attributes <span class="math-container">$A_{1} .. A_{n}$</span> and <span class="math-container">$2^{n}$</span> rows(Basically resembling a Truth table). What is going to be the computational complexity of evaluating this join, given that it is an acyclic, K-uniform join ? Also, are there any gaurentees for cyclic joins which are of the form as I mentioned above (i.e same the column names keep changing but the table attribute remain the same for ex. AB,BA,AC)</p>

<cc.complexity-theory><db.databases><relational-structures>
What is the computational complexity of Acyclic Joins?
SagarM
# What is the computational complexity of Acyclic Joins?

(Asked by: username_0 on 2020-03-03)

I am quite new to relational algebra, but I realize that there are efficiency proofs for processing Acyclic joins. I have not been able to understand these results, but this particular problem is quite interesting to me. Given the following table, say $R\_i$, $i \in \{1..n\}$

\begin{array}{|c|c|c|}
\hline
A\_{i}& A\_{i+1} \\ \hline
0 & 0 \\ \hline
0 & 1 \\ \hline
1 & 0 \\ \hline
1 & 1 \\ \hline
\end{array}
Now, I want to evaluate $R\_{1}\bowtie\_{A\_2}R\_{2}\bowtie\_{A\_3} ... R\_{n-2}\bowtie\_{A\_{n-1}}R\_{n-1}$, which is going to be a table with attributes $A\_{1} .. A\_{n}$ and $2^{n}$ rows(Basically resembling a Truth table). What is going to be the computational complexity of evaluating this join, given that it is an acyclic, K-uniform join ? Also, are there any gaurentees for cyclic joins which are of the form as I mentioned above (i.e same the column names keep changing but the table attribute remain the same for ex. AB,BA,AC)

**Tags:** cc.complexity-theory, db.databases, relational-structures


---

## 1 answers

### Answer by username_1 on 2020-03-07. Score: 4 | Accepted answer

It essentially depends on what you mean by "evaluating this join". If you want to compute the whole table, then the $2^n$ blow-up is unavoidable, just because you need to store all these values.

However, given an acyclic query, you can compute the "semi-join" in time linear in the size of the data and linear in the size of the query. The semi-join is the projection of the results on the variables you still need to finish the computation. In your case, you inductively compute a relation $B\_i = \Pi\_{A\_i,A\_{i+1}}(R\_1 \bowtie \dots \bowtie R\_i)$. In the general case, you compute it inductively on the join tree in a bottom-up fashion and you only keep the variables that appears in the bag you are visiting. More details on this approach could be found in [1] or [2, Chapter 6].

Now you can also enumerate all tuples in the result with a polynomial time delay between two solutions. Even though you need an exponential time to enumerate all solutions, you can guarantee to have enumerated $t$ solutions after a time $t \times poly(n)$. You can even sometimes (with extra structure) guarantee a constant delay between two solutions. You can read more in [3] or in [4] for a more generic approach.

There is a lot more you can do on acyclic conjunctive queries in polynomial time such as counting the number of tuples in the result [5] (you need to be quantifier free however, or it becomes #P-complete again). One way of uniformly explains these tractability results is through the lens of factorized databases [6]. The paper is quite dense but the main idea boils down to the following: given an acyclic conjunctive query $Q$ and a database $D$, you can compute in time linear in the size of $D$ and $Q$, a circuit computing $Q(D)$. This circuit only usess Cartesian products gates and disjoint union gates and its input are small relations. Given such a circuit, you can then show that it is tractable to enumerate the tuples of the relation it represents (you can also count and do many other interesting things).

# References

[1] Flum, Jörg, Markus Frick, and Martin Grohe. "Query evaluation via tree-decompositions." Journal of the ACM (JACM) 49.6 (2002): 716-752.

[2] Libkin, Leonid. Elements of finite model theory. Springer Science & Business Media, 2013.

[3] Bagan, Guillaume, Arnaud Durand, and Etienne Grandjean. "On acyclic conjunctive queries and constant delay enumeration." International Workshop on Computer Science Logic. Springer, Berlin, Heidelberg, 2007.

[4] Idris, Muhammad, Martín Ugarte, and Stijn Vansummeren. "The dynamic yannakakis algorithm: Compact and efficient query processing under updates." Proceedings of the 2017 ACM International Conference on Management of Data. 2017.

[5] Pichler, Reinhard, and Sebastian Skritek. "Tractable counting of the answers to conjunctive queries." Journal of Computer and System Sciences 79.6 (2013): 984-1001.

[6] Olteanu, Dan, and Jakub Závodný. "Size bounds for factorised representations of query results." ACM Transactions on Database Systems (TODS) 40.1 (2015): 1-44.


---

