Implementing an OMEGA Query Processor

This paper describes the implementation of a spatial query processor designed for handling GIS type applications. We first propose an extension of an existing index structure called the two-step index structure. Then, we apply the two-step index structure to the task of implementing a spatial query processor called the OMEGA query processor. The OMEGA query processor includes a query optimizer and a query executor. The query executor consists of a spatial query executor, a non-spatial query executor, and computational geometric algorithms. The query executor uses SHORE as its underlying storage manager. The current version of the OMEGA query processor implements a sub-system that efficiently supports a well-chosen set of spatial operators. This system serves as a basis for implementing other more sophisticated operations required in special applications.