{'fraction_non_alphanumeric': 0.050749871394088084, 'fraction_numerical': 0.015313996280321316, 'mean_word_length': 3.9435641627543037, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 6, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 21, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Classes of Spatiotemporal Objects and Their Closure Properties

We present a data model for spatio-temporal databases. In this model spatio-temporal data is represented as a finite union of objects described by means of a spatial reference object, a temporal object and a geometric transformation function that determines the change or movement of the reference object in time. We define a number of practically relevant classes of spatio-temporal objects, and give complete results concerning closure under Boolean set operators for these classes. Since only few classes are closed under all set operators, we suggest an extension of the model, which leads to better closure properties, and therefore increased practical applicability. We also discuss a normal form for this extended data model.


Introduction
Many natural or man-made phenomena have both a spatial and a temporal extent. Consider for example a forest fire, a meteorological event (e.g., the movement of clouds pressure areas), property histories in a city or the flight of an air plane. To store information about such phenomena in a database, appropriate data modeling constructs are needed.
In this paper, we introduce and discuss a general framework for specifying spatiotemporal data. Hereto, the new concept of spatio-temporal object is introduced. We represent a spatio-temporal object as a finite number of objects represented by means of a spatial reference object, a temporal object (i.e., a time interval) and a timedependent geometric transformation that determines how this spatial object moves or changes through space during the considered time interval. Although this model is suited for data in arbitrary dimensions, we focus on two-dimensional reference objects that move or change during time.
In this framework, a number of classes of practically relevant spatio-temporal objects arise naturally. These classes are indexed by the type of spatial reference object and the type of transformation functions that are allowed. On the level of reference objects, we consider polygons, triangles, triangles with two sides parallel to the coordinate axes of the two-dimensional plane and rectangles with all sides parallel to the coordinate axes. We consider time-dependent affinities, scalings and translations for what concerns transformation functions. These functions can be expressed by rational, polynomial, respectively linear functions.
We investigate these classes with respect to closure under Boolean set operations, namely union, intersection and set-difference.
By definition, these classes are closed under union (a spatio-temporal object is described as the union of atomic objects). We call a class closed under intersection (respectively set-difference) if any finite intersection (respectively set-difference) of objects from a class can again be described by an object from that class (i.e., as a union of atomic objects). The classes that we consider are not necessarily closed under intersection and set-difference.
We provide an in-depth and exhaustive study of their closure with respect to all set-theoretic operations, and we conclude that our model for representing spatiotemporal data gives very poor closure results for the classes of objects we considered important for spatio-temporal practice. The only classes that seems to be useful in this respect have polygons as spatial reference objects and use rational affinities to move or change these objects in time.
A conclusion is that we have to enrich the data model by allowing set-theoretic operations other than union in the construction of geometric objects from atomic geometric objects. As soon as we also allow spatio-temporal objects to be constructed from atomic ones by means of union and intersection (or union and set-difference) then the model becomes closed for all Boolean set operations. Indeed, as an important result, we show that our classes, that are drawn from practice, have the nice property that they are closed under intersection if and only if they are closed under set-difference.
To appreciate the need for applying set-theoretic operators to spatiotemporal objects, consider the following scenario. Let two spatial objects represent the extents of the safe areas around two different ships. Taking into account the movement of ships, the extents of the safe areas over a period of time can be represented as two spatiotemporal objects. To avoid collisions, one needs to be able to determine the intersection of those objects.
The substantial literature on spatial and temporal databases does not provide much guidance in dealing with spatiotemporal phenomena. Spatial databases [20] deal with spatial objects (e.g., rectangles or polygons) and temporal databases [17] with temporal ones (e.g., time intervals). Their combination can handle discrete change [19] but not continuous change, which is required by applications dealing with phenomena like movement, natural disasters, or the growth of urban areas. In the latter applications, the temporal and spatial aspects cannot be conveniently separated.
Spatiotemporal data models and query languages are a topic of growing interest. The need to model both discrete and continuous change has been identified. The issue of closure under Boolean set operations has also received in this context a considerable attention. This is not surprising, since, for example, closure under intersection is essential for spatiotemporal join.
The paper [19] presents one of the first such models. However, it is only capable of modeling discrete change.
In [6] the authors define in an abstract way moving points and regions. Apart from moving points, no other classes of concrete, database-representable spatiotemporal objects are defined. In that approach continuous movement (but not growth or shrinking) can be modeled using linear interpolation functions. In the subsequent paper [7], the authors discuss a concrete, polyhedral representation of moving, growing and shrinking regions, which is applicable only to significantly restricted classes of spatiotemporal objects. This guarantees closure but eliminates the possibility of representing scaling and more general transformations. The results of the present paper shed some light on when similar concrete representations exist and when they do not.
In [9] the authors propose a formal spatiotemporal data model based on constraints in which, like in [19], only discrete change can be modeled. An SQL-based query language is also presented.
We have proposed elsewhere [5] a spatiotemporal data model based on parametric polygons: polygons whose vertices are defined using linear functions of time. This model is also capable of modeling continuous change but is not closed under intersection. A variation of this model restricted to rectangles but extended with periodic functions is given in [3]. The latter model is closed under set theoretic operators, enabling the definition of an extended relational algebra query language, for which query evaluation can be done in PTIME in the size of the input spatiotemporal database. The closure properties for [5] and [3] seem analoguous to the closure properties of the framework presented in this paper, respectively, but the relationships among these frameworks needs to be further explored.
Both discrete and continuous change can be represented using constraint databases [12]. Compared to the latter technology, our approach seems more constructive and amenable to implementation using standard database techniques. On the other hand, constraint databases do not suffer from the lack of closure under intersection. To some degree, it is due to the fact that the intersection of two generalized tuples in constraint databases need not immediately computed but rather the tuples may be only conjoined together. In most implementations of constraint databases [2,10,15] the "real" computation of the intersection occurs during projection or the presentation of the query result to the user. It is unclear whether such a strategy offers any computational advantages over the approach in which the intersections are computed immediately. In fact, recent work on spatial constraint databases [13] proposes extensions to relational algebra that require immediate computations of spatial object intersections. Also, our approach is potentially more general than constraint databases. For example, by moving beyond rational functions (but keeping the same basic framework) we can represent rotations with a fixed center. Finally, in our model it is easy to obtain any snapshot of a spatiotemporal object, making tasks like animation straightforward. It is not so in constraint databases where geometric representations of snapshots have to be explicitly constructed from constraints [4].
This paper is organized as follows: In Section 2, we give definitions and describe the relevant classes of spatio-temporal objects. The closure results for these classes with respect to Boolean set operations are given in Section 3. We propose the extended model in Section 4 and describe a normal form for objects in this extended model. Section 5 gives comments and concludes the paper.

Definitions and preliminaries
In this section, we define the notion of spatio-temporal object. In our approach, a spatio-temporal object consists of a spatial reference object, a time interval during which the spatio-temporal object exists and a continuous transformation that defines how the spatial reference object moves and changes during the interval of time.

Spatio-temporal and geometric objects
Let R be the set of real numbers and R 2 be the 2-dimensional real plane.
These definitions are very general and disregard the fact that objects should be finitely representable in the computer's memory. In this paper, we will study more restricted classes of spatial and spatio-temporal objects that are important from a practical point of view and have simple and efficient representations. Such classes have been identified in the course of spatial and spatio-temporal database research.
Here, we propose a geometric approach: a spatio-temporal object is defined as a spatial reference object together with a continuous transformation that defines how the object moves or changes during some time interval.
Definition 2.2 An atomic geometric object O is a triple (S, I, f ), where • S ⊂ R 2 is the spatial reference object of O, which is semi-algebraic 1 in R 2 ; • I ⊂ R is the time domain of O, which is a connected and bounded semi-algebraic set in R (i.e., a point or a bounded interval); and which is semi-algebraic 2 and continuous both in the time coordinate and in the spatial coordinates.
The semantics of an atomic geometric object O = (S, where p is a polynomial with integer coefficients in the real variables x 1 , x 2 , ..., x d . 2 A function f is said to be semi-algebraic if its graph is a semi-algebraic subset of (R 2 × R) × R 2 .
We remark that this definition guarantees that there is a finite representation of an atomic geometric object by means of the polynomial inequalities that describe its reference object, its time domain and the graph of its transformation function. This means that this data model is within the constraint model for databases (we refer to [14] for an overview of the research results in this area).

Definition 2.3
A geometric object is a finite set of atomic geometric objects. The semantics of a geometric object {O 1 , . . . , O n } is the union of the semantics of the atomic objects that constitute it, i.e., the set 1≤i≤n st(O i ).

⊓ ⊔
We agree that whenever we write "the spatio-temporal object O", where O is an (atomic) geometric object, we mean the semantics of the (atomic) geometric object O. Also, when O = (S, I, f ) is an atomic object and t ∈ I, we will refer to the set y ′ , t))} as the frame of O at time t and we will denote it f (S; t).
We define the time domain of a geometric object to be the smallest time interval that contains all the time domains of the composing atomic geometric objects. Recall that the smallest interval containing a set of intervals is also known as the convex closure of this set. We denote the convex closure of the sets I 1 , I 2 , ..., I n by Remark that a spatio-temporal object is empty (or non-existing) outside the time domain of the geometric object that defines it. Also, within its time domain a spatiotemporal object can be empty (for instance, at any moment when no atomic geometric object exists).
We conclude this section by remarking that the above introduced notions of spatial and spatio-temporal object and of (atomic) geometric object can be generalized to arbitrary dimension d (by simply substituting d for 2 in the above definitions). Since all the results in this paper are formulated for dimension 2, we have chosen not to use this generalization here.

