For the study of the computational complexity of evaluating conjunctive queries, two problems have to be distinguished.
Conjunctive queries are NP-complete with respect to combined complexity,[REF] while the data complexity of conjunctive queries is very low, in the parallel complexity class AC0, which is contained in LOGSPACE and thus in polynomial time.