4 Spatio-temporal Models and Languages: An Approach Based on Data Types
Martin Erwig, Christian S. Jensen, Enrico Nardelli, Markus Schneider · 2003
vs. Discrete Modeling. What does it mean to develop a data model with spatio-temporal data types? Actually, this is a design of a many-sorted algebra. There are two steps: 1. Invent a number of types and operations between them that appear to be suitable for querying. So far these are just names, which means one gives a signature. Formally, the signature consists of sorts (names for the types) and operators (names for the operations). 2. Define semantics for this signature, that is, associate an algebra, by defining carrier sets for the sorts and functions for the operators. So the carrier set for a type α contains the possible values for α, and the functions are mappings between the carrier sets. For a formal definition of many-sorted signature and algebra see [24] or [18]. Now one can make such designs at two different levels of abstraction, namely as abstract or as discrete models. Abstract models allow us to make definitions in terms of infinite sets, without worrying whether finite representations of these sets exist. This allows us to view a moving point as a continuous curve in the 3D space, as an arbitrary mapping from an infinite time domain into an also infinite space domain. All the types that we get by application of the type constructor τ are functions over an infinite domain, hence each value is an infinite set. This abstract view is the conceptual model that we are interested in. The curve described by a plane flying over space is continuous; for any point in time there exists a value, regardless of whether we are able to give a finite description for this mapping (or relation). In Section 4.2.2 we have in fact described the types mentioned under this view. In an abstract model, we have no problem in using types like “moving real”, mreal, and operations like mpoint×mpoint → mreal mdistance since it is quite clear that at any time some distance between the moving points exists (when both are defined). 4 Models and Languages: Data Types 105 The only trouble with abstract models is that we cannot store and manipulate them in computers. Only finite and in fact reasonably small sets can be stored; data structures and algorithms have to work with discrete (finite) representations of the infinite point sets. From this point of view, abstract models are entirely unrealistic; only discrete models are usable. This means we somehow need discrete models for moving points and moving regions as well as for all other involved types (mreal, region, . . . ). We can view discrete models as approximations, finite descriptions of the infinite shapes we are interested in. In spatial databases there is the same problem of giving discrete representations for in principle continuous shapes; there almost always linear approximations have been used. Hence, a region is described in terms of polygons and a curve in space (e.g. a river) by a polyline. Linear approximations are attractive because they are easy to handle mathematically; most algorithms in computational geometry work on linear shapes such as rectangles, polyhedra, etc. A linear approximation for a moving point is a polyline in 3D space; a linear approximation for a moving region is a set of polyhedra (see Figure 4.2). Remember that a moving point can be a partial function, hence it may disappear at times, the same is true for the moving region.