  We explored ways of doing spatial search within a relational database: (1)
hierarchical triangular mesh (a tessellation of the sphere), (2) a zoned
bucketing system, and (3) representing areas as disjunctive-normal form
constraints. Each of these approaches has merits. They all allow efficient
point-in-region queries. A relational representation for regions allows Boolean
operations among them and allows quick tests for point-in-region,
regions-containing-point, and region-overlap. The speed of these algorithms is
much improved by a zone and multi-scale zone-pyramid scheme. The approach has
the virtue that the zone mechanism works well on B-Trees native to all SQL
systems and integrates naturally with current query optimizers - rather than
requiring a new spatial access method and concomitant query optimizer
extensions. Over the last 5 years, we have used these techniques extensively in
our work on SkyServer.sdss.org, and SkyQuery.net.