Practically relevant classes of geometric objects
Here, we define special classes of geometric objects that are relevant to spatio-temporal database practice. These classes are denoted by S, F and they are determined by the type S of spatial reference object and the type F of transformation function. For clarity, a geometric object belongs to a class if all of its atomic geometric objects belong to that class.
The classes of geometric figures in the plane R 2 that we will consider are • S Poly , the class of arbitrary polygons, • S Tr , the class of arbitrary triangles, • S TrAx , the class of triangles with two sides parallel to the coordinate axes, and • S Rect the class of rectangles with all sides parallel to the coordinate axes.
In this paper, we assume triangles, polygons and rectangles to be filled objects. But since we allow two or more corner points of a triangle or rectangle to coincide, the model can deal with polylines and points too. A line segment and a point are considered triangles. Also line segments parallel to the axes and points are considered rectangles. Finally, note that S Rect ⊂ S TrAx ⊂ S Tr ⊂ S Poly .
The classes of transformation functions we will consider are • F Aff , the class of the affine transformations, • F Sc , the class of the scalings, • F Trans , the class of the translations, and • F id , the class consisting of the identity mapping.
It is clear that F id , F Trans and F Sc are subclasses of F Aff . More technically, these classes are defined as follows. The class F Aff of affine transformations consists of the mappings The corresponding classes of transformations will be denoted using superscripts F Rat , F Poly , and F Lin . For example, F Rat Sc represents the class of rational scalings. We assume that the time domain of an atomic geometric object belongs to the domain of the transformation function and that the denominator of a rational function in the definition of a transformation is never zero in the closure of the time domain (thus, the moving figure will remain within fixed bounds during the time domain).
Note that the shape of a spatio-temporal object at a certain time instant is not necessarily the same as the shape of the reference object of the geometric object that gives rise to the spatio-temporal object. For example, a rectangle is mapped to a parallelogram under an affinity. In this time domain, S A remains at its place (i.e., f A (x, y; t) = (x, y) for all t), while S B is translated with constant speed (equal to 1) in the direction of the positive y-axis (i.e., f B (x, y; t) = (x, y + t). The functions f A and f B belong to F Lin Trans . At t = 0 both objects intersect in a line segment. For 0 < t < 1 they intersect in a hexagon, for 1 ≤ t < 2 in a quadrangle, and finally for t = 2 in a point.

Closure properties under Boolean set operations
In this section, we work with the classes S, F introduced in the previous section, and we investigate which of these classes S, F are closed under the Boolean set operations ∪ (union), ∩ (intersection) and \ (set difference). We first define what closure means.
Definition 3.1 Let θ be one of the operations ∪, ∩ or \. We say that the class S, F is (atomically) closed under θ if for any two (atomic) geometric objects We will refer to an object O that satisfies the condition in the definition as an intersection, union or difference of O 1 and O 2 (they need not be unique).
For the union operation, the closure follows immediately from the definition. For ∩ and \ the situation is more complicated. The next theorem is the main result that we want to prove in this section. It summarizes the closure results for intersection and set-difference.
Theorem 3.1 For any class of objects S among S Poly , S Tr , S TrAx and S Rect and any class of transformations F among F Aff , F Sc , F Trans and F id , the closure with respect to ∩ and \ is summarized in the following table.
The items marked with † are from [19]. The remainder of this section is devoted to proving this theorem. We do this by first proving some lemmas in a first subsection that reduce the number of cases that have to be looked at and by then proving the remaining cases in a second subsection.

Reduction properties
The properties in this section reduce the number of cases that have to be investigated. First, we give a set-theoretic lemma that will be used frequently.
Proof. The first equality follows directly from distributivity of intersection with respect to union. The second equality can be proven by induction on m, using the observation that ( where B c denotes the complement of B with respect to some universe.

⊓ ⊔
The next property says that for ∩ and \ closure and closure on atomic objects coincide. For the if-direction of (a), assume that S, F is atomically closed under ∩ and let {O 1,1 , O 1,2 , . . . , O 1,n } and {O 2,1 , O 2,2 , . . . , O 2,m } be two geometric objects from S, F . By using Lemma 3.1 (a), we get Since ∩ is assumed to be atomically closed, each st(O 1,i )∩st(O 2,j ) can be written as a union lij k=1 st(O k,i,j ), where each O k,i,j is an atomic geometric object. Therefore, the intersection of . This completes the proof of the if-direction of (a). For the if-direction of (b), assume that S, F is atomically closed under \ and let k is an atomic geometric object. This proves the case m = 1. Next, assume we have shown that m } is also the semantics of a geometric object from S, F . This completes the proof.
⊓ ⊔ The following property states that intersection and set-difference are equivalent with respect to closure. Proof. By Property 3.2 it suffices to prove this property for atomic geometric objects.
For the if-direction, assume that S, F is closed under \ and let O 1 and O 2 be two atomic geometric objects from S, F . Since, Using the argumentation from the proof of the if-direction of (b) of Property 3.2, we can show that this set is again a union of semantics of atomic geometric objects from S, F .
For the only-if direction, assume that S, F is closed under ∩ and let O 1 = (S 1 , I 1 , f 1 ) and O 2 = (S 2 , I 2 , f 2 ) be two atomic geometric objects from S, F . We We can restrict our attention to the set st(O 1 ) \ st(O 2 ) in the interval I 1 ∩ I 2 rather than in the complete interval I 1 ∪I 2 (since the set-difference is empty in I 2 \ I 1 and equal to O 1 in I 1 \ I 2 ). Let I denote the topological closure of Figure 2: Examples of partitions of the set α(S 2 ) \ S 2 for the classes S Poly , S Tr , S TrAx , and S Rect respectively. f 1 (x ′ , y ′ , t) = f 2 (x, y; t))} is compact (i.e., topologically closed and bounded) since it is the image of the compact set S 1 × I under the continuous function f −1 2 • f 1 . Therefore, also S = S 2 ∪ S B is a compact set in R 2 . Let α : (x, y) → (ax + b 1 , ay + b 2 ) be a scaling followed by a translation that maps S 2 to a set that strictly contains S (this is possible since S is bounded). Remark that α maps any line to a parallel line. Let O 3 be the atomic geometric object (α(S 2 ), I, f 2 ). At any moment t in I, we thus have that f 2 (S 2 ; t) ⊂ f 2 (α(S 2 ); t) (since affinities are monotone mappings) and can always be written as the semantics of a geometric object in S, F where S and F are any pairs allowed in Theorem 3.1. For each of the classes S Poly , S Tr , S TrAx , and S Rect this is illustrated in Figure 2. For each of these classes α(S 2 ) \ S 2 can be partitioned into a finite number of reference objects T 1 , ..., T n from these classes. So, define the atomic geometric objects ) can be written as such a union. This completes the proof.

