Constraint Satisfaction, Databases, and Logic

1 Introduction

Constraint satisfaction problems constitute a broad class of algorithmic problems that are ubiquitous in several differ­ ent areas of artificial intelligence and computer science. In their full generality, constraint satisfaction problems are NP-complete and, thus, presumed to be algorithmically in­ tractable. To cope with the intractability of these prob­ lems, researchers have devoted considerable research efforts to both the design of heuristic algorithms for constraint sat­ isfaction and the pursuit of "islands of tractability", that is, special cases of constraint satisfaction problems for which polynomial-time algorithms exist.

During the past decade, the pursuit of "islands of tractabil­ ity" of constraint satisfaction has been intensified and has led to a number of discoveries that have also unveiled tight connections between constraint satisfaction, database theory, logic, and universal algebra. Our goal in this paper is to present an overview of the current state of affairs in the study of the computational complexity of constraint satisfaction with emphasis on the connections of this area of research with database theory and logic. The paper is organized as follows: Section 2 contains the precise definition of the CON­ STRAINT SATISFACTION PROBLEM and its reformulation as the HOMOMORPHISM PROBLEM; Section 3 contains some of the connections between constraint satisfaction problems and database theory; the remaining Sections 4, 5, and 6 contain a high-level account of some of the main results about the computational complexity of constraint satisfaction and the pursuit of tractable cases of this problem.

2 The Constraint Satisfaction Problem and the Homomorphism Problem

Constraint satisfaction problems were originally introduced by Montanari [Mon74] to model problems in computer vi­ sion. Since that time, however, it has been realized that nu­ merous important problems in artificial intelligence and com­ puter science can be modeled as constraint satisfaction prob­ lems (see [Dec92a; PJ97]). An instance of the CONSTRAINT SATISFACTION PROBLEM (CSP) consists of a set of vari­ ables, a set of possible values for the variables, and a set of constraints on tuples of variables that restrict the combi­ nations of values that the variables may take; the question

*Partially supported by NSF Grant No. IIS-9907419

Constraint Satisfaction, Databases, and Logic

Phokion G. Kolaitis*

Computer Science Department University of California, Santa Cruz Santa Cruz, CA 95064, U.S.A kolaitis@cs.ucsc.edu

is to determine whether there is an assignment of values to the variables so that the constraints are satisfied. More pre­ cisely, a CSP-instance is a triple (V, D, C), where V of a finite set of variables, D is a finite domain of values for the variables, and Cis a set constraints (t, R), where tis a tuple t = (xi, . .. , Xm) of variables for some m and R is a rela­ tion on D of arity m. A solution is a mapping h : V -t D such that, for every constraint (t, R) E C, we have that h(t) = (h(xi), ... , h(xm)) E R.

Consider the Boolean satisfiability problem 3-SAT: given a 3CNF-formula tp with variables XI, ... , Xn and clauses ci, ... , Ck. is tp satisfiable? Such an instance of 3-SAT can be thought of as the CSP-instance in which the set of vari­ ables is V = {xi, ... , Xn}, the domain is D = {0, 1}, and the constraints are determined by the clauses of tp. For ex­ ample, a clause of the form (x V ·y V z) gives rise to the constraint ( (x, y, z ), {0, 1 )3 - { (0, 1, 0)}). In an analogous manner, 3-COLORABILITY can be modeled as a constraint satisfaction problem. Indeed, an instance H = (V, E) of 3-COLORABILITY can be thought of as the CSP-instance in which the set of variables is the set V of the nodes of the graph H, the domain is the set D = { r, b, g} of three colors, and the constraints are the pairs ( ( u, v), Q), where ( u, v) E E and Q = {(r , b)(b, r), (r,g)(g, r), (b,g)(g, b)} is the inequal­ ity relation on D.

A vocabulary is a finite set of relational symbols RI, . .. , Rm each of which has a fixed arity. A rela­ tional structure over some vocabulary is a tuple A = (A, Rt , ... , R~) such that A is a non-empty set, called the universe of A, and each Rf is a relation on A having the same arity as the symbol Ri. Let A and B be two rela­ tional structures over the same vocabulary. A homomorphism h from A to B is a mapping h : A -t B from the uni­ verse A of A to the universe B of B such that, for every relation RA of A and every tuple (a1 , ... , an) E RA, we have that (h(ai ), . . . , h(an)) E R 8 . Feder and Vardi [FV98] were the first to point out that the CONSTRAINT SATISFAC­ TION PROBLEM can be identified with the HOMOMORPHISM PROBLEM: given two relational structures A and B, is there a homomorphism h from A to B? The intuition behind this identification is that the structure A represents the variables and the tuples of variables that occur in the constraints, while the structure B represents the domain of values and the tu­ ples of values that these constrained tuples of variables are allowed to take. Moreover, the homomorphisms from A to B are precisely the assignments of values to variables that satisfy the constraints. For instance, 3-COLORABILITY is equivalent to the problem of deciding whether there is a ho­ momorphism h from a given graph H to the complete graph K3 = ( {r , b,g}, {(r, b)(b, r), (r,g)(g, r), (b,g)(g, b)} with 3 nodes. More generally, k-COLORABILITY, k 2: 2, amounts to the existence of a homomorphism from a given graph H to the complete graph Kk with k nodes (also known as the k-clique). Numerous other important NP-complete prob­ lems can be viewed as special cases of the HOMOMORPHISM PROBLEM (and, hence, also of the CONSTRAINT SATISFAC­ TION PROBLEM). For example, consider the CLIQUE prob­ lem: given a graph H and an integer k, does H contain a clique of size k? A moment's reflection shows that this is equivalent to the question: given a complete graph Kk and a graph H, is there a homomorphism from Kk to H?

The conceptual insights gained from the identification of the CONSTRAINT SATISFACTION PROBLEM with the Ho­ MOMORPHISM PROBLEM have facilitated the use of tech­ niques from universal algebra in the study of constraint satisfaction [Jea98; FV98]). Moreover, they have clari­ fied the tight connections between constraint satisfaction and database theory. We discuss some of these connections in the next section.

