In the following, we assume a spatial database D to be a finite set of objects characterized by spatial and non-spatial attributes. The spatial attributes may represent, e.g., points or spatially extended objects such as polygons in some d-dimensional space S. The non-spatial attributes of an object in D may represent additional properties of a spatial object, e.g., the unemployment rate for a community represented by a polygon in a geographic information system.