Introduction

A spatial database system can be defined as a database system that offers spatial data types in its data model and query language, and supports spatial data types in its implementation, providing at least spatial indexing and spatial join methods [Gut94]. The spatial objects are composed of one or more points, lines and/or polygons. Fig.  shows a map from Google Maps (http://maps.google.com) obtained by entering a query ``Find computer related businesses near University of New South Wales". It shows different representations of spatial objects. i.e., points, lines, regions. A point may represent a data object for which only its location is important and its extent in space is not important. For example, the balloons labelled $A$ to $J$ point to the locations of computer shops around the university. The lines represent the facilities of moving through space or connections in space (i.e., roads, rivers). A region represents the spatial object for which its spatial extent is also important. A region may consist of disjoint pieces each containing many polygons. In the figure, University of New South Wales and Prince of Wales Hospital are represented by regions.

Figure: Google Maps (http://maps.google.com)

Spatial databases are also termed as image, pictorial, geometric and geographic databases. The application of spatial databases include Geographic Information Systems (GIS), Computer Aided Design (CAD), Very-Large-Scale Integration (VLSI) designs, Multimedia Information System (MMIS) and medicine and biological research.

Additional functionality must be added for databases to process spatial data objects because spatial data objects have complex structure and are multidimensional and there is no standard algebra defined for spatial data. Moreover, the spatial data objects are usually dynamic and the storage structure should allow efficient insertions and deletions of data. A spatial database needs to support different kind of spatial queries. For example, a query may be issued to find all police stations in Sydney. Logically, this query is to find one kind of spatial objects (police stations) that are contained by the other type of spatial object (Sydney). Another example which we already have seen is a query to find the computer shops near University of New South Wales. The spatial database needs to find the spatial objects (computer shops) that are closer to some other spatial object (the university).

To support the search operations on spatial data objects, special data structures are needed to be designed. These data structures are usually called spatial indexes or spatial access methods. In Section , we briefly describe why traditional one-dimensional indexes cannot be used in spatial databases and we also discuss the important requirements a good spatial access method should meet. In Section , we describe few basic and advanced spatial queries. Section  summarizes the contributions of this thesis towards spatial databases. Thesis organization is presented in Section .