Local and global relational consistency

Abstract. Local consistency has proven to be an important concept in the theory and practice of constraint networks. In this paper, we present a new de nition of local consistency, called relational consistency. The new de nition is relation-based, in contrast with the previous de nition of local consistency, which wecharacterize as variable-based. It allows the uni cation of known elimination operators such as resolution in theorem proving, joins in relational databases and variable elimination for solving linear inequalities. We show the usefulness and conceptual power of the new de nition in characterizing relationships between four properties of constraints | domain tightness, row-convexity, constraint tightness, and constraint looseness|and the level of local consistency needed to ensure global consistency. As well, algorithms for enforcing relational consistency are introduced and analyzed.