(PDF) Rina Dechter and Peter van Beek. Local and global relational consistency. Theoretical Computer Science, 173:283-308, 1997. A preliminary version of the paper appears in Proceedings of the First International Conference on Principles and Practices of Constraint Programming, Cassis, France, 240-257, September, 1995.
Local consistency has proven to be an important concept in the theory and practice of constraint networks. In this paper, we present a new definition of local consistency, called relational consistency. The new definition is relation-based, in contrast with the previous definition of local consistency, which we characterize as variable-based. It allows the unification 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 definition 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.