On the orthographic dimension of definable sets

A formula psi (x(1),....x(n)) conforms to a partition P of {x(1)...., x(n)) if it is equivalent to a Boolean combination of formulae that do not have free variables from more than one block of P. We show that if psi conforms to two partitions P-1 and P-2, it also conforms to their greatest lower bou nd in the partition lattice. As a corollary, we obtain that the concept of orthographic dimension of a constraint-definable set, introduced in the fie ld of constraint databases, is well-defined. (C) 2001 Elsevier Science B.V. All rights reserved.