⊓ ⊔
A final reduction property says that the closure results for polygons and triangles coincide. We can therefore concentrate on triangles further on. Proof. This property follows from the fact that any atomic geometric object O = (S, I, f ) from S Poly , F corresponds to a geometric object from S Tr , F . Indeed, let T 1 , . . . , T n be an arbitrary triangulation of the polygon S. The geometric object So, if S Poly , F is closed under θ, then also any union, intersection or set-difference of two elements of S Tr , F is again a geometric object of S Poly , F and because of the above argument also of S Tr , F .
On the other hand, suppose that S Tr , F is closed under θ. If O 1 and O 2 are objects in S Poly , F , then so are their union, intersection or set-difference, since they are in S Tr , F , which is a subclass of S Poly , F . ⊓ ⊔

Closure and non-closure proofs
In this section, we complete the proof of Theorem 3.1, by means of a series of lemmas that cover all the cases presented in the matrix of Theorem 3.1. Here, we take the reduction results of the previous section into account. In particular, we only consider intersections or set-differences of atomic geometric objects, and we do not have to consider polygons any more.

Finite time partition
Before giving these lemmas we introduce the technical notion of finite time partition. This will be of use in many of the proofs in this section. The finite time partition property tells us how and when the form (or appearance) of the intersection or setdifference of two atomic geometric objects changes. We observe that the intersection of two moving triangles can be empty, a single point, a straight line segment, a triangle, a quadrangle, a pentagon and a hexagon. The intersection of two moving rectangles can be empty, a single point, a line segment or a rectangle. We refer to all these different forms of the intersection or the set-difference as their possible shapes. Also the difference of two triangles or two rectangles can take a finite number of different shapes. In the example in Figure 1, the intersection takes four different shapes, whereas the difference takes five different shapes. We define this notion now more technically. Let O 1 = (S 1 , I 1 , f 1 ) and O 2 = (S 2 , I 2 , f 2 ) be two atomic geometric objects with rational affine transformations with time domains I 1 and I 2 . In the following, we denote by I 1 ∪ I 2 the convex closure of the set I 1 ∪ I 2 in R. Let t be in I 1 ∪ I 2 . Firstly, we call any line that intersects the border of f i (S i ; t) in infinitely many points, a carrier of the frame f i (S i ; t) and denote it car(f i (S i ; t)) (i = 1, 2).  (S 1 ; t)) ∪ car(f 2 (S 2 ; t)) and car(f 1 (S 1 ; t ′ )) ∪ car(f 2 (S 2 ; t ′ )) are topologically equivalent sets 3 in R 2 . Proof. Let O 1 = (S 1 , I 1 , f 1 ) and O 2 = (S 2 , I 2 , f 2 ) be two atomic geometric objects satisfying the conditions of the statement of this property. From the assumption that the reference objects S 1 and S 2 are semi-algebraic and the transformation functions f 1 and f 2 are affine rational functions, it follows that the sets st(O 1 ) and st(O 2 ) are semialgebraic subsets of R 2 × R (for details on this type of basic results on semi-algebraic sets, we refer to Chapter 2 of [1]). Let I be the set I 1 ∪ I 2 .
Also, the set A = t∈I1∪I2 (car(f 1 (S 1 ; t)) ∪ car(f 2 (S 2 ; t))) is semi-algebraic, since it can be defined in the first-order logic of the reals over the semi-algebraic sets st(O 1 ) and st(O 2 ) (this closure property of first-order logic over the reals can be found in Chapter 2 of [14]). We can therefore consider the set A as a subset of R 2 × R parameterized by the time parameter t. It follows from Semi-algebraic Triviality (Theorem 9.3.2 in [1] and also page 147 in [18]) that the set A induces a finite partition on I 1 ∪ I 2 such that in each partition class A remains topologically equivalent.

