On the Orthographic Dimension of Definable Sets
31 July 2001
A formula phi (chi sub 1,...,chi sub n) conforms to a partition P of {chi sub 1,...,chi sub 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 phi conforms to two partitions P sub 1 and P sub 2, it also conforms to their greatest lower bound in the partition lattice. As a corollary, we obtain that the concept of orthographic dimension of a constraint-definable set, introduced in the field of constraint databases, is well-defined.