# What is the computational complexity of Acyclic Joins?

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)

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.