Abstract
A Spatial Database is a database that offers spatial data types, a query language with spatial predicates, spatial indexing techniques, and efficient processing of spatial queries. All these fields have attracted the focus of researchers over the past 25 years. The main reason for studying spatial databases has been applications that emerged during this period, such as Geographical Information Systems, Computer-Aided Design, Very Large Scale Integration design, Multimedia Information Systems, and so forth. In parallel, the field of temporal databases, databases that deal with the management of timevarying data, attracted the research community since numerous database applications (i.e., Banking, Personnel Management, Transportation Scheduling) involve the notion of time.
TopBackground
A Spatial Network can be considered a special kind of graph. A graph is a set of nodes and a set of edges connecting such nodes. Within this context, a Spatial Network is a graph in which the edges between nodes are constrained by the location of the nodes in space. Depending on the Spatial Network application, the graph can be directed (e.g., edges modeling one-way roads or gas distribution pipes) or not (e.g., edges modeling two-way roads or pedestrian streets), weighted (e.g., edges having a weight, such as speed limit or the number of lanes of a road), planar (e.g., a graph that can be drawn so edges do not intersect in the plane, such as a river network where river intersections correspond to graph nodes), or nonplanar (e.g., an electricity network where cables may intersect without an electrical junction between them). For example, in Figure 1, a part of a road network is depicted. The arrows indicate one-way roads. The filled circles indicate points of interest (e.g., gas stations A, B, and C), while the nonfilled circle represents the position of a motorist identified by q. The double-arrow symbol represents the permitted changes of direction at the related crossroad.
Figure 1. An example of a road network
This graph-theoretic approach leads to a conceptual modeling of Spatial Networks that is independent of specific implementations and data management technologies (e.g., relational or object-oriented database management systems). By considering the representation of a Spatial Network graph through a specific data management technique, such as a set of interrelated tables or a collection of interreferenced objects, we reach a logical model, while the physical model of a Spatial Network describes the storage and indexing techniques used for the representation of the network.
Key Terms in this Chapter
Trajectory: The track followed by a moving object in the course of time (due to the change of its position).
Spatial Access Method, or Spatial Index: A technique of organizing spatial data (multidimensional data such as points, line segments, regions, polygons, volumes, or other kinds of geometric entities) that allows the efficient retrieval of data according to a set of search criteria.
Spatial Database: A database that offers spatial data types, a query language with spatial predicates, spatial indexing techniques, and efficient processing of spatial queries.
Moving Object or Moving Point: An entity (data element) in space with a varying position in the course of time. At any specific time instance, a moving object is characterized by its position, its direction of movement, and its speed of movement.
Spatial Network Database: A spatial database where the data modeled, stored, and queried are Spatial Network data.
k Nearest Neighbor Query: A query of finding k entities (data elements) among a group of entities that is nearest (according to a distance function) to a given (query) entity.
Spatial Query: A request expressed as a combination of spatial conditions (e.g., Euclidean distance from a query point) for extracting specific information from a large amount of spatial data without actually changing these data.
Spatial Network: A collection of interconnected elements that have the shape of curves, or polylines, appearing in geographic applications (e.g., a railway network, an electricity network, a road network).
Range Query: A query of finding all entities (data elements) among a group of entities with distances (according to specific distance functions) from a given (query) entity that satisfy some given conditions (e.g., with Euclidean distance that is smaller than a given value or with horizontal and vertical distances smaller than two respective given values).
Graph: A set of nodes and a set of edges connecting such nodes.