Conjunctive-query containment constraint satisfaction

Conjunctive-query containment is recognized as a fundamental problem in dat abase query evaluation and optimization. At the same time, constraint satis faction is recognized as a fundamental problem in artificial intelligence. What do conjunctive-query containment and constraint satisfaction have in c ommon? Our main conceptual contribution in this paper is to point out that, despite their very different formulation, conjunctive-query containment an d constraint satisfaction are essentially the same problem. The reason is t hat they can be recast as the following fundamental algebraic problem: give n two finite relational structures A and B, is there a homomorphism h: A -- > B? As formulated above, the homomorphism problem is uniform in the sense that both relational structures A and B are part of the input. By fixing th e structure B, one obtains the following nonuniform problem: given a finite relational structure A, is there a homomorphism h: A --> B? In general, no nuniform tractability results do not uniformize. Thus, it is natural to ask : which tractable cases of nonuniform tractability results for constraint s atisfaction and conjunctive-query containment do uniformize?. Our main tech nical contribution in this paper is to show that several cases of tractable nonuniform constraint-satisfaction problems do indeed uniformize. We exhib it three nonuniform tractability results that uniformize and, thus, give ri se to polynomial-time solvable cases of constraint satisfaction and conjunc tive-query containment. We begin by examining the tractable cases of Boolea n constraint-satisfaction problems and show that they do uniformize. This c an be applied to conjunctive-query containment via Booleanization; in parti cular, it yields one of the known tractable cases of conjunctive-query cont ainment. After this, we show that tractability results for constraint-satis faction problems that can be expressed using Datalog programs with bounded number of distinct variables also uniformize. Finally, we provide a new pro of for the fact that tractability results for queries with bounded treewidt h uniformize as well, via a connection with first-order logic with a bounde d number of distinct variables. (C) 2000 Academic Press.