3 Constraint Satisfaction and Relational Databases

The most frequently asked queries in relational database sys­ tems involve the computation of the join of two or more re­ lations in a database. Instead of spelling out the formal def­ inition of the join operation, Jet us consider for concreteness a database relation R(A, B , C) with A, B, C as attributes and a database relation S(B, C, D, E) with B, C, D, E as attributes. Then the join R M S consists of all quintuples (a, b, c, d, e) such that (a , b, c) E Rand (b, c, d, e) E S. Sev­ eral different researchers, including [Bib88], have pointed out that computing the set of all solutions of a CSP-instance can be viewed as a join evaluation problem. Indeed, if (V, D , C) is a CSP-instance, then, for every constraint (V;,, .. . , v;~), R) inC, let R; (Vi,, . .. , Vi~) be the relation R itself viewed as a database relation with attributes v;,, ... , v;~. If R1 , ... , Rt is the collection of all database relations obtained this way, then the join R1 M · · · M Rt consists of all solutions to the CSP-instance (V, D, C).

Join evaluation is a special case of conjunctive query evaluation. Specifically, an n-ary conjunctive query Q over a relational vocabulary is a query definable by a positive existential first-order formula of the form (:Jzl)···(:lz5 )1/l(xl, ··· ,xn,Zl,··· ,z5 ), where 1f! (x1, ... ,xn,z1, ... ,z 5 ) isaconjunctionofatomicformu­ las. For example, the binary conjunctive query "there is a path of length 3 from x1 to x2" is definable by the formula (:lz1)(:Jz2)(E(x1, zl) 1\ E(z1, z2) 1\ E(z2, x2)). Note that joins are precisely those conjunctive queries in which none of the variables in 1/J is quantified. At other extreme, a Boolean conjunctive query is a conjunctive query in which all variables of 1/J have been quantified out.

Every finite relational structure A gives rise to a canonical Boolean conjunctive query QA; the positive existential fi rst­ order sentence defining QA asserts that there exist as many elements as the cardinality of the universe of A and states all atomic facts satisfied by tuples from the universe of A . For example, if A= (A, E) is the 3-cycle with A= {1 , 2, 3} and E = {(1, 2), (2, 3) , (3, 1)}, then the canonical conjunctive query QA is definable by the sentence

The following basic result, due to Chandra and Merlin [CM77], establishes a strong connection between homomor­ phisms and conjunctive queries.

Theorem 3.1: [CM77] The following are equivalent for finite relational structures A and B.

1. There is a homomorphism hfrom A to B .
2. QB t;;; QA, that is, QB logically implies QA.
3. B f= QA, that is, the structure B satisfies the canonical query QA of A.

As an example, we saw earlier that a graph G = (V, E) is 3colorable if and only if there is a homomorphism from G to K3 . Consequently, Theorem 3.1 implies that G is 3-colorable if and only if K3 satisfies the canonical query QG of G .

In view of the identification of the CONSTRAINT SATIS­ FACTION PROBLEM with the HOMOMORPHISM PROBLEM, the preceding Theorem 3.1 implies that the CONSTRAINT SATISFACTION PROBLEM can also be identified with two fundamental problems in database theory: conjunctive query evaluation and conjunctive query implication (or contain­ ment). This fundamental connection between constraint sat­ isfaction and database theory was brought to front stage and further investigated in [KVOOa].

4 Computational Complexity of Constraint Satisfaction

The CONSTRAINT SATISFACTION PROBLEM is NP­ complete, because it is clearly in NP and also contains NP-hard problems as special cases, including 3-SAT, 3COLORABILITY, and CLIQUE. As explained in Garey and Johnson's classic monograph [GJ79], one of the main ways to cope with NP-completeness is to identify polynomial­ time solvable cases of the problem at hand that are ob­ tained by imposing restrictions on the possible inputs. For instance, HORN 3-SAT, the restriction of 3-SAT to Horn 3CNF-formulas, is solvable in polynomial-time using a unit-propagation algorithm. Sintilarly, it is known that 3COLORABILITY restricted to graphs of bounded treewidth is solvable in polynomial time (see [DF99]). In the case of con­ straint satisfaction, the pursuit of tractable cases has evolved over the years from the discovery of isolated cases to the dis­ covery of large "islands of tractability" of constraint satisfac­ tion. In what follows, we will give an account of some of the progress made in this area. We begin by introducing some terminology and notation that will enable us to formalize the concept of an "island of tractability" of constraint satisfaction using the fact that the CONSTRAINT SATISFACTION PROB­ LEM can be identified with the HOMOMORPHISM PROBLEM.

