INS 7985
No. of Pages 18, Model 3G
ARTICLE IN PRESS
25 June 2008 Disk Used
Information Sciences xxx (2008) xxx–xxx 1
Contents lists available at ScienceDirect
Information Sciences journal homepage: www.elsevier.com/locate/ins
Modeling and querying fuzzy spatiotemporal databases
3
Aziz Sözer *, Adnan Yazıcı, Halit Og˘uztüzün, Osman Tasß
4
Department of Computer Engineering, Middle East Technical University, 06531 Ankara, Turkey
14 15 16 17 18 19
i n f o
a b s t r a c t
Article history: Received 1 February 2007 Received in revised form 27 May 2008 Accepted 28 May 2008 Available online xxxx
Keywords: Object-oriented database Spatiotemporal data Fuzzy logic Knowledgebase Meteorological database application
Modeling spatiotemporal data, in particular fuzzy and complex spatial objects representing geographic entities and relations, is a topic of great importance in geographic information systems, computer vision, environmental data management systems, etc. Because of complex requirements, it is challenging to represent spatiotemporal data and its features in databases and to effectively query them. This article presents a new approach to model and query the spatiotemporal data of fuzzy spatial and complex objects and/or spatial relations. In our case study, we use a meteorological database application in an intelligent database architecture, which combines an object-oriented database with a knowledgebase for modeling and querying spatiotemporal objects. Ó 2008 Elsevier Inc. All rights reserved.
PR
a r t i c l e
D
2 7 0 8 9 10 11 12 13
TE
5
OO F
2
32
1. Introduction
34
Space and time are inherent notions in spatiotemporal applications, and hence database systems are required to deal with both spatial and temporal phenomena. Spatiotemporal application domains are numerous, e.g. in traffic control and in cadastral, meteorological and environmental information systems. They typically include spatial and temporal attribute variations. One source of such variations is moving objects. For example a moving car in city traffic changes position over time, and its position at a certain time should be estimated. Another source is the changing attributes of objects. An example can be given from physical maps. The borders of a salty lake move back and forth because of seasonal evaporation and rainfall. The green belt around the lake is also affected by these seasonal changes. Combining these two phenomena, some applications include moving objects while changing attributes. Meteorological event monitoring yields many such examples: on a weather map, a stormy area moves while possibly changing its shape. These issues make the task of modeling spatiotemporal information difficult, and advanced data structures and techniques are needed [28]. In modeling spatiotemporal data, two common approaches have been widely used: field-based and object-based modeling [22]. The field-based approach assumes the real world to have attributes which are varying over space as a continuous function. For example, isocontour lines on a map represent points of a constant value (e.g. pressure, temperature, velocity, density) within a volume of space. On the other hand, the object-based approach distinguishes fully definable disjunctive objects. That is, the database for the application stores a map that consists of a collection of identifiable objects, which refer to the partitions and fragments of information space. For example, the temperature regions (e.g. cold, warm, etc.), and the rainy or foggy areas on a weather map are reflected with their unique attributes (e.g. borders, position, direction, etc.) in the database. Uncertainty and fuzziness are also inherent features of most spatiotemporal applications. That is, spatial and temporal information and various relationships in these applications frequently involve uncertainty and fuzziness. For example, in
38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53
RR
37
CO
36
UN
35
EC
33
* Corresponding author. Tel.: +90 312 3110951; fax: +90 312 3115896. E-mail addresses:
[email protected],
[email protected],
[email protected] (A. Sözer). 0020-0255/$ - see front matter Ó 2008 Elsevier Inc. All rights reserved. doi:10.1016/j.ins.2008.05.034
Please cite this article in press as: A. Sözer et al., Modeling and querying fuzzy spatiotemporal databases, Inform. Sci. (2008), doi:10.1016/j.ins.2008.05.034
21 22 23 24 25 26 27 28 29 30
31
INS 7985 25 June 2008 Disk Used 2
55 56 57 58 59 60 61 62 63 64
A. Sözer et al. / Information Sciences xxx (2008) xxx–xxx
describing a windy and wavy region, the region’s boundary is a fuzzy concept. In the case of estimating a moving weather object, the need to determine its position at a certain time, or its time of arrival at a certain location, gives rise to fuzzy estimations. The most common reasons for various types of uncertainties in spatiotemporal applications are as follows: (1) Some spatial information is inherently imprecise or fuzzy. The locations of objects, spatial relationships and various geometric and topological properties usually involve various forms of uncertainty [29]. (2) Most natural phenomena have fuzzy boundaries due to the transitional nature of variation in the phenomenon (e.g. a river’s changing line because of floods and drought) [4,11,24]. (3) To obtain precise data is difficult and unnecessary most of the time, and we may only be able to give a range of values in which the exact numbers would lie. For instance, we may need the number of ‘‘cloudy” or ‘‘partly cloudy” days for some region in a period. In this request, the user specifies cloudiness criteria in linguistic terms instead of giving numeric degrees of cloudiness (e.g. 4/8 or 6/8) [2].
OO F
54
65
74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113
PR
73
D
72
TE
70 71
EC
69
RR
68
There have been several efforts aimed at using fuzzy set theory for modeling spatial objects and their properties [26– 28,30,39]. Schneider [26,27] represents fuzzy spatial objects and relationships as well as complex crisp objects and relationships by using fuzzy techniques. Tang [30] proposes basic fuzzy spatial object types based on a fuzzy topology. A fuzzy cell complex is defined for fuzzy points, lines and regions. Zhan [39] describes how to find the resultant regions from the topological overlay of two simple polygons with indeterminate boundaries. The effect of three typical overlay operations – intersection, difference, and union – on resultant regions is also discussed. Temporality has also been studied by some researchers [23,25,40]. In its simplest form, time is considered as an attribute of spatial objects in [25]. A simple timestamping approach is adequate to obtain the states of objects at certain times. However, to identify individual changes in objects, event-based approaches are developed in [23]. In [40], temporal uncertainty and fuzzy timing are introduced in a model that combines temporality and fuzziness. The main features of this model are that fuzzy timestamping, enabling time, occurrence time and delays are defined. There are also efforts to combine spatial and temporal properties into one modeling framework using an object-oriented modeling approach [12,13,31]. Object-oriented features such as classes and instances, attributes and abstract data types, operations and methods, classification and encapsulation, aggregation, information hiding, inheritance, polymorphism and dynamic binding are very useful for modeling and manipulating spatiotemporal data. Worboys [35] introduced the concept of the spatiotemporal object and defined a spatiotemporal object as a unified object with both spatial and bitemporal extents, also called a simplex. A finite set of such spatiotemporal simplexes are then defined to form a spatiotemporal complex on the basis of which a query algebra is developed. Geo-ER [15], which is an extension of the entity-relationship (ER) model, provides a set of concepts specific to the spatial application domain, and attempts to capture spatial peculiarities at the conceptual level of geographic database design. Yazici et al. [38] used unified modeling language (UML) [1], providing extensions to handle spatial and temporal objects. In their work, some new special entity sets, relationships, and constructs were introduced for modeling spatial objects. Fuzzy object-oriented modeling techniques are used to model and analyze the imperfect information requirements of various complex applications. Gyseghem [14] proposes an object-oriented model that represents uncertainty and fuzzy information. In that work, fuzzy information is presented by fuzzy sets and uncertainty by means of generalized fuzzy sets. Bordogna [3] has defined a graph-based fuzzy object-oriented data model that permits attributes to take linguistic values. The association between an object instance and instance properties are modeled through a fuzzy reference relation. Lee [17] proposes a new approach to object-oriented modeling based on fuzzy logic to formulate fuzzy classes, fuzzy rules to describe the relationship between attributes, the membership function of a fuzzy class based on both static and dynamic properties, and uncertain fuzzy associations between classes. Marin et al. [20] present a set of operators useful to compare objects in a fuzzy setting. Among them is a generalized resemblance degree between two fuzzy sets of imprecise objects and a generalized resemblance degree to compare complex fuzzy objects. Yazici and George [36] have studied a similarity-based fuzzy object-oriented data model in which impreciseness at the data level contributes to uncertainty in the class–object and class–subclass hierarchy. In this paper, we introduce some extensions to that model for spatiotemporal objects. In knowledge intensive applications, support for deduction is an important requirement. In a spatiotemporal application, relations between objects can be very complex. Consider the following, for example: there is a ship crossing the sea and in some parts the sea line may be restricted for travel due to wave and wind conditions. How can we record this information and make the deduction that the sea line is restricted? The spatiotemporal data could be stored in databases but naturally there would be relations including some rules as well. Instead of storing all relations in a database, a knowledgebase that is capable of making deductions and providing knowledge is preferable and very helpful for retrieving the status of the sea line. Hence, the interaction and/or integration of database and knowledgebase technologies is an important requirement for the development of knowledge intensive applications. This is reflected in the continuing research into the development of deductive object-oriented models since the late 1980s [7]. In this study, we present a new approach to model and query real world spatiotemporal objects, in particular meteorological phenomena. We combine our fuzzy object-oriented database model with a knowledgebase to cope with the deduction requirements of the application. The specific contribution of our work comes with a generic modeling of spatiotemporal database applications and a fuzzy spatiotemporal querying mechanism. The generic data model developed in this study is
CO
67
UN
66
No. of Pages 18, Model 3G
ARTICLE IN PRESS
Please cite this article in press as: A. Sözer et al., Modeling and querying fuzzy spatiotemporal databases, Inform. Sci. (2008), doi:10.1016/j.ins.2008.05.034
INS 7985
No. of Pages 18, Model 3G
ARTICLE IN PRESS
25 June 2008 Disk Used
3
A. Sözer et al. / Information Sciences xxx (2008) xxx–xxx
122
2. Background
123
126
In order to support our modeling and querying aspects, spatial and temporal concepts are discussed in this section. The formal definitions required for representing spatiotemporal information are then presented. Specifically, spatiotemporal objects, attributes and operations are defined. The generic model, which supports a meteorological database application, is presented in the next section.
127
2.1. Spatial data types
128
148
In many areas of geographic information systems, natural objects (e.g. mountains, rivers, aridity areas, population distribution areas and meteorological phenomena like foggy regions, wavy sea regions, etc.) and man-made objects (e.g. cadastral divisions, administrative borders of the cities, roads and bridges, etc.) are modeled and queried. The objects are defined with spatial (e.g. geometric shape, location, boundary length, diameter, etc.) and/or descriptive (e.g. name, origin, etc.) attributes [19]. In Fig. 1, the wave heights over the Mediterranean Sea are illustrated on a weather map. According to the map, the wave heights have varying characteristics, which are most dense in south-west of Italy and clear on the Eastern Mediterranean. The borders of the density regions are indeterminate since the characteristics change somewhat gradually. In a geographic space like this map, the objects with imprecise or vague spatial attributes could be referred to as fuzzy spatial objects and the ones with precise or exact attributes (e.g. country borders) could be referred to as crisp spatial objects [26]. We shall first give the definitions for fuzzy spatial objects, which are fuzzy points, lines and regions. A fuzzy point is a point for which an exact position is not known but possible positions are known within a certain area. In Fig. 2a, the expected position of such a point is shown by a black dot and the possible positions are shown by grey dots. For instance, a ship waiting in the queue for crossing ‘‘Istanbul Bosphorus” is found at a certain point but may change its position from time to time (e.g. move to the grey parts). A fuzzy line is a line, the exact shape, position or length of which is not known, but it is known in which area the line must be. In Fig. 2b, the center line shows the normal shape of a river. The actual river line can change position and shape due to floods or droughts (e.g. the grey area). A fuzzy region is a region with indeterminate boundaries. It has three parts: (1) the core (e.g. the dark part) (2) the indeterminate boundary (e.g. grey part) and (3) the exterior (e.g. the outer parts of indeterminate boundary) [39]. In Fig. 2c, a typical fuzzy region is depicted and might be used to express the gradual change over a spatial domain for a given attribute (e.g. wave height). Finally, a complex region is as set of regions, possibly with holes and multiple components (see, Fig. 2d) [26]. Foggy regions with clear patches or cloudy regions with rainy parts, for example, can be represented as complex regions.
149
2.2. Spatial relations between objects
150
Spatial relationships are divided into three: topological (e.g. ‘‘overlap”, ‘‘covers”, etc.), directional (e.g., ‘‘North of”) and metric (e.g. ‘‘5 km away from”) relationships [5].
125
129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147
151
PR
124
D
120
TE
119
EC
118
RR
117
CO
116
UN
115
OO F
121
presented formally using logical specification [32]. In addition, crisp/fuzzy spatial/non-spatial querying, which may require inferencing, is handled by utilizing the intelligent fuzzy object-oriented database (IFOOD) architecture [16]. In the following section, we give some background information on concepts related to fuzzy spatiotemporal database modeling, including spatial and temporal fuzziness as well as relationships between fuzzy and complex objects. In Section 3, we describe how to develop a generic model for spatiotemporal database applications. We use a meteorological database application to illustrate our approach. Section 4 gives details about the architectural design of the system. In Section 5, we present example queries from the application domain, and discuss crucial details of their processing. Finally, we present our conclusions and point to possible future studies, in the last section.
114
Fig. 1. A weather chart showing wave heights on the Mediterranean Sea.
Please cite this article in press as: A. Sözer et al., Modeling and querying fuzzy spatiotemporal databases, Inform. Sci. (2008), doi:10.1016/j.ins.2008.05.034
INS 7985
No. of Pages 18, Model 3G
ARTICLE IN PRESS
25 June 2008 Disk Used 4
A. Sözer et al. / Information Sciences xxx (2008) xxx–xxx
b) Fuzzy line
a) Fuzzy point
c) Fuzzy region
d) Complex region
Fig. 2. Spatial data types.
158
2.3. Fuzzy topological relations
159
The eight binary topological predicates for simple crisp regions are generalized for modeling fuzzy topological relations. A fuzzy region may be simply perceived to have three parts: (1) the core, (2) the indeterminate boundary (3) the exterior [39]. Suppose that ‘‘A” is a set of attributes under consideration, and that a region is a fuzzy subset defined in two dimensional space R2 over ‘‘A”. The membership function of the region can be defined as l:X Y A ? [0, 1], where X and Y are the sets of coordinates defining the region. Each point (x, y) within the region is assigned a membership value for an attribute a in A. A fuzzy region is illustrated in Fig. 3 with the core, the indeterminate boundary, the exterior and a-cut levels. The concept of an a-cut level region is used to approximate the indeterminate boundaries of a fuzzy region and defined as follows:
162 163 164 165
167 168 169 170 171
173 174 175 176 177
PR
161
Ra ¼ fðx; y; aÞjlR ðx; y; aÞ P ag ð0 < a < 1Þ
Next, fuzzy topological relations between fuzzy regions are defined. Fuzzy topological relations are inevitably fuzzy because of the indeterminate boundaries of the regions involved. The degree of the fuzzy relation is measured by aggregating the acut level of fuzzy regions. The basic probability assignment m(Rai), which can be interpreted as the probability that Rai is the true representative of R, is defined as in [9,27,39]:
mðRai Þ ¼ ai aiþ1
It is clear that i¼1 mðRai Þ ¼ 1. Let s(R, S) be the value representing the topological relation between two fuzzy regions R and S, and s(Rai, Saj) be the value representing the topological relation between two a-cut level regions Rai and Saj. Then the general relation between two fuzzy regions can be determined by
179
n X m X i¼1
mðRai ÞmðSaj ÞsðRai ; Saj Þ
j¼1
For example, the overlap relation between two fuzzy regions can be approximated by using the formula above as follows:
sðR; SÞ ¼
n X m X i¼1
j¼1
mðRai ÞmðSaj Þsoverlap ðRai ; Saj Þ
UN
182
for 1 6 i 6 n for some n 2 N with 1 ¼ a1 > a2 > > an > anþ1 ¼ 0
Pn
sðR; SÞ ¼ 180
D
160
TE
156
EC
155
RR
154
CO
153
OO F
157
Topological relations describe spatial intersection or relationships of objects in space. A model for analyzing binary topological relations, known as the 9-intersection model, has been proposed in the literature [10]. The 9-intersection model is based on the intersection between the parts (interior, boundary, exterior) of the regions involved. The intersections of the parts are analyzed with 3 3 matrices (total 29 = 512 matrices). The model distinguishes eight meaningful (disjoint, meet, overlap, equal, contains, inside, covers and covered by) relations for crisp regions. Later, this model was generalized for fuzzy regions [21,30,39] and complex regions [8,27] which are presented in the next sections.
152
Fig. 3. Visualisation of a simple fuzzy region.
Please cite this article in press as: A. Sözer et al., Modeling and querying fuzzy spatiotemporal databases, Inform. Sci. (2008), doi:10.1016/j.ins.2008.05.034
INS 7985
No. of Pages 18, Model 3G
ARTICLE IN PRESS
25 June 2008 Disk Used
5
A. Sözer et al. / Information Sciences xxx (2008) xxx–xxx
184
The remaining topological relations can be analyzed in a similar manner. The overlay of two fuzzy regions is illustrated in Fig. 4.
185
2.4. Topological relations between complex regions
186
A complex region is the union of simple regions (SR) including, possibly, holes. Let Fand G be two simple regions with holes, S S that is F SR ¼ F 0 ni¼1 F i and GSR ¼ G0 m j¼1 Gj , where F0, G0 are bases and Fi, Gj are the holes of F and G, respectively. Then, two regions are disjoint if F0 and G0 are disjoint or one region is inside of another region’s hole. More precisely,
187 188
disjointSR ðF; GÞ ¼ disjointðF 0 ; G0 Þ _ ð91 6 i 6 n : insideðG0 ; F i ÞÞ _ ð91 6 j 6 m : insideðF 0 ; Gj ÞÞ;
190
194 195 196 197 198 199
where
OO F
191
193
insideSR ðF; GÞ ¼ insideðF 0 ; G0 Þ ^ ð81 6 j 6 m : disjointðF 0 ; Gj Þ _ ðinsideðGj ; F 0 Þ ^ 91 6 i 6 n : insideðGj ; F i ÞÞÞ F is considered to be inside G if F0 is inside G0 and if each hole Gj of G is either disjoint from F0 or inside a hole of Fi. Examplary regions with holes and their relations are illustrated in Fig. 5. Other topological predicates for simple regions, possibly with holes, are defined in the same vein. Based on these definitions, topological predicates for complex regions are defined as follows: S S Let F CR ¼ ni¼1 F i and GCR ¼ m j¼1 Gj be two complex regions (CR), where Fi and Gj are simple regions with holes. Then the topological relations are defined as follows:
PR
183
disjoint CR ðF; GÞ () 81 6 i 6 n81 6 j 6 m : disjoint SR ðF i ; Gj Þ
meet CR ðF; GÞ () :disjointCR ðF; GÞ ^ ð81 6 i 6 n81 6 j 6 m : ðdisjointjmeetÞSR ðF i ; Gj ÞÞ insideCR ðF; GÞ () 81 6 i 6 n91 6 j 6 m : insideSR ðF i ; Gj Þ containsCR ðF; GÞ () insideCR ðG; FÞ equalCR ðF; GÞ () n ¼ m ^ 81 6 i 6 n : equalSR ðF i ; Gi Þ
overlapCR ðF; GÞ () :ðdisjointjmeetjinsidejcontainsjequaljcoveredByjcoversÞCR ðF; GÞ
TE
201
D
coversCR ðF; GÞ () coveredByCR ðG; FÞ
2.5. Temporal requirements
203
Temporal aspects have been the focus of attention in the literature, and applications frequently require that these be captured in the database. Information about objects’ attributes and relationships among objects are valid when the object exits
Contains
RR
Disjoint
Inside
Equal
Meet
Covers
Coveredby
Overlap
CO
Fig. 4. Examples of topological relations between fuzzy regions.
UN
204
EC
202
Fig. 5. Examples of the relations (a) disjoint and (b) inside.
Please cite this article in press as: A. Sözer et al., Modeling and querying fuzzy spatiotemporal databases, Inform. Sci. (2008), doi:10.1016/j.ins.2008.05.034
INS 7985 25 June 2008 Disk Used 6 205 206 207 208 209 210 211 212
No. of Pages 18, Model 3G
ARTICLE IN PRESS A. Sözer et al. / Information Sciences xxx (2008) xxx–xxx
temporally. For example, windy regions exist over the sea within a time interval and the ships which have to cross these regions are planned to start and finish their journeys at certain times. The windy regions and the ship routes will be expected to relate to each other in certain ways in this interval. To handle temporal aspects, time is generally stored in databases in two forms: (a) The valid time is the time when the information about an object or relationship holds in the modeled reality. For example the valid times of a ferry route in the Marmara Sea is 08:30, 12:00 and 17:00 daily. (b) The transaction time of a database entry is the time when the entry is part of the current state of the database. The time when the ferry lines’ times are stored in the database is the transaction time of the entry.
213
217
3. A generic model for spatiotemporal querying
218 219
In this section, the components of a generic spatiotemporal model, which are a fuzzy object-oriented database (FOOD) [37] and a fuzzy knowledgebase (FKB) [16] are presented.
220
3.1. The fuzzy object-oriented database (FOOD) model
221
The fuzzy object-oriented model supports multivalued attributes and fuzzy domains are defined for these attributes. The domain of an attribute is the set of all possible values that may be taken. For example, the fuzzy domain for a ‘‘temperature” attribute of a meteorological observation can be defined as
228 229 230 231 232 233 234 235 236
238 239 240 241 242 243 244 245 246
248
PR
D
227
That is, the temperature attribute can have some combination of these values from the domain such as {hot, warm}, {warm}, {cool, cold, moderate}. The similarity matrix in Table 1 shows the similarity of each element with other elements in the domain. The matrix indicates that cool and cold temperatures are similar with a degree of 0.8. In a case where the temperature value is estimated only and given a threshold value of 0.8, multiple values {cool, cold} can be associated, which gives us a fuzzy representation for temperature value. Note that the values of the similarity relations can be defined either by domain experts or computed using various methods existing in the literature [33]. In FOOD, attributes are defined within a range which is a set of allowed values that can be taken. In general, range domain. The range of an attribute ai of a class C is represented by the notation rngc (ai), where ai 2 {a1, a2, . . . , an}, the attributes of class C. For example, the range of the temperature attribute of a class for a ‘‘fog” object can be defined as a subset of the temperature domain:
TE
226
Domaintemperature ¼ fhot; warm; moderate; cool; coldg
rng fog ðtemperatureÞ ¼ fmoderate; cool; coldg
EC
225
RR
223
Another type of fuzziness in FOOD occurs between classes and objects. That is, while some objects are full members of a fuzzy class, some other objects may belong to the class partially. The objects may still be considered as instances of this class but with a degree of membership in [0, 1]. A formal range definition indicating the ideal values for a fuzzy attribute is given in the class definition. However, an attribute of an object can take any value from the related domain. Then, the degree of membership of an object to its class is computed by using the similarities between the attribute values and the class range values, and the relevance of fuzzy attributes. The relevance is given by the weight of the fuzzy attribute in determining the boundary of a fuzzy class. Thus, the degree of membership of an object Oj to a class C is determined by the formula:
lc ðoj Þ ¼
n X i1
CO
222
,
INCðrng c ðai Þ=oj ðaj ÞÞXRLVðai ; CÞ
UN
215
OO F
216
Individual time values are termed chronons. Many temporal aspects have duration, which can be captured by using time intervals, where a time interval [tbegin, tend] is defined as a set of consecutive chronons. We call tbegin and tend the start and the end chronon of the interval, respectively.
214
n X
RLVðai ; CÞ
i¼1
Table 1 The similarity matrix for temperature attribute Temperature hot warm moderate cool cold
hot
warm
moderate
cool
cold
1.0 0.6 0.4 0 0
0.6 1.0 0.8 0.2 0
0.4 0.8 1.0 0.6 0.4
0 0.2 0.6 1.0 0.8
0 0 0.4 0.8 1.0
Please cite this article in press as: A. Sözer et al., Modeling and querying fuzzy spatiotemporal databases, Inform. Sci. (2008), doi:10.1016/j.ins.2008.05.034
INS 7985
No. of Pages 18, Model 3G
ARTICLE IN PRESS
25 June 2008 Disk Used
7
A. Sözer et al. / Information Sciences xxx (2008) xxx–xxx
253
3.2. The generic model
254
In this section, the types, operations and predicates for a generic spatiotemporal model are specified. We use C-logic, which allows direct transformation of the specification into first order formulas [34]. C-logic also allows class and subclass specification independently, which facilitates the update of objects’ subparts. This specification can then be easily implemented in a programming language. In C-logic a class is specified as a collection of atomic properties. For example, a ‘‘Point” is a spatial data type having a membership value to exist at a location (x,y).
256 257 258 259
261 262 263
265 266 267 268
270 271 272 273 274 275 276
Point :¼ ½l ) ½float; x ) ½float; y ) ½float; where 0 6 l 6 1:0:
For example, an object of type Point can be defined as p := Point[l ) 1.0,x ) 3.0, y ) 5.5], which indicates that the point p is located at (3.0, 5.5) with membership value l = 1.0. A more general specification for Point class is given below:
Point :¼ ½l ) fl1 ; . . . ; ln g; x ) fx1 ; . . . ; xn g; y ) fy1 ; . . . ; yn g; where 0 6 l 6 1:0 and ðx; yÞ 2 R2 :
The mapping ) can be understood as either ‘‘containing as a subset”, if a collection of terms follows, or ‘‘containing an element”, if it is followed by a single term. In the former case, terms with the same index are associated with each other. An object is defined as an instance of a class within an interval of time and specified by a predicate is_instance:
PR
255
is instanceðObject; Class; TÞ; where T begin 6 T 6 T end
In a spatiotemporal model, the spatial portions of objects are described with ‘‘Geometry”, ‘‘Point”, ‘‘Line” and ‘‘Region” classes. The ‘‘Point”, ‘‘Line” and ‘‘Region” classes are associated with each other through aggregation relation. For example, a line can be described by an aggregation of points and similarly a region can be represented by an aggregation of lines, and so on. A special form of aggregation is the ‘‘whole/parts” relation between ‘‘Geometry” and part classes, namely, ‘‘Point”, ‘‘Line” and ‘‘Region”. ‘‘Geometry” is formed by the combination of more than one spatial type and expressed in ‘‘Geometry” class definition as follows:
D
251
TE
250
OO F
252
where INC(rngC(aj)/oj(ai)) is the inclusion value that is taking into account the semantics of attributes and RLV(ai, C) is the relevance of attribute ai to the class C, as given in the class definition. All attributes, therefore, affect the membership degrees in proportion to their relevance values. For the details of the FOOD model, including examples of the computation of inclusion values, the reader is referred to [37].
249
Geometry :¼ ½parts ) fPi ; Lj ; Rk g; size ) ½float; MBR ) ½Reg 1 ; center ) ½P1 ; where
EC
T begin 6 T 6 T end ; is instanceðPi ; Point; TÞ; is instanceðLj ; Line; TÞ; is instanceðRk ; Region; TÞ; is instanceðReg 1 ; Region; TÞ; is instanceðP1 ; Point; TÞ and at least one of i; j and k > 0;
278
281 282 283 284
The other attributes of the ‘‘Geometry” class are ‘‘Minimum Bounding Rectangles (MBR)” [6] for locating and accessing objects in space, ‘‘center” for the central position of the object and ‘‘size” for the amount of space that an object covers. The ‘‘ST_Object” class is associated with the ‘‘Geometry” class from which detailed spatial information is extracted, such as geometries and possible holes for regions as well as the position and trajectory of an object. The ‘‘ST_Object” class, having geometric and temporal attributes is defined below. Note that an ‘‘ST_Object” can have at least one simple geometry with possible holes.
ST Object :¼
RR
280
geometry ) fGeoi g; holes ) fHolej g; position ) ½Pos;
CO
279
i; j; k 2 N
trajectory ) fTrajk g; times ) fT begin ; . . . ; T end g
; where
is instanceðT; DateTimeÞ; is instanceðGeoi ; Geometry; TÞ; is instanceðHolej ; Geometry; TÞ; is instanceðPos; Point; TÞ;
287 288 289
291
is instanceðTrajk ; Point; TÞ; T begin 6 T 6 T end ;
i P 1; j P 0; k P 1;
i; j; k 2 N
UN
286
A fuzzy spatial relation describes the relative positions of two fuzzy spatial objects. The degree of relation can be computed by using the definitions in Section 2.3 and the ‘‘Fuzzy Topological Relation algorithm” presented in Fig. 12. A formal definition is given here:
fuzzy spatial relationðST Obj1 ; ST Obj2 ; TÞ 3 2 l ) fl1 ; . . . ; ln g; 7 6 :¼ 4 rel Type ) fdisjoint; meet; inside; equal; contains; covers; coveredBy; overlapg; 5; where T ) fT begin ; . . . ; T end g T begin 6 T 6 T end ; is instanceðST Obj1 ; ST Object; TÞ; is instanceðST Obj2 ; ST Object; TÞ
Please cite this article in press as: A. Sözer et al., Modeling and querying fuzzy spatiotemporal databases, Inform. Sci. (2008), doi:10.1016/j.ins.2008.05.034
INS 7985
No. of Pages 18, Model 3G
ARTICLE IN PRESS
25 June 2008 Disk Used 8
A. Sözer et al. / Information Sciences xxx (2008) xxx–xxx
3.3. The object model
293
In this paper, we consider a meteorological application where the objects/relations are modeled with the extended UML model [38]. The object model presented in Fig. 6 consists of two parts: the first part includes generic spatiotemporal classes that can be used by any specific application domain and the second part consists of meteorological application classes. The spatial part consists of ‘‘Geometry”, ‘‘Point”, ‘‘Line” and ‘‘Region” classes. The classes ‘‘Point”, ‘‘Line” and ‘‘Region” are denoted as part classes and the relationship in between is illustrated by the aggregation constructor (denoted by a diamond symbol). A special form of aggregation (i.e. the ‘‘whole/part” relation) exists between ‘‘Geometry”, the whole, and the part classes, which is indicated by a double diamond symbol. In the whole/part relation the whole is aggregated by different kinds of parts. The l attribute in spatial classes stores a membership value to describe a proximity to a certain fixed space. So, the objects may belong to a class fully (i.e. with a degree of 1) or partially (i.e. with a membership degree between ‘‘0” and ‘‘1”). As an extension to UML, a fuzzy class constructor, indicated by a double-square placed on the upper left-hand side of the spatial class, explicitly represents the fuzzy instances. The other fuzzy constructor, indicated by the tag ‘‘U” to the left-hand side of the name of the class, is used to indicate the existence of class attributes having uncertain values, such as the size of fuzzy geometries. The temporal portion is made up of the ‘‘Time” class, which contains time-related information, including the valid time and transaction time. The temporal dependency of the classes is shown by ‘‘T” on the upper right-hand side of the entities and the spatiotemporal dependency by ‘‘ST”. The type of the time information (e.g. valid or transaction time) and start and end
302 303 304 305 306 307 308 309
PR
300 301
D
299
TE
298
EC
297
RR
296
CO
295
UN
294
OO F
292
Fig. 6. A fuzzy spatiotemporal model.
Please cite this article in press as: A. Sözer et al., Modeling and querying fuzzy spatiotemporal databases, Inform. Sci. (2008), doi:10.1016/j.ins.2008.05.034
INS 7985
No. of Pages 18, Model 3G
ARTICLE IN PRESS
25 June 2008 Disk Used
9
A. Sözer et al. / Information Sciences xxx (2008) xxx–xxx
316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346
OO F
315
/* Fuzzy class includes class–object inclusion methods and is inherited by fuzzy classes */ class Fuzzy: { private: float objMem; // Membership value public: void Ranges(); // Range values are defined void Relevance(); // Relevance values are defined float Membership(); // Get the object membership } class ST_Object:Fuzzy // Spatiotemporal class definition { private: String objectID; // A unique object id to refer the object in DB Public: Set SimpleGeometry(); // A set of unordered geometries Set Holes(); Ref Position(); List Trajectory(); List Times(); }
PR
314
D
313
TE
312
times (e.g. beginDateTime and endDateTime attributes) are the attributes of a temporal entity. UType, for the types of the attributes, represents uncertain types such that data may belong to a domain of valid values, and may be null, incomplete, nonapplicable or expressed with a level of precision. The ‘‘Fuzzy” class provides range definitions, relevance values and class–object membership values for ‘‘ST_Object”. Under the generic model, meteorological application classes (e.g. ‘‘MetObject”, ‘‘Geo_Region”, ‘‘Geo_Line”, ‘‘Measurement”, ‘‘Vehicle” and ‘‘City”) inherit the generic model classes. A ‘‘MetObject”, referring to a meteorological object, contains information on spatial and temporal properties. Meteorological objects are aggregated by numerous ‘‘Measurements” observed by meteorological stations in the cities. A geographic region (‘‘Geo_Region”) is an aggregation of cities and has an orientation such as ‘‘N” or {‘‘S”,”SW”}. The model is completed with other class definitions. A ‘‘Geo_Line” refers to a geographic line object which may be a real one like a river, a railway, or a virtual line like the route of a ferry or a plane. The vehicles which are represented by the ‘‘Vehicle” class, travel between source and destination cities. This modeling approach should satisfy most practical requirements for spatiotemporal applications. For example, the changes of spatial attributes are captured by collecting all the related ‘‘Geometry” and ‘‘Time” objects. The relations between the objects are calculated dynamically. The generic model and the object model using is finalized with example class definitions in C++. We show a few typical class definitions since the other classes can be created similarly.
EC
310 311
RR
347
355
3.4. Coupling the fuzzy database with a fuzzy knowledgebase
356
In order to achieve an intelligent application, a knowledgebase (KB) is integrated to the object-oriented database. We utilize the ‘‘Intelligent Fuzzy Object-Oriented Database” (IFOOD) [16], which provides flexible and powerful querying mechanisms for complex data and knowledge with uncertainty in both database and knowledgebase. The knowledgebase (KB) used in the IFOOD architecture includes rules and intelligent objects having fuzzy attributes. In addition, it features a fuzzy inference method used for deduction of fuzzy conclusions. It gets the rules and facts/objects as input, tries to satisfy rules by comparing them with facts, and produces a conclusion from the satisfied rules. The IFOOD language is an object-oriented database language extended with declarative rules to define predicates. We illustrate this with an example: sea traffic is prohibited in the Istanbul Strait due to conditions of wind, visibility, and waves, etc. In the knowledgebase, the combination of rules and the objects attributes fire the sea lines are prohibited conclusion. The fuzzy rules are defined using linguistic values as follows:
350 351 352 353
357 358 359 360 361 362 363 364 365 366
UN
349
CO
354
The Fuzzy class contains definitions of membership functions for class/objects relations. A fuzzy attribute is defined as a predefined MultiValued which also supports set-valued type. The relevance and range of these fuzzy attributes are defined in related classes and methods such as ‘‘Ranges()”, ‘‘Relevance()” and ‘‘Membership()”. The relations between classes are defined by using special structures in C++. For example, Ref denotes a reference to an instance of class T. Hence, instances of class ‘‘T” can be stored in the database and used to reference database objects. The other one is the Set template that represents a set of elements (unordered and not duplicated) of type T. If the elements are ordered List is used.
348
Please cite this article in press as: A. Sözer et al., Modeling and querying fuzzy spatiotemporal databases, Inform. Sci. (2008), doi:10.1016/j.ins.2008.05.034
INS 7985 25 June 2008 Disk Used 10 367 368 369
No. of Pages 18, Model 3G
ARTICLE IN PRESS A. Sözer et al. / Information Sciences xxx (2008) xxx–xxx
if city.visibility is badsight or underAverage and city.wind is windy or gust then city.sealine is prohibited.
370 371
The rule given below exemplifies the exact syntax of the fuzzy if-then rules utilized in the IFOOD language.
defrule X:Statusð½prohibited; Y; Z; thresholdÞ Geo LineðXÞ; CityðYÞ; 373
Y:visibilityð½badsight; underAverage; thresholdÞ; Y:windð½windy; gust; thresholdÞ;
377
4. The architecture of the spatiotemporal database application
378
397
The architecture of the proposed environment for spatiotemporal data modeling is illustrated in Fig. 7. The FOOD system acts as a database server for data management and the FKB system acts as a knowledge server for knowledge management. Additionally, the fuzzy spatial predicates are determined by the fuzzy spatial processor (FSP). The communication and interaction between the database system, the knowledge base system and the fuzzy spatial processor is performed by the bridge interface (BI). At the higher level, there is a single user interface that provides a unified environment for both data and knowledge management and allows users the capability of query processing independently from the physical structure of the architecture. Fuzzy processors are used to handle uncertainty at both the object-oriented database component and the knowledgebase component of the system. At the user interface level, users are able to define objects and rules having uncertain properties and to query the system with uncertain conditions. The definitions of uncertain types, similarity relations, and membership functions are stored in the object-oriented database. The FKB system processes rules taking fuzzy objects as input. We provide the required facilities in the FKB system to access the definitions in the FOOD system. For example, if the FKB system needs the similarity of two fuzzy terms of a special domain, it gets this value via the fuzzy processor from the FOOD system. The FSP module processess topological predicates between complex spatial objects possibly with holes and fuzzy spatial objects. BI forwards the user request to FKB if the query includes a topological predicate. FSP requests the spatial objects from FOOD and finds the predicates and the degree of membership of the relation. The BI component plays a coordinating role in query processing. It gets user queries, analyzes them, sends requests to the database and/or to the knowledge base, retrieves the results, and sends them up to the user interface. The algorithm, with implementation steps, is as shown in Fig. 8.
398
5. Query processing with examples
386 387 388 389 390 391 392 393 394 395 396
399 400 401
PR
385
D
384
TE
383
EC
382
The following procedures are applied to resolve the query according to its type:
RR
380 381
The basic query (crisp and non-spatial): This type of query asks for crisp data that does not have a spatial dimension. The BI sends the parsed query expression directly to OODB. The objects that meet the query condition are sent back to the BI.
CO
379
UN
375
OO F
376
where o.a(v, [thresholdrng(a)]) is an object term, where o is an object ID, a is an object attribute, v is an attribute value, and thresholdrng(a) is the threshold level defined for the attribute a. For more details of the IFOOD inference engine and language the reader is referred to [16].
374
Fig. 7. The architecture of the spatiotemporal database application.
Please cite this article in press as: A. Sözer et al., Modeling and querying fuzzy spatiotemporal databases, Inform. Sci. (2008), doi:10.1016/j.ins.2008.05.034
INS 7985
No. of Pages 18, Model 3G
ARTICLE IN PRESS
25 June 2008 Disk Used
11
A. Sözer et al. / Information Sciences xxx (2008) xxx–xxx
EC
TE
D
PR
OO F
Query Evaluation Algorithm: Input: Query supplied by the user Output: Retrieved objects Get and Parse(query); if query is nonspatial-query then if query is crisp-query then Send-to-OODB(crisp-query); else Send-to-OODB(fuzzy-query); end if if query includes knowledge-base predicate(s) then Transfer-to-knowledge-base(satisfying-objects); Start-inference-engine-evaluation; Return(result); end if Get(satisfying-objects); else Send-to-OODB(spatial-query); if query includes knowledge-base predicate(s)(rule) then Transfer-to-knowledge-base(satisfying-objects); Transfer-to-FSP(satisfying-objects); Apply fuzzy spatial and/or complex spatial algorithm; Start-inference-engine-evaluation; Return(result); else Transfer-to-FSP(satisfying-objects); Apply fuzzy spatial algorithm in Figure 10 and/or complex spatial algorithm in Figure 12; end if end if Submit-to-user(selected satisfying-objects); Fig. 8. Query evaluation algorithm.
404 405 406 407 408 409 410 411
The fuzzy non-spatial query: This type of query asks for data that is fuzzy but non-spatial and the BI, FKB, and OODB components are employed. The objects retrieved by the BI are sent to the FKB component to check whether they meet the fuzzy conditions. How these objects are checked is illustrated in Example 1. Objects satisfying the conditions are sent back to the BI. The complex spatial query: Complex spatial objects and their relationships are queried in this type of query. The BI, OODB and the FSP components are employed to fetch query results. The user asks for the objects that have topological relations (described in Sections 2.2 and 2.4) with the objects under inquiry. Example 2 illustrates this type of query. The fuzzy spatiotemporal query: In this type query, the user asks for the objects that meet the conditions of the predefined rules within a specified time interval. The rules can be evaluated by an examination of topological relations between fuzzy regions and fuzzy objects. The fuzzy spatiotemporal queries are illustrated in Examples 3–5.
RR
403
CO
402
413 414
UN
412
Example 1 (Fuzzy non-spatial query). The objects used in the example are listed in Table 2, and the similarity relation of ‘‘cloud” is included in Tables 2 and 3. The similarity relation of ‘‘temperature” is already presented in Section 3.1.
Table 2 Sample records in database ID
Object type
Name
Temperature
Cloud
Visibility
DateTime
C1 C2 C3
City City City
Istanbul Edirne Izmit
Cool Moderate Cold
Cloudy Partly cloudy Cloudy, closed
Bad sight Under average Average
01.01.2008 01.01.2008 01.01.2008
Please cite this article in press as: A. Sözer et al., Modeling and querying fuzzy spatiotemporal databases, Inform. Sci. (2008), doi:10.1016/j.ins.2008.05.034
INS 7985
No. of Pages 18, Model 3G
ARTICLE IN PRESS
25 June 2008 Disk Used 12
A. Sözer et al. / Information Sciences xxx (2008) xxx–xxx
Table 3 Similarity matrix of cloud attribute Clear
Partly cloudy
Cloudy
Closed
Clear Partly cloudy Cloudy Closed
1.0 0.6 0 0
0.6 1.0 0.6 0.4
0 0.6 1.0 0.8
0 0.4 0.8 1.0
PR
OO F
Cloud
Fig. 9. Maximum temperature regions (left) and meteorological events (right) for 01, January 2008.
Query: Retrieve the cool and partly cloudy cities on 01.01.2008. This query is formulated as follows:
415 416
select X.cityname from city(X) where X.temperature([cool], 0.6) and X.cloud([cloudy],0.8), X.validtime(01.01.2008).
418 419
TE
D
417
420 421
The query is evaluated as follows:
422
(i) The first predicate to evaluate in this query is X.temperature([cold],0.6). C1.temperature is cool, and lSimilarity(cool,cool) = 1.0. Therefore, C1 satisfies the temperature predicate. C2.temperature is moderate, and lSimilarity(cool,moderate) = 0.6. Therefore C2 satisfies it. C3.temperature is cold, and lSimilarity(cool,cold) = 0.8. Therefore C3 satisfies it.
EC
423 424 425 426
(ii) Then, the predicate X.cloud([cloudy],0.8) is evaluated. C1.cloud is cloudy, and lS Similarity(cloudy, cloudy) = 1.0. Therefore C1 satisfies the cloud predicate. C2.cloud is partly cloudy, and lSimilarity(cloudy, partly cloudy) = 0.6. Therefore C2 does not satisfy it. C3.cloud is cloudy or closed with max{lSimilarity(cloudy, cloudy),lSimilarity(cloudy, closed)} = max{1.0, 0.8} = 1.0. Therefore C3 satisfies it.
427
RR
428 429 430 431 432
(iii) As a result, the objects C1 and C3 satisfy the fuzzy query conditions.
CO
433
434
436 437 438 439 440 441 442 443 444
Example 2 (Complex spatial query). Fig. 9 shows the maximum temperature regions (on the left) and the meteorological events (on the right) as mapped by the Turkish Meteorological Office for 01, January 2008. Q2 The temperature regions are shown in different colors (e.g. cold parts by dark blue1, cool parts by green, moderate parts by orange and warm parts by red). Temperature regions are visualised as complex spatial objects since they have multiple components possibly with holes. The expected meteorological events are depicted with symbols and colors, e.g. rain (green drops), snow (blue stars), grey clouds, black foggy areas and yellow patchy areas. We assume the spatial objects representing temperature regions and meteorological objects in Fig. 9 are inserted in the database as shown in Table 4. The temperature regions, which are classified by their degrees (e.g. cool, cold, etc.), have different geometries (e.g. Geo1, Geo2, etc.). According to the figure, Cold (dark blue) region has one simple region (Geo1) and a hole (Hole1). The cool regions (green) have four simple regions forming Geo2, and none of them has a hole.
UN
435
Query: Retrieve the cold and foggy regions on 01, January 2008.
445
1
For interpretation of color in Fig. 9, the reader is referred to the web version of this article.
Please cite this article in press as: A. Sözer et al., Modeling and querying fuzzy spatiotemporal databases, Inform. Sci. (2008), doi:10.1016/j.ins.2008.05.034
INS 7985
No. of Pages 18, Model 3G
ARTICLE IN PRESS
25 June 2008 Disk Used
13
A. Sözer et al. / Information Sciences xxx (2008) xxx–xxx Table 4 Objects in the FOOD Object
ObjType
Degree
Geometries
Holes
Valid time
MetObject MetObject MetObject MetObject MetObject
Temperature Fog Snow Rain Cloud
{cold, cool, moderate, warm} {foggy} {heavy, rainy} {shower} {cloudy, partly cloudy}
{Geo1, Geo2, Geo3, Geo4} {Geo5} {Geo6, Geo7} {Geo8} {Geo9, Geo10}
{Hole1, Null, Null, Null} {Null} {Null, Null} {Null} {Null, Null}
01.01.2008 01.01.2008 01.01.2008 01.01.2008 01.01.2008
Complex Topological Relation algorithm:
OO F
Input: Simple regions of two complex regions
Output: Sequence of topological predicates that hold between each pair of simple regions
1. for each simple region of complex regions(F,G) F0 ← {Base geometry of F} G0 ← {Base geometry of G}
if spatial_relation(F0,G0) = “disjoint” then
simple topological relation(STR) ← ”disjoint”; else for i ← 1 to n //For each hole of F if spatial_relation(G0,Fi) = “inside” then
PR
S ← ∅ //S is a set of Simple topological relations
D
simple topological relation(STR) ← ”disjoint”; end if
TE
end for
for j ← 1 to m //For each hole of G
if spatial_relation(F0,Gj ) = “inside” then
end for end if
EC
simple topological relation(STR) ← ”disjoint”; end if
RR
// If not disjoint do related calculations for other topological predicates S ← S ∪ {STR}; end for
2. for each STR in S
CO
if all STR are pairwise disjoint then
complex topological relation(CTR) ← ”Disjoint”;
end if
// If not disjoint do similar calculations for other complex topological predicates
UN
CTR ← {Disjoint | Meet | Inside | Equal | Covers | Coveredby | Contains | Overlap}
end for
Fig. 10. Complex topological predicate evaluation algorithm.
446
This query is formulated as follows:
447
select spatial_relation(X.geometry,Y.geometry) from MetObject(X), MetObject(Y) where X.ObjType([temperature]) and Y.ObjType([fog]) and X.degree([cold],0.8) and Y.degree([foggy],0.8) and X.validtime(01.01.08) and Y.validtime(01.01.08);
448 449 450
Please cite this article in press as: A. Sözer et al., Modeling and querying fuzzy spatiotemporal databases, Inform. Sci. (2008), doi:10.1016/j.ins.2008.05.034
INS 7985
No. of Pages 18, Model 3G
ARTICLE IN PRESS
25 June 2008 Disk Used 14
A. Sözer et al. / Information Sciences xxx (2008) xxx–xxx
451
454 455 456 457 458 459 460 461 462 463 464 465 466 467 468
In this query, the temperature objects having the attribute value cold, and the fog objects having the foggy degree are fetched from FOOD to BI. The user supplies a threshold value 0.8 for temperature degree, so ‘‘cool” regions are also fetched since lS([cold], [cold]) = 1.0 and lS([cold], [cool]) = 0.8). The simple topological relation algorithm is applied for components with holes of complex regions. After finding simple topological predicates, the complex topological relation algorithm is applied to determine the final topological predicate. Note that we show only the ‘‘disjoint” case in the algorithm in Fig. 10 since it occupies a great deal of space and the other cases are handled similarly, as explained in Section 2.4. Example 3 (Fuzzy spatiotemporal query). In this example, fuzzy spatial relations are queried. In Fig. 11, wave height and wind speed for ‘‘Marmara Sea” are illustrated at 31.12.2007 15:00 Greenwich Mean Time (GMT) (between 40.0–41.4 North latitudes and 26–30 East longitudes). Both meteorological events are represented as fuzzy spatial objects, in which the central parts have the highest waves and strongest winds while the coastal areas have lower waves and calmer wind conditions. The three lines, namely, Line1, Line2 and Line3 represent ferry routes between the ports.
OO F
453
Query: Retrieve the sea lines restricted for transportation due to wind and wave conditions on 31st, December 2007. This query is formulated as follows: select X from Geo_line(X), MetObject(Y), MetObject(Z) where X.LineType([SeaLine]) and Y.ObjType([Wave]) and Z.ObjType([Wind]) and X.status([restricted], Y, Z, threshold), X.validtime (31.12.2007).
PR
452
469 470 471
In the query, the sea lines restricted for transportation are requested. In this case, X.status([restricted],Y,Z,threshold) is a rule defined in the FKB as follows:
defrule X:Statusð½restricted; Y; Z; thresholdÞ Geo LineðXÞ; MetObjectðY Þ; MetObjectðZÞ;
478 479 480 481 482 483 484 485 486 487 488
D
TE
477
EC
476
The threshold value supplied by the user gives a limit for the restriction of the sealine. Required objects (sea wind and wave height geometries) are fetched from the OODB, and FSP calculates the fuzzy spatial relation (overlap in this case) between the fuzzy regions wind and wave, and crisp ferry lines using the fuzzy topological relation algorithm in Fig. 12: According to the meteorological forecast, the sea area is divided into fivea-cut levels and the ferry lines overlap some of them (see Fig. 11); the calculation details are presented in Tables 5 and 6. The results of the fuzzy spatial relation calculations are supplied to FKB for inferencing. In FKB, a rule may be composed of more than one condition. Each condition in a rule may have its own matching degree. Therefore, we compute an overall matching degree. Here, we use the ‘‘min” operator for combining the degree of matching of conjunction (AND) conditions and the ‘‘max” operator for combining the degree of matching of disjunction (OR) conditions [29]. For example, considering the rule given for ‘‘restricted sealine” above, each term is matched with a matching degree, as shown in Tables 5 and 6, and the overall matching degree is calculated as in Table 7. According to the overall restriction degrees in the third column, given the threshold value 0.7, ‘‘Line1” and ‘‘Line2” will be restricted. Example 4 (Nested rule query). Due to the restrictions in the transportation lines, the vehicles’ trips are ‘‘cancelled” or ‘‘delayed”. Following Example 3, we find the ‘‘delayed” vehicles for the same date.
RR
475
Query: Retrieve delayed ferries on 31st, December 2007.
CO
474
overlapðX:geometry; Y:geometry; thresholdÞ; overlapðX:geometry; Z:geometry; thresholdÞ;
UN
473
Fig. 11. Wave height and wind speed over Marmara Sea.
Please cite this article in press as: A. Sözer et al., Modeling and querying fuzzy spatiotemporal databases, Inform. Sci. (2008), doi:10.1016/j.ins.2008.05.034
INS 7985
No. of Pages 18, Model 3G
ARTICLE IN PRESS
25 June 2008 Disk Used
15
A. Sözer et al. / Information Sciences xxx (2008) xxx–xxx
Fuzzy Topological Relation algorithm (region vs line): Input: Two fuzzy object geometries Output: The overlap degree of two objects 1. FuzzyRelation ← 0 2. for each α − cut level region Rα i – R α i+1 if the line overlaps with Rα i – R α i+1 then end if end for 3. Return FuzzyRelation Fig. 12. Fuzzy topological predicate evaluation algorithm.
PR
Table 5 Computing a fuzzy topological relation for a wavy region and ferry lines
OO F
FuzzyRelation ← FuzzyRelation + m(regionα i ) × m(lineα j )
soverlap
m(regionai) m(line1aj)
soverlap
m(regionai) m(line2aj)
soverlap
m(regionai) m(line3aj)
1.0–0.75 0.75–0.50 0.50–0.30 0.30–0.0 soverlap(R, L)
1 1 1 1
0.25 0.25 0.20 0.30 1.0
0 1 1 1
0.00 0.25 0.20 0.30 0.75
0 0 0 1
0.00 0.00 0.00 0.30 0.30
TE
Table 6 Computing a fuzzy topological relation for a windy region and ferry lines
D
a-cut levels of wavy region
soverlap
m(regionai) m(line1aj)
soverlap
m(regionai) m(line2aj)
soverlap
m(regionai) m(line3aj)
1.0–0.65 0.65–0.30 0.30–0.20 0.20–0.0 soverlap(R, L)
1 1 1 0
0.35 0.35 0.10 0.00 0.80
1 1 1 1
0.35 0.35 0.10 0.20 1.00
0 0 1 1
0.00 0.00 0.10 0.20 0.30
Degree of overlap of lines with wavy region
Degree of overlap of lines with windy region
loverall = Min(overlapwavy, overlapwindy)
1.00 0.75 0.30
0.80 1.00 0.30
0.80 0.75 0.30
CO
Line 1 Line 2 Line 3
RR
Table 7 The overall fuzzy relation degrees
EC
a-cut levelsof windy region
This query is formulated as follows:
490
select X from Vehicle(X), MetObject(Y), MetObject(Z), Geo_Line(L) where X.Type([Ferry]) and X.GetLine()=L and X.status([delayed],Y,Z,L,threshold) and X.validtime (31.12.2007).
491 492 493 494
UN
489
The rule is defined in FKB as follows:
defrule X:Statusð½delayed; Y; Z; L; thresholdÞ VehicleðXÞ; MetObjectðYÞ; MetObjectðZÞ; Geo LineðLÞ; 496
L:Statusð½restricted; Y; Z; thresholdÞ;
497
This rule is a nested rule as it fires another rule (Y.status[restricted],threshold), as described in Example 3.
498
Example 5 (Fuzzy spatiotemporal query). In Fig. 13, the meteorological objects for an interval are presented. According to the figures the rainy areas (green drops) move to the east while decreasing in effective size. On the other hand the cloudy areas move to the west while increasing in effective size.
499 500
Please cite this article in press as: A. Sözer et al., Modeling and querying fuzzy spatiotemporal databases, Inform. Sci. (2008), doi:10.1016/j.ins.2008.05.034
INS 7985
No. of Pages 18, Model 3G
ARTICLE IN PRESS
25 June 2008 Disk Used 16
OO F
A. Sözer et al. / Information Sciences xxx (2008) xxx–xxx
Fig. 13. Meteorological events for the interval 01.01.2008 and 02.01.2008.
505 506 507
Center X ¼
li yi ; where 0 < li 6 1 and
i¼1
n X
li ¼ 1 and li ¼ Areai =Total area
i¼1
The approximated center points for the complex object (e.g. at coordinates of (91, 77) and (228, 103)) are used to calculate the directional change and the speed of the object. The summation of the areas of each part show the change (growth or decrease) in the object’s effect area.
Fuzzy Spatiotemporal Query algorithm: Input: A pair of geometries for a time interval Output: Area, direction and speed change 1. for each chronon for each object in the chronon TotalArea ← 0
EC
512
li xi
for each component of the object’s geometry TotalArea ← TotalArea + component’s area (CA) end for
object center ( X , Y ) ← (0,0 )
CO
510 511
i¼1 n X
for each component of the object’s geometry Get the minimum bounding rectangle(MBR) Get the center (x,y) of the MBR Object center ( X , Y ) ← ( X + x ∗ CA / TotalArea, Y )+ y ∗ CA / TotalArea
end for
UN
509
Center Y ¼
n X
PR
504
D
503
Query: Retrieve the area, direction and speed changes of meteorologic events in terms of position and effect area between 01.01.2008 and 02.01.2008. In the query, the directional, positional and areal changes of the objects are queried and the algorithm in Fig. 14 is applied. In order to illustrate how the algorithm works, the rain object’s spatial attribute changes are shown in Fig. 15. This complex object is made of three parts on the first day (on the left) and four parts on the second day (on the right). The MBRs, central points for each part and the areas are depicted in the figure. A central point for the whole object on both days is calculated, using a weighted average considering the proportional area of each part:
TE
502
RR
501
end for end for
2. for each pair of center points Calculate distance and speed Calculate the directional change end for 3. Calculate area change Fig. 14. The algorithm to evaluate area, speed and direction change.
Please cite this article in press as: A. Sözer et al., Modeling and querying fuzzy spatiotemporal databases, Inform. Sci. (2008), doi:10.1016/j.ins.2008.05.034
INS 7985
No. of Pages 18, Model 3G
ARTICLE IN PRESS
25 June 2008 Disk Used
17
OO F
A. Sözer et al. / Information Sciences xxx (2008) xxx–xxx
Fig. 15. Rain object movement for 01.01.2008 (a) and 02.01.2008 (b).
513
6. Conclusions
514
526
In this study, we have introduced a generic spatiotemporal data model and a querying mechanism for spatiotemporal databases. We presented our method, designed to handle uncertainty in spatiotemporal database applications. We used an application, involving meteorological objects with some spatial and temporal attributes, as an example. The proposed mechanism has been implemented as a proof-of-concept prototype. In the scope of this work, meteorological phenomena and geographic data are modeled as spatiotemporal objects. These objects can move and evolve in time. In addition, the meteorological and geographic man made objects may have spatial relations. The crucial decision was to integrate the model with a fuzzy knowledgebase allowing a fuzzy deduction and querying capability to handle complex data and knowledge. As a result, we are able to handle spatiotemporal queries (position, spatial properties and spatial relationships). Spatiotemporal data modeling and querying require further research. The model and the method presented in this paper should be applied to other fields, such as wireless sensor networks and multimedia, to gain more insight into fuzzy spatiotemporal modeling and querying. Another future research topic is the development of efficient indexing mechanisms for fuzzy spatiotemporal databases.
527
7. Uncited reference
PR
515 516 517 518 519 520 521
524 525
528
Q1
EC
523
TE
D
522
[18]. References
530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559
[1] G. Booch, J. Rumbaugh, I. Jacobson, The Unified Modeling Language User Guide Reading, Addison-Wesley, MA, 1999. [2] G. Bordogna, S. Chiesa, D. Geneletti, Linguistic modelling of imperfect spatial information as a basis for simplifying spatial analysis, Information Sciences 176 (2006) 366–389. [3] G. Bordogna, A. Leporati, D. Lucarella, G. Pasi, The Fuzzy Object Oriented Database, Recent Issues on Fuzzy Databases, Springer-Verlag, 2000. [4] T. Cheng, M. Molenaar, H. Lin, Formalizing fuzzy objects from uncertain classification results, International Journal of Geographical Information Science 15 (1) (2001) 27–42. [5] C. Claramunt, M. Theriault, Fuzzy semantics for direction relations between composite regions, Information Sciences 160 (2004) 73–90. [6] M.A. Cobb, F.E. Petry, Modeling spatial relationships within a fuzzy framework, Journal of the American Society For Information Science 49 (3) (1998) 253–266. [7] R.M. Colomb, Deductive Databases and Their Applications, Taylor & Francis, 1998. [8] S. Du, Q. Qin, Q. Wang, H. Ma, Evaluating structural and topological consistency of complex regions with broad boundaries in multi-resolution spatial databases, Information Sciences 178 (2008) 52–68. [9] D. Dubois, M.C. Jaulent, A general approach to parameter evaluation in fuzzy digital pictures, Pattern Recognition Letters (1987) 251–259. [10] M. Egenhofer, E. Clementini, P. Felice, Topological relations between regions with holes, International Journal of Geographical Information Systems 8 (2) (1994) 129–144. [11] P. Fisher, C. Arnot, R. Wadsworth, J.J. Wellens, Detecting change in vague interpretations of landscapes, Ecological Informatics 1 (2006) 163– 178. [12] A. Frihida, D.J. Marceau, M. Theriault, Spatiotemporal object-oriented data model for disaggregate travel behavior, Transactions in GIS 6 (3) (2002) 277–294. [13] T. Griffiths, A. Fernandes, N. Paton, R. Barr, The TRIPOD spatio-temporal data model, Data and Knowledge Engineering 49 (1) (2003) 23–65. [14] N.V. Gyseghem, R.D. Caluwe, Imprecision and uncertainty in the UFO database model, Journal of the American Society for Information Science 49 (3) (1999) 236–252. [15] T. Hadzilacos, N. Tryfona, An extended entity-relationship model for geographic applications, SIGMOD Record 26 (3) (1997). [16] M. Koyuncu, A. Yazici, IFOOD: an intelligent fuzzy object-oriented database architecture, IEEE Transactionson Knowledge and Data Engineering (2003) 1137–1154. [17] J. Lee, N.L. Xue, K.H. Hsu, S.J. Yang, Modeling imprecise requirements with fuzzy objects, Information Sciences 118 (1999) 101–119. [18] M. Liu, Deductive database languages: problems and solutions, ACM Computing Surveys 31 (1) (1999) 27–62. [19] C.T. Lu, Y. Kou, J. Zhao, L. Chen, Detecting and tracking regional outliers in meteorological data, Information Sciences 177 (2007) 1609–1632. [20] N. Marin, J.M. Medina, O. Pons, M.A. Vila, Object resemblance in a fuzzy object-oriented context, in: Proceedings of 2002 IEEE International Conference on Fuzzy Systems, Honolulu (EEUU), 2002.
UN
CO
RR
529
Please cite this article in press as: A. Sözer et al., Modeling and querying fuzzy spatiotemporal databases, Inform. Sci. (2008), doi:10.1016/j.ins.2008.05.034
INS 7985 25 June 2008 Disk Used 18
A. Sözer et al. / Information Sciences xxx (2008) xxx–xxx
OO F
[21] A. Pauly, M. Schneider, Topological predicates between vague spatial objects, in: Ninth Int. Symp. on Spatial and Temporal Databases (SSDT), Lecture Notes in Computer Science (LNCS), Springer, 2005, pp. 418–432. [22] N. Pelekis, B. Theodoulidis, I. Kopanakis, Y. Theodoridis, Literature review of spatio-temporal database models, The Knowledge Engineering Review 19 (3) (2004) 235–274. [23] D. Peuquet, Making space for time: issues in space–time data representation, GeoInformatica 5 (1) (2001) 11–32. [24] B. Plewe, The nature of uncertainty in historical geographic information, Transaction in GIS (2002) 431–456. [25] A. Renolen, Temporal Maps and Temporal Geographical Information Systems (Review of Research), Department of Surveying and Mapping, The Norwegian Institute of Technology, 1997. [26] M. Schneider, Uncertainty management for spatial data in databases: fuzzy spatial data types, in: Sixth Int. Symp. on Advances in Spatial Databases, LNCS, vol. 1651, Springer-Verlag, 1999, pp. 330–351. [27] M. Schneider, A design of topological predicates for complex crisp and fuzzy regions, in: 20th International Conference on Conceptual Modeling, Yokohama, Japan, November 27–30, 2001. [28] S. Shekhar, S. Chawla, S. Ravada, A. Fetterer, L. Yuan, L. Chang-Tien, Spatial databases – accomplishments and research needs, IEEE Transactions on Knowledge and Data Engineering 11 (1) (1999) 45–55. [29] J.G. Stell, Part and complement: fundamental concepts in spatial relations, Annals of Artificial Intelligence and Mathematics 41 (2004) 1–18. [30] X. Tang, Y. Fang, W. Kainz, Fuzzy topological relations between fuzzy spatial objects, in: FSKD 2006, LNAI, vol. 4223, Springer-Verlag, 2006, pp. 324– 333. [31] N. Tryfona, S.J. Jensen, Using abstractions for spatio-temporal conceptual modeling, in: Proceedings of ACM SAC, Como, Italy, 2000. [32] C. Vidal, A. Rodriguez, A logical approach for modeling spatio-temporal objects and events, LNCS, vol. 3770, Springer-Verlag, 2005, pp. 218–227. [33] T. Warren, L.Z. Zhang, C. Mount, Similarity measures for retrieval in case-based resoning systems, Applied Artificial Intelligence 12 (4) (1998) 267–288. [34] C. Weidong, D. Warren, C-logic of complex objects, in: ACM SIGACTSIGMOD-SIGART Symp. Principles of Database Systems, 1989, pp. 369–378. [35] M.F. Worboys, A unified model for spatial and temporal information, The Computer Journal 37 (1) (1994). [36] A. Yazici, R. George, Fuzzy Database Modeling, Physica-Verlag, Heidelberg/New York, 1998. [37] A. Yazici, R. George, D. Aksoy, Design and implementation issues in the fuzzy object-oriented data (FOOD) model, Information Sciences 108 (4) (1998) 241–260. [38] A. Yazici, Q. Zhu, N. Sun, Semantic data modeling of spatiotemporal database applications, International Journal of Intelligent Systems 16 (2001) 881– 904. [39] F.B. Zhan, H. Lin, Overlay of two simple polygons with indeterminate boundaries, Transactions in GIS 7 (1) (2003) 67–81. [40] Y. Zhou, T. Murata, Petri net model with fuzzy timing and fuzzy-metric temporal logic, International Journal of Intelligent Systems 14 (8) (1999) 719– 745.
PR
560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589
No. of Pages 18, Model 3G
ARTICLE IN PRESS
UN
CO
RR
EC
TE
D
590
Please cite this article in press as: A. Sözer et al., Modeling and querying fuzzy spatiotemporal databases, Inform. Sci. (2008), doi:10.1016/j.ins.2008.05.034
