Conjunctivepuery containment is reorganized as a fundamental problem in database query evaluation and optimization. At the same time, constraint satisfaction is recognized as a fundamental problem in artificial intelligence. What do conjunctive-query containment and constraint satisfaction have in common? Our main conceptual contribution in this paper is to point out that, despite their very different formulation conjunctive-query containment and constraint satisfaction arc essentially the same problem. The reason is that they can be recast as the following fundamental algebraic problem: given 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 lixing the structure B, one obtains the following nonuniform problem : given a finite rela- tional structurc A. is there a homomorphism h: A → B? In general, non- uniform tractability results do not uniformize. Thus. it is natural to ask: which tractable cases of nonuniform tractability results for constraint satisfaction and conjunctive-query containment do uniformize? Our main technical contribution in this paper is to show that several cases of tractable non- uniform constraint-satisfaction problems do indaced uniformize. We exhibit three nonuniform tractability results that uniformize and. thus. give rise to polynomial-time so1vable cases of constraint satisfaction and conjunctive- query containment. We begin by examining the tractab1e cases of Boolean
展开▼
