The complexity of acyclic conjunctive queries

This paper deals with the evaluation of acyclic Boolean conjunctive queries in relational databases. By well-known results of Yannakakis [1981], this problem is solvable in polynomial time, its precise complexity, however, ha s not been pinpointed so far, We show that the problem of evaluating acycli c Boolean conjunctive queries is complete for LOGCFL, the class of decision problems that are logspace-reducible to a context-free language. Since LOG CFL is contained in AC(1) and NC2. the evaluation problem of acyclic Boolea n conjunctive queries is highly parallelizable, We present a parallel datab ase algorithm solving this problem with a logarithmic number of parallel jo in operations. The algorithm is generalized to computing the output of rele vant classes of non-Boolean queries. We also show that the acyclic versions of the following well-known database and Al problems are all LOGCFL-comple te: The Query Output Tuple problem for conjunctive queries. Conjunctive Que ry Containment, Clause Subsumption, and Constraint Satisfaction. The LOGCFL -completeness result is extended to the class of queries of bounded treewid th and to other relevant query classes which are more general than the acyc lic queries.