LOCAL AND GLOBAL RELATIONAL CONSISTENCY

Local consistency has proven to be an important concept in the theory and practice of constraint networks. In this paper, we present a new d efinition of local consistency, called relational consistency. The new definition is relation-based, in contrast with the previous definitio n of local consistency, which we characterize as variable-based. We sh ow the conceptual power of the new definition by showing how it unifie s known elimination operators such as resolution in theorem proving, j oins in relational databases, and variable elimination for solving lin ear inequalities. Algorithms for enforcing various levels of relationa l consistency are introduced and analyzed. We also show the usefulness of the new definition in characterizing relationships between propert ies of constraint networks and the level of local consistency needed t o ensure global consistency.