Constraint-Based Query Optimization for Spatial Databases

Richard Helm, Kim Marriott, Martin Odersky

10th ACM Symposium on Principles of Database Systems, May 1991

We present a method for converting a system of multivariate Boolean
constraints into a sequence of univariate range queries of the 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.