Heuristic Hypertree Decomposition

The problem of computing solutions to constraint satisfaction problems (CSPs) has gained widespread interest during the last few years, when resources became available to carry out significant computations on that topic. In the last few decades increasingly methods from database theory have been used in the area of constraint satisfaction. This is due to the fact that finite domain constraint satisfaction problems can be interpreted as databases. Different methods have been developed for improving the efficiency of the evaluation of questions concerning CSPs. Recently, a new method called hypertree decomposition has been developed by Gottlob and others, that dominates in a precise sense all known methods from the literature. However, computing an optimal decomposition of such a kind is very expensive in terms of space and time requirements. Thus the necessity arises for doing more than simply give an exact algorithm for computing optimal hypertree decompositions. This point is handled in detail in the present work. We develop a heuristics, that can compute good hypertree decompositions on hardware that is available at a low price. The space requirements of the algorithm are very modest compared to the exact algorithm for computing optimal hypertree decompositions. The time requirements can be adjusted and traded against the quality of the solution. The quality of the solution is compared in the environment of a constraint solver developed by DaimlerChrylser, which can import strategies generated from hypertree decompositions and use them for the evaluation of CSPs. Furthermore, correctness results about the heuristics containing a completely new type of inductive construction of hypertree decompositions are given as theoretical results together with a few applications of the concept of hypertree decomposition