In general, an instance of the HOMOMORPHISM PROBLEM consists of two arbitrary relational structures A and B. Thus, all restricted cases of this problem can be obtained by impos­ ing restrictions on the input structures A and B.

Definition 4.1: Let A, B be two classes of relational struc­ tures. We write CSP(A, B) to denote the restriction of the HOMOMORPHISM PROBLEM to input structures from A and B. In other words,

An island of tractability of constraint satisfaction is a pair (A, B) of classes of relational structures such that CSP(A, B) is in the complexity class P of all decision problems solvable in polynomial time.

The ultimate goal in the pursuit of islands of tractability of constraint satisfaction is to identify or somehow charac­ terize all classes A and B of relational structures such that CSP(A, B) is in P. The basic starting point in this investiga­ tion is to consider the cases in which one of the two classes A, B is as small as possible, while the other is as large as possible. This amounts to considering the cases in which one of A, B is the class All of all relational structures over some arbitrary, but fixed, relational vocabulary, while the other is a singleton {B} consisting of some fixed structure B over that vocabulary. Thus, the starting points of the investigation is to determine, for every relational structure B, the computa­ tional complexity of the decision problems CSP( {B} , All) and CSP(All, {B}).

Clearly, for each fixed B, the decision problem CSP( {B}, All) can be solved in polynomial time, because, given a structure A, the existence of a homomorphism from A to B can be checked by testing all functions h from the universe B of B to the universe A of A (the total number of such functions is IAIIBI, which is a polynomial number in the size of the structure A). At the other extreme, however, the situation is quite different, since the computational complex­ ity of CSP(All, {B}) may very well depend on the partic­ ular structure B . Indeed, CSP(All , {K3}) is NP-complete, because it is the 3-COLORABILITY problem; in contrast, CSP(All, {K2}) is in P, because it is the 2-COLORABILITY problem.

For simplicity, in what follows, for every fixed structure B, we put

and call this the non-uniform constraint satisfaction problem associated with B . Thus, the first major goal in the study of the computational complexity of constraint satisfaction is to identify those structures B for which CSP(B) is in P. Al­ though this goal has yet to be realized, much progress has been made towards it. The next section contains a bird's-eye view of some of the main results obtained to date.

5 The Computational Complexity of Non-Uniform Constraint Satisfaction

