Local Consistency - Relational Consistency

While the previous definitions of consistency are all about consistency of assignments, relational consistency involves satisfaction of a given constraint or set of constraints only. More precisely, relational consistency implies that every consistent partial assignment can be extended in such a way that a given constraint or set of constraints is satisfied. Formally, a constraint on variables is relational arc-consistent with one of its variables if every consistent assignment to can be extended to in such a way is satisfied. The difference between "regular" consistency and relational arc consistency is that the latter only requires the extended assignment to satisfy a given constraint, while the former requires it to satisfy all relevant constraints.

This definition can be extended to more than one constraint and more than one variable. In particular, relational path consistency is similar to relational arc-consistency, but two constraints are used in place of one. Two constraints are relational path consistent with a variable if every consistent assignemt to all their variable but the considered one can be extended in such a way the two constraints are satified.

For more than two constraints, relational -consistency is defined. Relational -consistency involves a set of constraints and a variable that is in the scope of all these constraints. In particular, these constraints are relational -consistent with the variable if every consistent assignment to all other variables that are in their scopes can be extended to the variable in such a way these constraints are satisfied. A problem is -relational consistent if every set of constraints is relational -consistent with every variable that is in all their scopes. Strong relational consistency is defined as above: it is the property of being relational -consistent for every .

Relational consistency can also be defined for more variables, instead of one. A set of constraints is relational -consistent if every consistent assignment to a subset of of their variables can be extended to an evaluation to all variables that satisfies all constraints. This definition does not exactly extends the above because the variables to which the evaluations are supposed to be extendible are not necessarily in all scopes of the involved constraints.

If an order of the variables is given, relational consistency can 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.