Technical lemmas
The following two lemmas are technical lemmas that say that two/three points that move with their respective rational affinities can be combined into one line/triangle that moves by a single rational affinity. For the proofs we refer to the Appendix.
be three atomic geometric objects with g i ∈ F Rat Aff . If the three points (x 1 , y 1 ), (x 2 , y 2 ) and (x 3 , y 3 ) form a triangle S (i.e., are not collinear) and if g 1 (x 1 , y 1 ; t), g 2 (x 2 , y 2 ; t) and g 3 (x 3 , y 3 ; t) form a triangle S t at any moment t ∈ I (i.e., are not collinear), then there exists an atomic geometric O = (S, I, g) with g ∈ F Rat Aff such that g i (x i , y i ; t) = g(x i , y i ; t) for all t ∈ I and i = 1, 2, 3.
⊓ ⊔ Lemma 3.3 Let O i = ({(x i , y i )}, I, g i ) (i = 1, 2) be two atomic geometric objects with g i ∈ F Rat Aff . If the two points (x 1 , y 1 ) and (x 2 , y 2 ) form a line segment L (i.e., are not equal) and if g 1 (x 1 , y 1 ; t) and g 2 (x 2 , y 2 ; t) form a line segment L t at any moment t ∈ I (i.e., are not equal), then there exists an atomic geometric O = (L, I, g) with g ∈ F Rat Aff such that g i (x i , y i ; t) = g(x i , y i ; t) for all t ∈ I and i = 1, 2.

⊓ ⊔
The next lemma shows that if two lines that move with a rational affinity intersect, also the intersection point is moved by a rational affinity. The proof of this lemma is in the Appendix. Aff that describes the intersection point of g 1 (L 1 ; t) and g 2 (L 2 ; t) in I. ⊓ ⊔