The first major result in the study of non-uniform constraint satisfaction problems was obtained by Schaefer [Sch78], who, in effect, classified the computational complexity of all Boolean non-uniform constraint satisfaction problems. A Boolean structure is simply a relational structure with a 2-element universe, that is, a structure of the form B = ( { 0, 1} , RP , ... , R~,). A Boolean non-uniform constraint satisfaction problem is a problem of the form CSP(B) with B a Boolean structure. These problems are also known as GENERALIZED SATISFIABILITY PROBLEMS, because they can be viewed as variants of Boolean satisfiability problems in which the formulas are conjunctions of generalized con­ nectives [0179]. In particular, they contain the well known problems k-SAT, k 2: 2, 1-IN-3-SAT, POSITIVE 1-IN-3SAT, NOT-ALL-EQUAL 3-SAT, and MONOTONE 3-SAT as special cases. For example, 3-SAT is CSP(B), where B = ({0, l},Ro,R1 ,R2 ,R3 ) and Ri is the set of truth assign­ ments that satisfy a 3-clause in which the first i-literals are negated, i = 0, 1,2, 3 (thus, Ro = {O,lP- {(0, 0,0)}) . Similarly, MONOTONE 3-SAT is CSP(B), where B = ( { 0, 1} , Ro, R3) .

Ladner [Lad75] showed that if P =f. NP, then there are decision problems in NP that are neither NP-complete, nor they belong to P. Consequently, it is conceivable that a given family of NP-problems contains problems of such interme­ diate complexity. Schaefer [Sch78], however, showed that the family of all Boolean non-uniform constraint satisfaction problems contains no problems of intermediate complexity.

Theorem 5.1: (Schaefer's Dichotomy Theorem [Sch78])

• !JB = ( { 0, 1}, RP, .. . , R~) is Boolean structure, then either CSP(B) is in P or CSP(B) is NP-complete. In a picture,
• Moreover, there is a polynomial-time algorithm to de­ cide, given a Boolean structure B, whether CSP(B) is in P or it is NP-complete.

Schaefer [Sch78] actually showed that there are exactly six types of Boolean structures such that CSP(B) is in P, and provided explicit descriptions of them. Specifically, he showed that CSP(B) is in P precisly when at least one of the following six conditions is satisfied:

• Every relation R~, 1 ::; i ::; m, of B is 0-valid, that is, R~ contains the all-zeroes tuple (0, .. . , 0).
• Every relation R~, 1 ::; i ::; m, of B is 1-valid, that is, R~ contains the all-ones tuple (1, . . . , 1) .
• Every relation R~, 1 ::; i ::; m, of B is bijunctive, that is, R~ is the set of truth assignments satisfying some 2CNF formula.

• Every relation R~, 1 :::; i :::; m, of B is Horn, that is, R~ is the set of truth assignments satisfying some Horn formula.
• Every relation R~, 1 :::; i :::; m, of B is dual Horn, that is, R~ is the set of truth assignments satisfying some dual Horn formula.
• Every relation R~, 1 :::; i :::; m, of B is affine, that is, R~ is the set of solutions to a system of linear equations over the two-element field.

Schaefer's Dichotomy Theorem yields a complete classifi­ cation of the complexity of CSP(B) for Boolean structures B. At the same time, it raises the challenge of classifying the computational complexity of CSP(B) for arbitrary rela­ tional structures B. To this effect, Feder and Vardi [FV98] formulated the following important conjecture.

Conjecture 5.2: (Feder-Vardi Dichotomy Conjecture) If B = (B, Rr, ... , R!) is an arbitrary relational structure, then either CSP(B) is in P or CSP(B) is NP-complete. In a picture,

The Feder-Vardi Dichotomy Conjecture inspired intensive research efforts that resulted into significant advances to­ wards resolving it. In particular, quite recently Bulatov con­ firmed two important cases of this conjecture that are de­ scribed next.

Theorem 5.3: Let B = (B, RP, ... , R~) be a relational structure.

• (Bulatov [Bul02a]) If B = {0, 1, 2}, then either CSP(B) is in P or CSP(B) is NP-complete.
• (Bulatov [Bul03]) If every non-empty subset of B is one of the relations R~ ofB, then either CSP(B) is in P or CSP(B) is NP-complete.

Moreover, in both cases there is a polynomial-time algorithm to decide whether CSP(B) is in P or it is NP-complete.

The second of the two cases above is known as conserva­ tive constraint satisfaction. In effect, it is the case in which all possible unary constraints on the domain are present.

In spite of the progress made, the Feder-Vardi Dichotomy Conjecture remains unresolved for CSP(B) with IBI 2: 4. The research efforts towards this conjecture, however, have also resulted into the discovery of broad sufficient condi­ tions for tractability of non-uniform constraint satisfaction that have provided unifying explanations for numerous seem­ ingly disparate tractability results and have also led to the dis­ covery of new islands of tractability of CSP (B). These broad sufficient conditions for tractability of CSP(B) are based on concepts and techniques from two different areas: universal algebra and logic. The approach via universal algebra yields sufficient conditions for tractabilty of CSP(B) in terms of closure properties of the relations in B under certain func­ tions on B. The approach via logic yields sufficient condi­ tions for tractability in terms of expressibility of CSP(B) in Datalog. In the remainder of this section, our primary focus is on the latter approach.

Datalog is the main database query language used in de­ ductive database systems (see [Ull89]). In a nutsfell, a Dat­ alog program is a negation-free and function-free logic pro­ gram. More precisely, a Datalog program is a finite set of rules of the form

where T, 51 , ... , Sr are relation symbols. In effect, the right­ hand side of each rule (called the body of the rule) is a con­ junctive query in which all variables not occurring in the left­ hand side (called the head of the rule) are existentially quan­ tified. Datalog embodies recursion because relation symbols may occur both in the heads and the bodies of rules. Those that do are the recursive or or intensional database predicates (IDBs) of the program, while the remaining relation symbols are the extensional database predicates (EDBs). One of the IDB predicates is singled out as the goal of the program.

As a standard example, the transitive closure of the edge relation E of a graph H = (V, E) is defined by the following Datalog program.

Every Datalog program can be evaluated "bottom-up" in a polynomial number of iterations on a given database. For ex­ ample, the k-th iteration of the above Datalog program yields the set of all pairs of nodes of H that are connected via a path of length at most k; moreover, at most n iterations suffice to compute the transitive closure of E, where n is the number of nodes in V. It follows that each fixed Datalog program can be evaluated in time polynomial in the size of a given relational structure. Consequently, if a query Q is definable by a Data­ log program, then Q is in P. Thus, expressibility in Datalog is a sufficient condition for tractability.

Another important feature of Datalog is that queries de­ finable by Datalog programs are preserved under homomor­ phisms. This means that if a structure A satisfies the goal of a Datalog program and there is a homomorphism from A to B, then also B satisfies the goal of the program.

Let B = ( B, RP, ... , R~) be a relational structure. It is easy to see that, except for trivial situations, CSP (B) is not preserved under homomorphisms, which implies that CSP(B) is not expressible in Datalog. Thus, at first sight, it appears that there is no link between expressibility in Dat­ alog and tractability of non-uniform constraint satisfaction. A moment's reflection, however, reveals that the complement CSP(B) of CSP(B) is preserved under homomorphisms, where

CSP(B) = {A: no homomorphism h: A--+ B exists}.

Consequently, it is conceivable that, for some structures B, the non-uniform constraint satisfaction problem CSP(B) is in P because its complement CSP(B) is expressible in Dat­ alog. Feder and Vardi [FV98] pursued this link in depth and demonstrated that expressibility of CSP(B) in Datalog is a unifying explanation for numerous tractability results about CSP(B ).

As an important concrete example, consider 2COLORABILITY, which is the same problem as CSP(K2 ) . The following Datalog program with Q as its goal expresses NoN 2-COLORABILITY, since a graph is 2-colorable if and only if it contains no cycles of odd length.

As two additional important examples, recall that if B = ( { 0, 1}, R~, ... , R~.) is a Boolean structure such that ev­ ery relation R~ is Hom or every relation R~ is bijunctive, then CSP(B) is in P. It can be shown that in both these cases CSP(B ) is expressible in Datalog.

To gauge the broad spectrum of tractable cases covered by Datalog, it is perhaps worth comparing tractability via Dat­ alog to tractability via closure properties, which, as men­ tioned earlier, is an approach to tractability based on uni­ versal algebra. For this, we need to first introduce some basic concepts from universal algebra. If R is an n-ary relation on a set B and f : Bk --+ B is a function, then we say that R is closed under f if for every k-tuples (au, ... , aln) , ... , (akl, ... , akn) in R, we have that the n-tuple (!(au, . .. ,aki), ... ,f(aln···· ,akn)) is also in R. If B = (B, R~, . .. , R~,) is a relational structure, then a polymorphism of B is a function f : Bk --+ B for some k ~ 1 such that each relation R~, 1 ~ i ~ m, is closed under f. We write Pol(B) for the set of all polymorphisms of B . As it turns out, the complexity of CSP(B ) is intimately connected to the kinds of functions that Pol(B) contains. In particular, it has been shown that if Pol(B) contains functions that satisfy certain algebraic iden­ tities, then CSP(B) is in P. This connection has been in­ vestigated in depth and with much success by Jeavons and his collaborators in a sequence of papers, including [JCG97; JCC98], and by Bulatov [Bul02b] (but also Feder and Vardi [FV98] had results along these lines). The following are the presently known most general sufficient conditions for tractability of CSP(B) based on closure properties.

Theorem 5.4: Let B = (B, R~ , ... , R~) be a relational structure.

• If Pol(B) contains a near-unanimity function, then CSP(B) is in P.
• /fPol(B) contains a set function, then CSP(B) is in P.
• lfPo!(B) contains a Malt§ev function, then CSP(B) is in P.

A k-ary function f with k ~ 3 is a near unanimity func­ tion if f( x1, . .. ,xk ) = y, for every k-tuple (x1, ... ,xk) such that at least k - 1 of the xi's are equal toy. Note that the ternary majority function on {0, 1} is a near unanimity function . A k-ary function f with k ~ 2 is a set jimction if for every k-tuple (x1, .. . ,xk), we have that f(x 1, ... , xk) depends only on the set { x 1 , . . . , Xk}. Note that the Boolean binary functions 1\ and V are set functions. Finally, a ternary function f( x, y, z) is a Malt§ev function if, for every x andy, it satisfies the identities f (y , y, x) = f(x, y, y) = x. Note that the Boolean function x EB y EB z is a Maltsev function . It should be pointed out that the preceding Theorem 5.4 con­ tains as special cases the non-trivial tractable cases in Schae­ fer 's Dichotomy Theorem 5.1. Indeed, it is known that a Boolean relation is bijunctive if and only if it is closed under the ternary majority operation; moreover, a Boolean relation is Horn (dual Horn) if and only if it is closed under 1\ (respec­ tively, V); finally, a Boolean relation is affine if and only if it is closed under x EB y EB z.

Concerning the comparison between Datalog and closure properties, it can be shown that if Pol(B) contains a near­ unanimity function or a set function, then CSP(B ) is express­ ible in Datalog. Thus, expressibility in Datalog subsumes two of the three sufficient conditions for tractability based on clo­ sure properties. It also known, however, that there are struc­ tures B (in fact, even Boolean structures) such that Poi(B) contains a Maltsev function, but CSP(B ) is not expressible in Datalog. At the same time, there are structures B such that Poi(B) does not contain any near unanimity functions, set functions, or Maltsev functions, yet CSP(B) is tractable because CSP(B) is expressible in Datalog.

In what follows in this section, we will take a closer look at the connections between Datalog and non-uniform constraint satisfaction. In particular, we will address the following ques­ tion: when is CSP(B) expressible in Datalog? As we will see, expressibility of CSP(B) in Datalog can be character­ ized in terms of pebble games and also in terms of consistency properties.

Combinatorial games are a versatile tool in analyzing the expressive power of logics. The most well known among these games are the Ehrenfeucht-Fra·isse-games for first-order logic (see [EFT94]). A different family of games, known as k-pebble games, has been used to study fixed-point logics and in finitary logics with finitely many variables (see [KV90]. We now describe a variant of k-pebble games that are suitable for analyzing the expressive power of Datalog [KV95].

Definition 5.5: Let k ~ 2 be a positive integer. The exis­ tential k-pebble game (or, in short, the (3, k)-pebble game) is played between two players, the Spoiler and the Duplicator, on two relational structures A and B according to the follow­ ing rules: each player has k pebbles labeled 1, .. . , k; on the i-th move of a round of the game, 1 ~ i ~ k, the Spoiler places a pebble on an element a; of A, and the Duplicator responds by placing the pebble with the same label on an el­ ement b; of B. The Spoiler wins the game at the end of that round, if the correspondence a; t-+ b;, 1 ~ i ~ k , is not a homomorphim between the substructures of A and B with universes { a 1 , ... , ak} and {b1 , ... , bk} , respectively. Oth­ erwise, the Spoiler removes one or more pebbles, and a new round of the game begins. The Duplicator wins the (3, k)­ pebble game if he has a winning strategy, that is to say, a systematic way that allows him to sustain playing "forever", so that the Spoiler can never win a round of the game.

To illustrate this game, let Km be the complete undirected graph with m nodes. For every k 2: 2, the Duplicator wins the (3, k)-pebble game on Kk and Kk+1 , but the Spoiler wins the (3, k + I)-pebble game on Kk+l and Kk. As another example, let Ls be the s-element linear order, s 2: 2. If m < n, then the Duplicator wins the (3, 2)-pebble game on Lm and Ln, but the Spoiler wins the (3, 2)-pebble game on Ln and Lm.

Note that the above description of a winning strategy for the Duplicator in the (3, k )-pebble game is rather informal. The concept of a winning strategy can be made precise, how­ ever, in terms of families of partial homomorphisms with ap­ propriate closure and extension properties, where a partial homomorphism from A to B is a homomorphism from a sub­ structure of A to a substructure of B.

Definition 5.6: Let k be a positive integer. A winning strat­ egy for the Duplicator in the existential k-pebble game on A and B is a nonempty family :F of partial homomorphisms from A to B such that:

1. For every f E :F, the domain dom(f) off has at most k elements.
2. :F is closed under subfunctions, which means that if g E :F and f ~ g, then f E :F.
3. :F has the k-forth property, which means that for every f E :F with ldom(f) I < k and every a E A on which f is undefined, there is a g E :F that extends f and is defined on a.

Intuitively, the second condition provides the Duplicator with a "good" move when the Spoiler removes a pebble from an element A , while the third condition provides the Dupli­ cator with a "good" move when the Spoiler places a pebble on an element of A .

For every positive integer k, let k-Datalog be the collection of all Datalog programs such that each rule has at most k distinct variables. The next result describes the connection between (3 , k)-pebble games and k-Datalog, and also gives some of the algorithmic properties of (3, k )-pebble games.

Theorem 5.7: [KV95; KVOOa] Let k be a positive integer.

• Assume that Q is a query definable by a k-Datalog pro­ gram. If A and Bare two relational structures such that A satisfies Q and the Duplicator wins the (3, k)-pebble game on A and B, then also B satisfies Q.
• There is a polynomial-time algorithm to decide whether, given two finite structures A and B, the Spoiler or the Duplicator wins the (3, k )-pebble game on A and B.
• For every finite relational structure B, there is a k­ Datalog program 1fB that expresses the query: given a finite a-structure A, does the Spoiler win the (3, k )­ pebble game on A and B ?

The preceding Theorem 5.7 can be used to characterize when CSP(B) is expressible in Datalog.

Theorem 5.8: [KVOOa] Let k be a positive integer and B a fi­ nite relational structure. The following statements are equiv­ alent.

• CSP(B) is expressible in k-Datalog
• CSP (B) = {A : Duplicator wins the

(3, k)-pebble game on A and B} .

Note that if a homomorphism from A to B exists, then the Duplicator wins the (3, k )-pebble game on A and Busing the values of the homomorphism as his strategy. Thus, Theorem 5.8 asserts that CSP(B) is expressible in k-Datalog if and only if the following property holds: whenever the Duplicator wins the (3, k)-pebble on A and B, a homomorphism from A to B exists.

A striking consequence of Theorems 5.7 and 5.8 is that all non-uniform constraint satisfaction problems CSP(B ) for which CSP(B) is expressible in k-Datalog can be solved in polynomial time using the same algorithm, namely, the polynomial-time algorithm for determining the winner in the (3, k)-pebble game. Moreover, since expressibility in Data­ log subsumes the tractable cases in which Pol(B) contains a near unanimity function or a set function, it follows that the algorithm for determining the winner in the (3, k)-pebble game can also be used to solve CSP(B) in polynomial time in these two major tractable cases.

Many heuristic algorithms for constraint satisfaction in­ volve "constraint propagation", which can be intuitively de­ scribed as the derivation of new constraints from the original ones. This process has been formalized using various consis­ tency concepts that make explicit additional constraints im­ plied by the original constraints. The strong k-consistency property is the most important one among them; in infor­ mal terms, this property holds when every partial solution on fewer thank variables can be extended to a solution on k vari­ ables [Dec92b]. Closely related to this is the process of estab­ lishing strong k-consistency, which is the question of whether additional constraints can be added to a given instance of the CONSTRAINT SATISFACTION PROBLEM in such a way that the resulting instance is strongly k-consistent and has the same space of solutions as the original one (see [Dec92b; KVOOb] for the formal definitions). It turns out that the fol­ lowing tight connection exists between strong k-consistency properties and (3, k)-pebble games.

Theorem 5.9: [KVOOb] The following are equivalent for a CSP-instance (V, D, C).

• It is possible to establish strong k-consistency for (V,D,C).
• The Duplicator wins the (3, k)-pebble game on A and B, where A, B form the instance of the HOMOMOR­ PHISM PROBLEM associated with (V, D , C).

Furthermore, when this happens, the set Wk (A, B) of all winning configurations for the Duplicator in the (3, k)­ pebble game gives rise to the largest (and, hence, least con­ strained) CSP-instance that establishes strong k-consistency for (V, D, C).

The preceding theorem provides a different perspective on consistency properties and reinforces the usefulness of the

(3, k )-pebble games in the study of constraint satisfaction. In particular, Theorem 5.9 implies that computing winning strategies for the Duplicator in the (3, k )-pebble game is the most general form of constraint propagation. Moreover, as an immediate consequence of Theorems 5.8 and 5.9, we obtain another characterization of when CSP(B) is expressible in k-Datalog.

Corollary 5.10: Let k be a positive integer and B be a fixed finite relational structure. Then the following are equivalent.

• CSP(B) is expressible in k-Datalog
• For every finite relational structure A, establishing strong k-consistency for A and B implies that there is a homomorphism from A to B.

The results presented in this section make a strong case for the importance of the property "CSP(B) in expressible in Datalog" as a broad sufficient condition for tractability of CSP(B), since this property subsumes numerous tractable cases of non-uniform constraint satisfaction. In view of this, one would like to have an efficient algorith to test whether, given a relational structure B, we have that CSP(B) is ex­ pressible in Datalog. Such an algorithm could be used as a building block in heuristic algorithms for constraint satisfac­ tion, where one first tests for expressibility in Datalog be­ fore resorting to some other exhaustive search procedure. At present, however, no such efficient algorithm is known. In fact, it is not even known whether expressibility of CSP(B) in Datalog is a decidable property. More precisely, the fol­ lowing problem, originally posed by Feder and Vardi [FV98], remains open.

Open Problem: Let k 2: 2 be a fixed positive integer. Is there an algorithm to decide whether, given B, we have that CSP(B) is expressible in k-Datalog?

6 Uniform Constraint Satisfaction and Bounded Treewidth

In Section 5, we focused on the pursuit of islands of tractabil­ ity of non-uniform constraint satisfaction, that is, islands of the form

where B is a fixed relational structure. In particular, we saw that substantial progress has been made towards obtaining a complete classification of all relational structures B for which CSP(B) is solvable in polynomial time. The state of affairs, however, is different for constraint satisfaction problems of the form CSP(A, B), where neither A nor B is a singleton class. We call such problems uniform constraint satisfac­ tion problems, because an instance of CSP(A, B) is a pair of structures A E A and B E B (unlike CSP(B), where an instance is just a structure A).

At present, we are far away from even coming close to a characterization of all classes A and B such that CSP(A, B) is solvable in polynomial time. Nonetheless, significant progress has been made in the case in which B is the class All of all relational structures over an arbitrary, but fixed, vocabu­ lary. In what follows, we present the main results concerning islands of tractability of uniform constraint satisfaction of the form CSP(A, All).

As is well known, many algorithmic problems that are "hard" on arbitrary graphs become "easy" on trees. This mo­ tivated researchers to investigate whether the concept of a tree can be appropriately relaxed while maintaining good compu­ tational behavior. As part of their seminar work on graph minors, Robertson and Seymour introduced the concept of treewidth and showed that graphs of bounded treewidth are "tree-like" structures exhibiting such good behavior. The monograph by Downey and Fellows [DF99] contains com­ plete definitions and characterizations of these concepts. Here, instead of giving the standard definition of treewidth in terms of tree compositions, we present an equivalent one in terms of partial k-trees.

Definition 6.1: Let k be a positive integer.

• A graph H is a k-tree if either H is a Kk+1 -clique or there are a k-tree G, nodes a1 , ... , ak in G forming a Kk-clique, and a node b in H - G such that H is obtained from G by connecting b to each of the nodes a1 , ... , ak (thus, forming a Kk+l -clique).
• A graph is a partial k-tree if it is a subgraph (not neces­ sarily induced) of a k-tree.
• The treewidth of a graph H, denoted by tw(H), is the smallest k such that H is a partial k-tree.
• We write T(k) to denote the class of all graphs H such that tw(H) < k.

Clearly, if T is a tree, then tw(T) = 1. Similarly, if n 2: 3 and Cn is the n-element cycle, then tw(C) = 2. At the other end of the scale, tw(Kk) = k - 1, for every k 2: 2. Computing the treewidth of a graph is an intractable problem. Specifically, the following problem is NP-complete: given a graph H and an integer k 2: 1, is tw(H) :S k? Nonetheless, Bodlaender [Bod93] showed that for every fixed integer k 2: 1, there is a linear-time algorithm such that, given a graph H, it determines whether or not tw(H) < k.

The notion of treewidth can be defined for arbitrary finite relational structures A = (A, Rf- , ... , R!) using the Gail man graph GA of the structure A. Specifically, tw(A) = tw(G(A)), where G(A) = (A, E) and

In what follows, T(k) will denote the class of all relational structures of treewidth less than k over a fixed relational vo­ cabulary.

Dechter and Pearl [DP89] and Freuder [Fre90] showed that the classes of structures of bounded treewidth give rise to large islands of tractrability of uniform constraint satisfaction.

Theorem 6.2: [DP89; Fre90] If k 2: 2 is a positive integer, then CSP(T(k), All) is in P.

The polynomial-time algorithm for CSP(T(k), All) in the above theorem is often described as a bucket elimination al­ gorithm [Dec99]. It should be noted that it is not a constraint propagation algorithm. Instead, this algorithm uses the bound on the treewidth to test if a solution to the constraint satisfac­ tion problem exists by solving a join evaluation problem in which all intermediate relations are of bounded arity.

Kolaitis and Vardi [KVOOb], and Dalmau, Kolaitis and Vardi [DKV02] investigated certain logical aspects of the treewidth of a relational structure and showed that this combinatorial concept is closely connected to the canoni­ cal conjunctive query of the structure being definable in a fragment of first-order logic with a fixed number of vari­ ables. This made it possible to show that the tractability of CSP(T(k), All) can be explained in terms of expressibility in k-Datalog. Moreover, it led to the discovery of larger is­ lands of tractability of uniform constraint satisfaction.

Definition 6.3: Let k 2: 2 be a positive integer.

• FOk is the collection of all first-order formulas with at most k distinct variables.
• Lk is the collection of all FOk -formulas built using atomic formulas, conjunction, and existential first-order quantification only.

As an example, it is easy to see that if Cn is then-element cycle, n 2: 3, then the canonical conjunctive query QCn is expressible in L 3 . For instance, Qc· is logically equivalent to

As mentioned earlier, for every n 2: 3, we have that tw(Cn) = 2. The next result shows that this relationship between treewidth and number of variables needed to express the canonical conjunctive query is not an accident.

Theorem 6.4: [KVOOb; DKV02] Let k 2: 2 be a positive integer.

• If A E T(k), then the canonical conjunctive query QA is expressible in Lk.
• If B is an arbitrary, but fixed, structure, then CSP(T(k), {B}) is expressible in k-Datalog.
• CSP(T(k), All) can be solved in polynomial time by de­ termining whether, given a structure A E T(k) and an arbitrary structure B, the Spoiler or the Duplicator wins the (3, k )-pebble on A and B.

As a consequence of the above Theorem 6.4, we see that CSP(T(k), All) can be solved in polynomial time using a constraint propagation algorithm that is quite different from the bucket elimination algorithm in Theorem 6.2.

Definition 6.5: Let A and B be two relational structures.

• We say that A and B are homomorphically equivalent, denoted A "'h B, if there are homomorphisms h : A -t B and h' : B -t A.
• We say that B is the core of A, and write core( A) = B, if
• B is a substructure of A.
• There is no homomorphism h: B -t B' from B to a proper substructure B' of B.

Clearly, core(Kk) = Kk and core(Cn) = Cn . Moreover, if if H is a 2-colorable graph, then core(H) = K 2 . It should be note that cores play an important role in database query processing and optimization (see [CM77]). The next result shows that they can also be used to characterize when the canonical conjunctive query is definable in Lk.

Theorem 6.6: Let k 2: 2 be a positive integer and A a relational structure. Then the following statements are equiv­ alent.

• QA is definable in Lk.
• There is a structure B E T(k) such that A "'h B.
• core(A) E T(k).

Definition 6.7: If k 2: 2 is a positive integer, then 1-f.(T(k)) is the class of all relational structures over some fixed vocab­ ulary that are homomorphically equivalent to a structure in T(k).

Equivalently, 1-f.(T(k)) is the class of all relational struc­ tures A such that core(A) has treewidth less thank.

It should noted that T(k) is properly contained in 1-f.(T(k)). Indeed, it is known that there are 2-colorable graphs of arbitrarily large treewidth. In particular, grids are known to have these properties (see [DF99]). Yet, these graphs are members of 1-f.(T(2) ), since their core is K 2 .

Theorem 6.8: [DKV02] Let k 2: 2 be a positive integer.

• If B is an arbitrary, but fixed, structure, then CSP(H(T(k)), {B}) is expressible in k-Datalog.
• CSP(H(T(k)), All) is in P. Moreover, CSP(H(T(k)), All) can be solved in polynomial time by determining whether, given a structure A E 1-f.(T(k)) and an arbitrary structure B. the Spoiler or the Duplicator wins the (3, k )-pebble on A and B.

The preceding Theorem 6.8 yields new islands of tractabil­ ity for uniform constraint satisfaction that properly subsume the islands of tractability constituted by the classes of struc­ tures of bounded treewidth. However, this expansion of the tractability landscape comes at a certain price. Specifically, as seen earlier, for every fixed k 2: 2, there is a polynomial­ algorithm for determining membership in T(k) [Bod93] . In contrast, it has been shown that, for every fixed k 2: 2, deter­ mining membership in 1-f.(T(k)) is an NP-complete problem [DKV02]. Thus, these new islands of tractability are not as easily accessible as the earlier ones.

Since 1-f.(T(k)) contains structures of arbitrarily large treewidth, the bucket elimination algorithm cannot be used to solve CSP(H(T(k)), All) in polynomial time. Thus, Theo­ rem 6.8 also shows that determining the winner of the (3, k )­ pebble is a polynomial time algorithm that applies to islands of tractability not covered by the bucket elimination algo­ rithm.

It is now natural to ask whether there are classes A of re­ lational structures over some fixed vocabulary such that they are larger than the classes 1-f.(T(k)) and CSP(A, All) is solv­ able in polynomial time. A rather unexpected and remarkable new result by Grohe [Gro03] essentially shows that no such classes exist, provided a certain complexity-theoretic hypoth­ esis is true.

Theorem 6.9: [Gro03] Assume that FPT =J. W[l]. If A is a recursively enumerable class of relational structures over some fixed vocabulary such that CSP(A, All) is in P, then there is a positive integer k such that A s; 1-f.(T(k) ).

The hypothesis FPT =f. W[l] is a statement in parametrized complexity that is analogous to the hypothesis P =f. NP, and it is widely accepted as being true (see [DF99]). In effect, Grohe's Theorem 6.9 is a converse to Theorem 6.8. Together, these two theorems yield a complete characterization of all is­ lands of tractability of the form CSP(A, All). Moreover, they reveal that all tractable cases of the form CSP(A, All) can be solved by the same polynomial-time algorithm, namely, the algorithm for determining the winner in the (3, k)-pebble game. In other words, all tractable cases of constraint sati­ faction of the form CSP(A, All) can be solved in polynomial time using constraint propagation.