Jose Antonio Cotelo Lema (1), Luca Forlizzi (2), Ralf
Hartmut Güting (3),
Enrico Nardelli (2), and M. Schneider
(3)
(1) Laboratorio de Bases de Datos, Facultade de
Informatica, Universidade da Coruna,
A Coruna, Spain,
jaclema@mail2.udc.es
(2) Dipartimento di Matematica Pura ed Applicata,
Universita Degli Studi di L'Aquila,
L'Aquila, Italy, {forlizzi,
nardelli}@univaq.it
(3) Praktische Informatik IV, Fernuniversität
Hagen, D-58084 Hagen, Germany
{Markus.Schneider,
gueting}@fernuni-hagen.de
Abstract: Whereas earlier work on spatio-temporal databases generally focused on geometries changing in discrete steps, the emerging area of moving objects databases supports geometries changing continuously. Two important abstractions are moving point and moving region, modeling objects for which only the time-dependent position, or also the shape and extent are relevant, respectively. Examples of the first kind of moving entity are all kinds of vehicles, aircraft, people, or animals; of the latter hurricanes, forest fires, forest growth, or oil spills in the sea. The goal is to develop data models and query languages as well as DBMS implementations supporting such entities, enabling new kinds of database applications.
In earlier work we have proposed an approach based on abstract data types. Hence, moving point or moving region are viewed as data types with suitable operations. For example, a moving point might be projected into the plane, yielding a curve, or a moving region be mapped to a function describing the development of its size, yielding a real-valued function. A careful design of a system of types and operations (an algebra) has been presented, emphasizing completeness, closure, consistency and genericity. This design was given at an abstract level, defining, for example, geometries in terms of infinite point sets. In the next step, a discrete model was presented, offering finite representations and data structures for all the types of the abstract model.
The present paper provides the final step towards implementation
by studying and developing systematically algorithms for (a large
subset of) the operations. Some of them are relatively
straightforward; others are quite complex. Algorithms are meant to be
used in a database context; we also address filtering techniques and
practical issues such as large object management or numeric
robustness in the context of an ongoing prototype implementation.
Keywords: spatio-temporal databases, moving objects databases, algorithms, moving point, moving region
Published: FernUniversität Hagen, Informatik-Report 289, October 2001.