HSJ-Solver: a new method based on GHD for answering conjunctive queries and solving constraint satisfaction problems.

Evaluating conjunctive queries (CQs) is NP-hard in general; however, acyclic CQs or nearest acyclic CQs can be evaluated in polynomial time. Many structural methods for characterising such classes are proposed in the literature. However, exploiting these methods to answer CQs is not efficient in practice when the relations have a realistic size. In this work, we propose a new method called HSJ-Solver for evaluating CQs and for solving constraint satisfaction problems (CSPs) represented by a generalised hypertree decomposition (GHD). Experiments carried out on CSP benchmarks show that using HSJ-Solver significantly improves the achieved performance. [ABSTRACT FROM AUTHOR]