What is the computational complexity of Acyclic Joins?

Question

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)

Answer 1

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.