Variable Independence, Quantier Elimination, and Constraint Representations

Abstract. Whenever we have data represented by constraints (such as order, linear, polynomial, etc.), running time for many constraint pro-cessing algorithms can be considerably lowered if it is known that certain variables in those constraints are independent of each other. For example, when one deals with spatial and temporal databases given by constraints, the projection operation, which corresponds to quantier elimination, is usually the costliest. Since the behavior of many quantier elimination algorithms becomes worse as the dimension increases, eliminating certain variables from consideration helps speed up those algorithms. While these observations have been made in the literature, it re-mained unknown when the problem of testing if certain variables are independent is decidable, and how to construct eciently a new rep-resentation of a constraint-set in which those variables do not appear together in the same atomic constraints. Here we answer this question. We rst consider a general condition that gives us decidability of vari-able independence; this condition is stated in terms of model-theoretic properties of the structures corresponding to constraint classes. We then show that this condition covers the domains most relevant to spatial and temporal applications. For some of these domains, including linear and polynomial constraints over the reals, we provide a uniform decision procedure which gives us tractability, and present a polynomial-time al-gorithm for producing nice constraint representations.