Preliminaries in Functional constraints

The binary constraint satisfaction problem  is such a tuple (N,D,C)  that N is a finite set of variables, D is a set of domains and C is a set of binary constraints where the relations between the any two variables in N are binary.

We define solution space of CSP as the set of all its solutions. The relationship equivalent of 2 CSPs iff they have the same solution space.

2 operations on constraints are defined as intersection and composition.

Constraint c_ij is functional on j if for any a in a certain Domain D_i there is at most one b in another Domain D_j such that a and b satisfy the constraint