Spatio-temporal databases deal with geometries changing over time. The goal
of our work is to provide a DBMS data model and query language capable of
handling such time-dependent geometries, including those changing continuou
sly that describe moving objects. Two fundamental abstractions are moving p
oint and moving region, describing objects for which only the time-dependen
t position, or position and extent, respectively, are of interest. We propo
se to represent such time-dependent geometries as attribute data types with
suitable operations, that is, to provide an abstract data type extension t
o a DBMS data model and query language. This paper presents a design of suc
h a system of abstract data types. It turns out that besides the main types
of interest, moving point and moving region, a relatively large number of
auxiliary data types are needed. For example, one needs a line type to repr
esent the projection of a moving point into the plane, or a "moving real" t
o represent the time-dependent distance of two moving points. It then becom
es crucial to achieve (i) orthogonality in the design of the type system, i
.e., type constructors can be applied uniformly; (ii) genericity and consis
tency of operations, i.e., operations range over as many types as possible
and behave consistently; and (iii) closure and consistency between structur
e and operations of nontemporal and related temporal types. Satisfying thes
e goals leads to a simple and expressive system of abstract data types that
may be integrated into a query language to yield a powerful language for q
uerying spatio-temporal data, including moving objects. The paper formally
defines the types and operations, offers detailed insight into the consider
ations that went into the design, and exemplifies the use of the abstract d
ata types using SQL. The paper offers a precise and conceptually clean foun
dation for implementing a spatio-temporal DBMS extension.