Constraint-based query optimization for spatial databases

We present a method for converting a system of multivariate Boolean constraints into a sequence of nnivariafe range queries of he type supported by current spatial databases. The method relies on the transformation of a Boolean constraint system into triangular form. We extend previous results in this area by considering negative as well as positive constraints. We also present a method to approximate triangular Boolean constraints by bounding box constraints.