Projective operations on relational constraints

ABSTRACT: Given a set of variables and a set of values, by a (relational) constraint we mean any set of functions from the former to the latter. Two special operations on constraints are considered, called existential and universal projections, because of their similarity with existential and universal quantifiers in a predicate calculus. The expressive power of both operations is explored, i.e., the general properties of the variety of constraints which may be produced starting from some initial constraint and applying those operations one or more times. A few comments are added concerning the expressive power of a larger system, comprising projective and Boolean operations (i.e., complementation, union and intersection) on constraints.