be restricted to the cases when the variables(s) the evaluation should be extendable to follow the other variables in the order. This modified condition is called directional relational consistency. Relational consistency and satisfiability A constraint satisfaction problem may be relationally consistent, have no empty domain or unsatisfiable constraint, and yet be unsatisfiable. There are however some cases in which this is not possible. The first case is that of strongly relational -consistent problem when the domains contain at most elements. In this case, a consistent evaluation of variables can be always extended to a single other variable. If is such an evaluation and is the variable, there are only possible values the variable can take. If all such values are inconsistent with the evaluation, there are (non-necessarily unique) constraints that are violated by the evaluation and one of its possible values. As a result, the evaluation cannot be extended to satisfy all these -or-less constraints, violating the condition of strong relational -consistency. The second case is related to a measure of the constraints, rather than the domains. A constraint is -tight if every evaluation to all its variables but one can be extended to satisfy the constraint either by all possible values of the other variable or by at most of its values. Problem having -tight constraints are satisfiable if and only if they are strongly relationally -consistent. The third case is that of binary constraints that can be represented by row-convex matrices. A binary constraint can be represented by a bidimensional matrix , where is 0 or 1 depending on whether the -th value of the domain of and the -th value of the domain of satisfy the constraint. A row of this matrix is convex if the 1's it contains are consecutive (formally, if two elements are 1, all elements in between are 1 as well). A matrix is row convex if all its rows are convex. The condition that makes strong relational path consistency equivalent to satisfiability is that of constraint satisfaction problems for which there exists an order of the variables that makes all constraint to be represented by row convex matrices. This result is based on the fact that a set of convex rows having a common element pairwise also have a globally common element. Considering an evaluation over variables, the allowed values for the -th one are given by selecting some rows from some