Hypertree Decompositions and Tractable Queries

G. Gottlob, N. Leone, F. Scarcello

Several important decision problems on conjunctive queries (CQs) are NP-complete in general but become tractable, and actually highly parallelizable, if restricted to acyclic or ne…