Results for affinities
We can now start our series of closure and non-closure lemmas and start with the affine transformations. For the most general classes we have the following positive result. First, suppose the intersection is a convex polygon. Let t 0 be a point in J l (even if it is a degenerated interval, J l contains at least one point). We take the intersection of f 1 (T 1 ; t 0 ) and f 2 (T 2 ; t 0 ) as reference object P . The set P ⊂ R 2 can be triangulated, for instance by connecting its corner points to its point of gravity: this yields triangles T ′ 1 , . . . , T ′ m (with 1 ≤ m ≤ 6). Each of the corner points (x 1 , y 1 ), (x 2 , y 2 ), (x 3 , y 3 ) of a triangle T ′ j is moved in the time interval J l by a rational affinity (in particular it is moved f 1 or f 2 applied to the inverse image of f 1 (·; t 0 ), respectively f 2 (·, t 0 )). More specifically, a corner point of T  Proof. It suffices to prove the lemma for triangles. We give a counterexample for intersection that serves for both classes S Tr , F Lin Aff and S Tr , F Poly Aff . Consider two atomic geometric objects O 1 and O 2 with reference objects triangles with corner points (1, 1), (3, 1), (2, 3) and (2, 2), (4, 2), (3,4), respectively. The affine transformations of these triangles are given by the matrices t 2t 3t t and t 2t + 1 t 3t + 1 , respectively. Assume these objects are moved in some interval of the strictly positive t-axis (for example I = [1, 2]), the intersection of the two objects is a triangle with corner points (6t + 2, 8t + 2), ( 1 2 t (181t+70) (13t+4) , 1 2 t (243t+70) (13t+4) ) and ( 29 4 t, 37 4 t). Assume that this triangle could be represented as a geometric object {O 1 , . . . , O m } from S Tr , F Poly Aff . Then, there exists some subinterval J of I during which the corner point ( 1 2 t (181t+70) (13t+4) , 1 2 t (243t+70) (13t+4) ) is the image of a corner point (x 0 , y 0 ) of a reference triangle that is transformed by a polynomial (or linear) affinity. We therefore have that, for instance the x-coordinate 1 2 t (181t+70) (13t+4) of the above point is of the form a(t)x 0 + b(t)y 0 + e(t) for t ∈ J with a(t), b(t) and e(t) polynomials (or linear polynomials) in t. Therefore, 181t 2 + 70t − 2(a(t)x 0 + b(t)y 0 + e(t))(13t + 4) = 0 for all t ∈ J. Since the number of zero's of this polynomial exceeds its degree, it is identical to zero. Therefore, a(t)x 0 + b(t)y 0 + e(t) is of the form αt + β. This leads to the conditions β = 0, 181 = 26α and 70 = 8α. There is no solution and we have a contradiction. ⊓ ⊔ Proof. Let us first consider the class S Rect ,F Rat Aff . Because of Lemmas 3.2, and 3.3, it suffices to consider the intersection of two atomic geometric objects O 1 = (R 1 , I 1 , f 1 ) and O 2 = (R 2 , I 2 , f 2 ). The image of a rectangle under an affinity is a parallelogram. The shape of the intersection of f 1 (R 1 ; t) and f 2 (R 2 ; t) for some t in I 1 ∩ I 2 can therefore be a convex polygon with at most eight corner points, a line segment or a point.
In any of these cases, we can copy the argumentation used in the proof of Lemma 3.5. In case the intersection is a line segment or a point, this settles the case. In the case where it is a convex polygon, we can reuse the triangulation technique presented in the proof of Lemma 3.5, now noting that it can consist of at most eight triangles instead of six. So, we get that the intersection of O 1 and O 2 can be described by the atomic geometric objects (T ′ j , J l , f j ) (1 ≤ j ≤ m ≤ 8), where the T ′ j are triangles and the f j are rational affinities.
For the purpose of this lemma, we need to describe the intersection of O 1 and O 2 by means of moving rectangles, however. This can be achieved by replacing each of the triangles T ′ j by three rectangles R 1j , R 2j and R 3j . Let the corner points of T ′ j be (x 1 , y 1 ), (x 2 , y 2 ) and (x 3 , y 3 ). The rectangle R ij are chosen such that a constant affinity f ij maps R ij to the parallelogram with corner points (x i , y i ), 1 2 (x 1 +x 2 , y 1 +y 2 ), 1 2 (x 1 + x 3 , y 1 + y 3 ) and 1 2 (x 3 + x 2 , y 3 + y 2 ) (i = 1, 2, 3). So, T ′ j is the union of the three parallelograms: we get a description of the intersection of O 1 and O 2 during J l in terms of atomic geometric objects from S Rect ,F Rat Aff . The closure result for S TrAx ,F Rat Aff can be obtained by further dividing the rectangles R i,j along a diagonal into two triangles from S TrAx .

respectively.
In some interval of the strictly positive t-axis, the intersection of the two objects is a triangle with corner points (6t + 2, 8t + 2), (t (28t+15) (3t+2) , 3t (13t+2) (3t+2) ) and ( 21 2 t, 17 2 t). The same type of argumentation as in the proof of Lemma 3.6, can be used to show that at least a rational affinity is needed to describe the intersection. Therefore, both S Rect ,F Lin Aff and S Rect ,F Poly Aff are not closed for intersection and set-difference. Secondly, for S TrAx ,F L Aff , we can reuse the above counterexample leaving out the corner points (1, 1) and (4,4) respectively. The intersection remains the same and the argumentation can be repeated.

⊓ ⊔
The proof of Lemma 3.5 is based on the property that affinities do not preserve parallelism to the axes. We will see later that for scalings, which do preserve parallelism to the axes, the class of the objects of S TrAx is not closed.

