HyperTrac:hypergraph Decompositions and Tractability

Conjunctive Queries (CQs, also known as Select-From-Where queries in the database query language SQL) are the most fundamental form of database queries. Likewise, Constraint Satisfaction Problems (CSPs) are a fundamental task in the Artificial Intelligence domain. Both problems are known to have high complexity. Therefore, the search for classes of CQs and CSPs with lower complexity has been an active research area for many years. An important tool for identifying such classes of CQs and CSPs with lower complexity are so-called hypergraph decompositions. These techniques have been successfully applied to CSP solving and have meanwhile also been integrated into commercial database systems. There are several types of hypergraph decompositions in the literature, namely hypertree decompositions (HDs), their generalization to generalized hypertree decompositions (GHDs) and the yet more general fractional hypertree decompo- sitions (FHDs). However, the computation of an appropriate HD, GHD, or FHD is itself a demanding problem. Algorithms for this task exist, but they typically only work well for small Conjunctive Queries or small Constraint Satisfaction Problems. In this project, we will tackle the problem of computing various forms of hypergraph decompositions (namely HDs, GHDs, and FHDs) both from a theoretical and practical point of view. On the one hand, we aim at the development of new algorithms that outperform existing ones. On the other hand, we want to identify meaningful restrictions of the CQs or CSPs under consideration to allow for yet more efficient decomposition algorithms.

Answering queries posed by the user to a database or finding solutions that satisfy certain constraints specified by the user are fundamental problems in computer science. However, these are non-trivial problems and even modern computers may struggle to solve them in an acceptable time. Consequently, various methods have been proposed in the literature for decomposing a given problem and to use the resulting decompositions to find solutions faster. Intuitively, such decompositions split a complex computation task into smaller, manageable subtasks. However, also the problem of finding a good decomposition may be challenging. In this project, we therefore pursued two main directions: First, we significantly improved upon previous methods for computing decompositions. We applied several methods to achieve this goal: on the one hand, we designed parallel algorithms that can run on a cluster of computers. On the other hand, we analysed problem instances typically occurring in practice and identified structural properties of these problem instances. We have then exploited these properties to design more efficient algorithms. As a byproduct of this work, we created a benchmark of problem instances that can be (and already has been) used for experimental evaluations also by other groups designing algorithms in this area. Second, we worked on fast solution methods - many of them using decompositions - for various problems in the areas of Databases and Artificial Intelligence. In case of the Database area, we have thus proposed novel techniques for query evaluation and optimization of various query languages. In the Artificial Intelligence area, we have targeted various problems from areas as diverse as Computational Social Choice and Reasoning. However, in particular, in the area of query evaluation and optimization, the use of decomposition-based methods has not yet entered industrial-strength programmes. This is at least partly due to the fact that the computation of decompositions has been considered as a difficult and hence time-consuming task. With the progress made in this project with the development of new algorithms (and publicly available software tools implementing these algorithms) for computing decompositions, this should no longer be an obstacle. Hence, the natural next step will be to integrate decomposition-based techniques into state-of-the-art database systems.