| The idea of a map is a fundamental metaphor in spatial systems. For instance, in the fields of geographical information systems (GIS), spatial databases, geography, robotics, computer assisted design (CAD), and spatial cognition, the arrangement of spatial data into map form plays a primary role in the composition, representation, and analysis of spatial data. However, no models of maps currently exist that provide a precise definition of a spatial data type for maps and operations over them. Instead, many informal definitions are provided, many of which are tied to specific implementation concepts. Furthermore, although the integration of spatial databases into spatial fields such as GIS has received much attention, the notion of integrating maps into databases has been overlooked. Thus, the idea of integrating maps into SQL and performing queries over them has not yet been explored. This thesis describes the design and implementation of Map Algebra, a type system and operations for maps in spatial databases. We provide a three level approach to defining Map Algebra. First, we provide an abstract model of maps. This is a mathematical description of maps and their operations and topological predicates. This model is defined on formal mathematical concepts that are not implementable in computer systems; therefore, we then provide a discrete model of maps based on discrete concepts that can be translated to computer systems. We then provide an implementation model of maps, complete with algorithms to implement map operations, that can be directly implemented in a computer system. Furthermore, we develop a query language called Map Query Language that can be used to pose queries over maps in databases. |