Results for scalings
We divide the results for scalings into one positive and two negative results. Proof. Because of Lemmas 3.2, and 3.3, it suffices to consider the intersection of two atomic geometric objects O 1 = (R 1 , I 1 , g 1 ) and O 2 = (R 2 , I 2 , g 2 ). According to Property 3.5, the intersection of the two rectangles takes different shapes in elements of a finite partition of I 1 ∩ I 2 (we only consider this intersection, since elsewhere in I 1 ∪ I 2 the intersection of O 1 and O 2 is empty in any case). Let J be an interval in this partition. First, we remark that scalings map lines that are parallel to the x-axis or to the y-axis to a parallel line. Therefore, at any moment t in J both the frame of O 1 and the frame of O 2 are rectangles with sides parallel to the coordinate axis.
Let us assume that the intersection of O 1 and O 2 is a rectangle in J.
We remark that this intersection rectangle is uniquely determined by the coordinates of its upper-left corner point (x ul (t), y ul (t)) and the coordinates of the lowerright corner point (x lr (t), y lr (t)). Let assume the upper-left corner point of the intersection comes from O 1 and the lower-right from O 2 (possibly we have to work with the upper-right and lower-left corners, but this is equivalent). Let the scaling of O 1 be determined by a 1 (t), b 1 (t), e 1 (t), f 1 (t) and the one of O 2 by a 2 (t), b 2 (t), e 2 (t), f 2 (t) (following the matrix notation of section 2.2).
The intersection is an atomic geometric object O = (R, J, f ) composed as follows. The reference rectangle R has as upper-left corner point (x ul , y ul ) the upper-left corner point of the reference object R 1 of O 1 and as lower-right corner point (x lr , y lr ) the lower-right corner point of the reference object R 2 of O 2 (if (x lr , y lr ) and (x lr , y lr ) have an x-or y-coordinate in common, we work with (x lr + 1, y lr + 1) instead of (x lr , y lr ) and replace e 2 (t) with e 2 (t) − a 2 (t) and f 2 (t) with f 2 (t) − b 2 (t) in the description of g 2 ). The transformation function g of O is determined by Proof. Consider the triangle with corner points (0, 0), (1, 0) and (0, 1) and the triangle with corner points ( 1 3 , 1), ( 2 3 , 1) and ( 2 3 , 0), both transformed by the identity transformation. Their intersection (for an illustration see (A) of Figure 3) cannot be described as a finite union of elements of S TrAx ,F L Sc since scalings map lines that are parallel to a coordinate axis to a parallel line. (Remember, for affinities, this class was closed, partly because affinities do not necessarily preserve parallelism with the coordinate axis.) ⊓ ⊔ The following lemma could be left out since it is implied by Lemma 3.12. We give it since its proof is conceptually easier, however. . The x-coordinate t+1 3t+2 is therefore of the form a(t)x 0 + e(t) with x 0 the x-coordinate of some corner point of a reference object, and a(t) and e(t) functions appearing in its transformation matrix. Therefore, a(t)x 0 + e(t) has degree 0, i.e., it is a number, say α. But then α(3t + 2) and t + 1 should be identical polynomials, leading to the equations 3α = 1 and 2α = 1 that clearly do not have a solution. It can therefore not be a linear or polynomial transformation.

