Uniform Constraint Satisfaction Problems and Database Theory

摘要

It is well-known that there is a close similarity between constraint satisfaction and conjunctive query evaluation. This paper explains this relationship and describes structural query decomposition methods that can equally be used to decompose CSP instances. In particular, we explain how "islands of tractability" can be achieved by decomposing the query on a database, or, equivalently, the scopes of a constraint satisfaction problem. We focus on advanced decomposition methods such as hypertree decompositions, which are hypergraph-based and subsume earlier graph-based decomposition methods. We also discuss generalizations thereof, such as weighted hypertree decompositions, and subedge-based decompositions. Finally, we report on an interesting new type of structural tractability results that, rather than explicitly computing problem decompositions, use algorithms that are guaranteed to find a correct solution in polynomial time if a decomposition exists.