⊓ ⊔
The next lemma completes the proofs for scalings. Proof. Because of Properties 3.2 and 3.4 it suffices to prove this lemma for atomic geometric objects that have a triangle as a reference object. We give an example of two atomic geometric objects O 1 and O 2 that have an intersection that cannot be described in S Tr ,F Rat Sc . Let the reference triangle of the atomic geometric object O 1 have corner points (0, 0), (1, 1) and ( 1 3 , 1 2 ) and let the transformation of this object be the scaling that maps (x, y) to Let the reference triangle of the atomic geometric object O 2 have corner points (0, 0), (1, 1) and (0, 1) and let the scaling of this object be the time-independent mapping that maps (x, y) to 4 0 0 4 We consider both objects in the time interval (0, 1 2 ). At any moment during this interval the intersection is given by the triangle with corner points (0, 0), ( 3(t+1) t+3 , t+1) and (1, 1). We remark that the point ( 3(t+1) t+3 , t + 1) is situated above the diagonal y = x and that in the limit towards 0, this point converges to (1,1). In other words, the intersection is always a triangle during the time interval (0, 1 2 ), but it converges to a line segment for t going to 0. It is easily verified that this intersection cannot be described as the image of a single triangle under a scaling from F Rat Sc . More generally, assume that this intersection is described by a geometric object Sc . At least one of the atomic objects describes a moving triangle that covers a line segment connecting (0, 0) and (f (t), f (t)) of the line connecting (0, 0) and (1, 1) during a time interval (0, ε] with ε > 0 (without loss of generality this interval can be assumed to be closed on the right side). Let the third cornerpoint (g(t), h(t)) be situated in the interior of the intersection triangle with cornerpoints (0, 0), ( 3(t+1) t+3 , t + 1) and (1,1). Let the scaling of this object be the one that maps (x, y) to where (a(t), b(t), c(t) and d(t) are rational functions of t. Without loss of generality the reference triangle of this atomic object can be assumed to have cornerpoints (0, 0), (1, 1), and (a, b), where the first is mapped to (0, 0), the second to (f (t), f (t)) and the third to (g(t), h(t)). Since we assume this reference object to be a triangle, we have a = b. It then follows that a(t) and b(t) must be equal to f (t) and that c(t) and d(t) must be constant 0. Therefore, this scaling maps the third cornerpoint (a, b) to (g(t), h(t)) = (af (t), bf (t)). Both a and b are therefore strictly positive. Since the point (af (t), bf (t)) is situated at the same side of the diagonal y = x as the point (0, 1), we get the condition bf (t) − af (t) > 0, or b > a. On the other hand, this point is situated on the same side as (0, 1) of the line connecting (0, 0) and ( 3(t+1) t+3 , t + 1). Therefore, we get From this a − 3 t+3 b > 0 follows, or 3b a < t + 3. Since t → t + 3 is strictly increasing in (0, ε] and has infimum 3 over this interval, we get 3b a ≤ 3, or b ≤ a. This contradicts b > a, that we obtained before. This concludes the proof. ⊓ ⊔

Results for translations
We give a general negative result for translations. Proof. First, we remark that translations preserve the shape and area of objects and the length of lines. Consider now two reference objects, located in the plane t = 0, from each of the relevant classes that have the interval [0, 1] on the x-axis as one of their sides. Let one reference object be located above the x-axis and the second be located below the xaxis. Let the first object undergo the translation (x, y) → (x − t, y) in the direction of the negative x-axis and let the second object undergo the translation (x, y) → (x+t, y) in the opposite direction, both in the time interval [0, t 0 ], for some t 0 > 0.
Then it is clear that the intersection of these objects is a shrinking line segment during the time interval [0, t 0 ]. So, in any of the cases, the intersection cannot be described as a finite union of translated objects.

Results for the identity
For completeness, we also give the results for the identity mapping.
Lemma 3.14 The classes S Poly ,F id , S Tr ,F id and S Rect ,F id are closed under ∩ and \. The class S TrAx ,F id is not closed under ∩ and \.
Proof. For the positive closure results, it suffices to remark the following. The intersection of two polygons is again a polygon (if line segments and points are considered to be in this class). The intersection of two triangles is a convex polygon with at most six corner points that can be triangulated, i.e., written as a disjoint union of triangles. The intersection of two rectangles is a rectangle, a line segment parallel to a coordinate axis, or a point. For the negative result, we remark that the intersection of two reference objects from S TrAx cannot necessarily be written as a finite union of such objects. Figure 3 contains an example.
⊓ ⊔ Now we have proven all the closure and non-closure results listed in the table of Theorem 3.1.

The extended data model
It is clear that the model for representing spatio-temporal data, that we have presented in Section 2, gives mostly negative closure results (see Theorem 3.1) for the classes of objects we considered important for spatio-temporal practice. The only classes that seem to be useful for further investigation are S, F Rat Aff , for any of the considered classes S of reference objects.
In this section, we will enrich the data model and get better closure results. We will also study normal forms for objects in this enriched model.
In Section 2, we defined a geometric object as a finite union of atomic objects. We could now try to modify this definition by allowing other operations than union in the construction of geometric objects from atomic geometric objects. The exhaustive list of alternative definitions that could be considered are: a geometric object is obtained from atomic geometric objects by means of (a) union (see Section 3); (b) intersection; (c) set-difference; (d) intersection and set-difference; and finally (e) union, intersection and set-difference.
In this paper, we will not investigate alternatives (b), (c) and (d). These alternatives may be interesting from a mathematical point of view, but in any practical application it is natural to allow union in the construction of spatio-temporal objects. In fact it is easy to see that for instance alternative (b) gives even worse closure results. Hereto, we first make two basic observations. Firstly, it is clear that the intersection of convex objects always results in a convex object, and that the affine transformation of a convex object remains a convex object. Secondly, the intersection of connected convex objects is again connected. It should be clear therefore that when the reference objects are triangles or rectangles, then whenever a union has two connected components, it cannot be written as an intersection of atomic geometric objects.
For alternative (c), we remark that in contrast to the intersection, the difference of two convex objects can result in a non-convex object, or in a set of disjoint objects. So, it is possible to describe a wide class of objects as the difference of some atomic objects. But, this approach has two major drawbacks: Only alternative (e) will be further investigated here.

The extended data model
First, we define the extended model. Atomic geometric objects are defined as in Section 2.
Definition 4.1 (Extended data model) An extended geometric object is a binary tree, where each non-leaf node has two children, where each of the nodes is labeled with ∪, ∩ or \ and where each leaf is labeled with an atomic geometric object. The semantics of a geometric object is defined (recursively starting from the root of the tree) as the semantics of its root. If a node n of the binary three has a left child lc and a right child rc, and if the root is labeled θ (with θ ∈ {∪, ∩, \}), the semantics sem(n) of node n is by definition sem(lc) θ sem(rc). The semantics of a leaf labeled with the atomic geometric object O is st(O).

⊓ ⊔
We define the time domain of an extended geometric object to be the convex closure of the union of the time domains of all the composing atomic geometric objects. By slight abuse of notation, we will write down binary trees as in Definition 4.1 in the usual set-theoretic notation. The expression The following property is trivial and says that this model is closed for all Boolean set operations.

Normal forms for CSG
By allowing geometric objects to be constructed from atomic objects via union, intersection and difference, we arrive at a situation that is similar to what is used in the field of "Constructive Solid Geometry" (CSG) [11]. This is a method of geometric modeling, where complex static objects are constructed out of simple objects by taking the union, intersection and difference.
Looking at literature on CSG, we find that there exists a normal form for objects composed as Boolean combinations (with the operators ∪, ∩, \) from atomic objects.
A tree representing a complex object (called a CSG tree) is in normal form when all intersection and subtraction operators have a left subtree which contains no union operators and a right subtree which is simply a primitive (a set of polygons representing a single solid object). All union operators are pushed towards the root, and all intersection and subtraction operators are pushed towards the leaves. In our setting, the primitives are atomic geometric objects and the complexes are geometric objects.
A CSG tree can be converted to normal form by repeatedly applying the following set of rewrite rules (which have the Church-Rosser property) to the tree and then its subtrees: Rule 9) where A, B, and C here can be both primitives or subtrees.

Normal forms for geometric objects
First, we define the notion of normal form for a geometric object in the extended data model.

Definition 4.2 (Normal form)
We say that a geometric object (in the extended version) is in normal form if every ∩or \-labeled node has no ∪-labeled node in the left subtree and has a right child that is labeled by an atomic object. ⊓ ⊔ By Rule 7, differences can be pushed down with respect to intersections and we obtain, in the set-theoretic notation, that a geometric object is in normal form if it is of the form where O i,j is an atomic object.
The rewrite Rules 1-9 can be easily converted to tree notation, as illustrated for Rule 1 in Figure 4. The following property says that any geometric object can be rewritten in normal form. For the proof, we refer to [8].

Conclusion
We have introduced the concept of spatio-temporal object to model events and objects that change in time. We also specified a framework for specifying such objects. For some special classes of spatio-temporal objects of practical relevance, we investigated their closure properties with respect to Boolean set operators. An exhaustive study of these closure properties shows that the chosen approach leads to mostly negative closure results. Therefore, we propose an adaptation to the model. The adapted model has better properties and also is easier to use.
To implement our approach, it is sufficient to be able to represent in a database the following: • spatial objects (a solved problem for many classes of such objects), • temporal objects (again a solved problem), • function objects (lambda terms).
Although to our knowledge none of the currently available DBMS provides the last option, we believe that the object-relational (or object-oriented) technology will soon make it feasible. In fact, one of the earliest object-relational DBMS, Postgres [16], allowed storing functions as tuple components. Also, some object-oriented data models, e.g., OODAPLEX [21], permit functions as first-class objects.
Moreover, storing functions themselves is sometimes not necessary. If the transformation functions are polynomials or rational functions, they can be represented as lists of coefficients. For linear polynomials, such lists are of fixed length, opening the possibility of representing the corresponding spatiotemporal objects using the standard relational data model.
In addition to implementation issues, it would be challenging to develop a type system that captures different dimensions of specialization present in geometric objects: region specialization (polygon, rectangle, ...), transformation specialization (affine mapping, scaling, ...) and time function specialization (rational, polynomial, ...).
Appendix: Technical proofs from Section 3.2 Proof of Lemma 3.2. Let (x 1 , y 1 ), (x 2 , y 2 ) and (x 3 , y 3 ) be the three corner points of the triangle S and let (x i , y i ) be transformed by the affinity g i given by The condition for the existence of a single affine transformation that transforms these corner points according to their respective affinities is that the first matrix in the matrix equation below is regular.
This is the case if and only if the three points (x 1 , y 1 ), (x 2 , y 2 ) and (x 3 , y 3 ) are not collinear. By assumption, this condition is satisfied. We find the affine transformation that transforms the triangle S according to the different movements of the corner points, by solving the above matrix equation.
The result of this computation is the affine transformation with coefficients a(t), b(t), c(t), d(t), e(t), and f (t) that have the following form (to save space time dependence is omitted): Indeed, the transformation matrix is regular. Simplifying the expression a(t)d(t) − b(t)c(t) gives the result x 1 (t)y 2 (t) − x 2 (t)y 1 (t) − x 1 (t)y 3 (t) + x 3 (t)y 1 (t) + x 2 (t)y 3 (t) − x 3 (t)y 2 (t) y 2 x 1 − y 3 x 1 − y 2 x 3 + y 1 x 3 + y 3 x 2 − y 1 x 2 , where x i (t) = a i (t)x i +b i (t)y i +e i (t) and y i (t) = c i (t)x i +d i (t)y i +f i (t), i = 1, 2, 3. This denominator of this expression is zero if and only if the three points (x 1 , y 1 ), (x 2 , y 2 ) and (x 3 , y 3 ) are collinear. By assumption, the points (x 1 , y 1 ), (x 2 , y 2 ) and (x 3 , y 3 ) form a triangle, however. The numerator is non-zero since the points g 1 (x 1 , y 1 ; t), g 2 (x 2 , y 2 ; t) and g 3 (x 3 , y 3 ; t) form a triangle S t at any moment t ∈ I. The coefficients of the resulting affine transformation are linear functions of the coefficients of the original transformations of the corner points (x 1 , y 1 ), (x 2 , y 2 ) and (x 3 , y 3 ). As the original transformations are rational, the resulting affine transformation is rational too.
⊓ ⊔ Proof of Lemma 3.3. Let (x 1 , y 1 ) and (x 2 , y 2 ) be the two end points of the line segment L and let (x i , y i ) be transformed by the affinity g i given by x y + e i (t) f i (t) , i = 1, 2.
We prove that there always exists a rational affine functions a(t), b(t), c(t) and d(t), such that the matrix a(t) b(t) c(t) d(t) transforms the line segment as described in the statement of this lemma (so, the translation components e(t) and f (t) of this affinity are identical zero). The condition for the existence of a single affinity that transforms the two endpoints of the line segment according to their respective affinities is that the first matrix in the following equation is regular.
This is true if the two endpoints of the line segment do not coincide. The affinity that determines the movement of the intersection, can be found by solving the above equation: it is given by As in the case of the previous lemma, it can be shown that

a(t) b(t) c(t) d(t)
is regular and therefore determines an affinity.
This solution is linear in the components of the original rational affine transformations of O 1 and O 1 , so it is also rational.
If the line segments are not parallel to one of the coordinate axes, the intersection point is the following. We only give the x-coordinate s x (t) (the y-coordinate s y (t) is expressed similarly). For clarity time dependence in the coefficients of the affinities is omitted.
We have that s x (t)((a 1