Fuzzy topological predicates, their properties, and their integration into query languages.
For a long time topological relationships between spatial objects have been a main focus of research on spatial data handling and reasoning. They have especially been integrated into query languages of spatial database systems and geographical information systems. One of their fundamental features is that they operate on spatial objects with precisely defined, sharp boundaries. But in many geometric and geographic applications there is a need to model spatial phenomena and their topological relationships rather through vague or fuzzy concepts due to indeterminate boundaries. This paper presents a model of fuzzy regions and focuses on the definition of topological predicates between them. Moreover, some properties of these predicates are shown, and we demonstrate how the predicates can be integrated into a query language.
INTRODUCTION
Representing, storing, quering, and manipulating spatial information
is important for many non-standard database applications.
Specialized systems like geographical information systems (GIS),
spatial database systems, and image database systems to some extent
provide the needed technology to support these applications.
For these systems the development of formal models for spatial objects
and for topological relationships between these objects is a
topic of great importance and interest, since these models exert a
great influence on the efficiency of spatial systems and on the expressiveness
of spatial query languages.
In the past, a number of data models and query languages for
spatial objects with precisely defined boundaries, so-called crisp
spatial objects, have been proposed with the aim of formulating
and processing spatial queries in databases (e.g., [8, 9]). Spatial
data types (see [9] for a survey) like point, line, or region are the
central concept of these approaches. They provide fundamental abstractions
for modeling the structure of geometric entities, their re-
lationships, properties, and operations. Topological predicates [6]
Permission to make digital or hard copies of all or part of this work for
personal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, to
republish, to post on servers or to redistribute to lists, requires prior specific
permission and/or a fee.
between crisp objects have been studied intensively in disciplines
like spatial analysis, spatial reasoning, and artificial intelligence.
Increasingly, researchers are beginning to realize that the current
mapping of spatial phenomena of the real world to exclusively crisp
spatial objects is an insufficient abstraction process for many spatial
applications and that the feature of spatial vagueness is inherent to
many geographic data [3]. Moreover, there is a general consensus
that applications based on this kind of indeterminate spatial data are
not covered by current information systems. In this paper we focus
on a special kind of spatial vagueness called spatial fuzziness.
Fuzziness captures the property of many spatial objects in reality
which do not have sharp boundaries or whose boundaries cannot
be precisely determined. Examples are natural, social, or cultural
phenomena like land features with continuously changing properties
(such as population density, soil quality, vegetation, pollution,
temperature, air pressure), oceans, deserts, English speaking areas,
or mountains and valleys. The transition between a valley and a
mountain usually cannot be exactly ascertained so that the two spatial
objects "valley" and "mountain" cannot be precisely separated
and defined in a crisp way. We will designate this kind of entities
as fuzzy spatial objects. In the GIS community, a number of models
based on fuzzy sets (e.g., [1, 5, 13, 14]) have been proposed,
but these are not suitable for an integration into a database system,
because they do not provide data types for fuzzy spatial data. The
author himself has started to work on this topic and to design a system
of fuzzy spatial data types including operations and predicates
[10, 11] that can be embedded into a DBMS.
The goal of this paper is to give a definition of topological predicates
on fuzzy regions, which is currently an open problem, and
to discuss some properties of these predicates. Besides, we show
the integration of these predicates into a query language. Section 2
presents a formal model of very generally defined crisp regions and
sketches the design of a well known collection of topological predicates
on crisp regions. In Section 3 we employ the concept of a
crisp region for a definition of fuzzy regions. Fuzzy regions are described
as collections of so-called crisp a-level regions. In practice,
this enables us to transfer the whole formal framework and later all
the well known implementation methods available for crisp regions
to fuzzy regions. In Section 4 we present an approach for designing
topological predicates between fuzzy regions that is based on fuzzy
set theory. Section 5 discusses some properties of these predicates,
and Section 6 deals with their integration into a query language.
Finally, Section 7 draws some conclusions.
2. CRISP REGIONS AND TOPOLOGICAL
PREDICATES
Our definition of crisp regions is based on point set theory
and point set topology [7]. Regions are embedded into the two-
Figure

1: Example of a (complex) region object.
dimensional Euclidean space IR 2 and are thus point sets. Unfortu-
nately, the use of pure point set theory for their definition causes
problems. If regions are modeled as arbitrary point sets, they can
suffer from undesired geometric anomalies. These degeneracies relate
to isolated or dangling line and point features as well as missing
lines and points in the form of cuts and punctures. A process called
regularization avoids these anomalies.
We assume that the reader is familiar with some needed, well-known
concepts of point set topology like topological space, open
set, closed set, interior, closure, exterior, and boundary. The concept
of regularity defines a point set S as regular closed if
We define a regularization function reg c which associates a set S
with its corresponding regular closed set as reg c (S) := S ffi . The
effect of the interior operation is to eliminate dangling points, dangling
lines, and boundary parts. The effect of the closure operation
is to eliminate cuts and punctures by appropriately supplementing
points and to add the boundary. We are now already able to give a
general definition of a type for complex crisp regions:
is bounded and regular closedg
In fact, this very "structureless" and implicit definition models (com-
plex) crisp regions possibly consisting of several components and
possibly having holes (Figure 1). As a special case, a simple region
is a region that does not have holes and does not consist of multiple
components.
An important approach to designing topological predicates on
simple crisp regions rests on the well-known 9-intersection model
[6] from which a complete collection of mutually exclusive topological
relationships can be derived. The model is based on the
nine possible intersections of boundary (-A), interior
of a spatial object A with the corresponding components
of another object B. Each intersection is tested with regard to
the topologically invariant criteria of emptiness and non-emptiness.
different configurations are possible from which only a
certain subset makes sense depending on the combination of spatial
objects just considered. For two simple regions eight meaningful
configurations have been identified which lead to the eight
predicates of the set T cr = fdisjoint, meet, overlap, equal, inside,
contains, covers, coveredByg. Each predicate is associated with a
unique combination of nine intersections so that all predicates are
mutually exclusive and complete with regard to the topologically
invariant criteria of emptiness and non-emptiness. We explain the
meaning of these predicates only informally here. Two crisp regions
A and B are disjoint if their point sets are disjoint. They meet
if their boundaries share points and their interiors are disjoint. They
are equal if both their boundaries and their interiors coincide. A is
contains A is a proper subset of B and if their
boundaries do not touch. A is covered by B (B covers A is a
proper subset of B and if their boundaries touch. Otherwise, A and
overlap. Generalizations to topological predicates for complex
crisp regions leading to the same (clustered) collection T cr of predicates
have been given in [12, 2]. We will base our definition of
topological predicates for fuzzy regions on these topological predicates
for complex crisp regions.
3. MODELING FUZZY REGIONS
A "structureless" definition of fuzzy regions in the sense that
only "flat" point sets are considered and no structural information
is revealed has been given in [10]. For our purposes we deploy a
"semantically richer" characterization and approximation of fuzzy
regions and define them in terms of special, nested a-cuts. A fuzzy
region -
F is described as a collection of crisp a-level regions 1 [10],
F , which is the level set of
F , and where
F a
We call F a an a-level region. Clearly, F a is a complex crisp region
whose boundary is defined by all points with membership value a i .
In particular, F a i can have holes. The kernel of -
F is then equal
to F 1:0 . An essential property of the a-level regions of a fuzzy
region is that they are nested, i.e., if we select membership values
We here describe the finite, discrete case. If L -
F is infinite, then
there are obviously infinitely many a-level regions which can only
be finitely represented within this view if we make a finite selection
of a-values. In the discrete case, if jL -
if we take
all these occurring membership values of a fuzzy region, we can
even replace "'" by "ae" in the inclusion relationships above. This
follows from the fact that for any p 2F a \Gamma F a
F (p) =a i . For the continuous case, we get -
As a result, we obtain:
A fuzzy region is a (possibly infinite) set of a-level re-
gions, i.e., -
F jg with a i ? a
F a ' F a
4. TOPOLOGICAL PREDICATES ON
FUZZY REGIONS
In this section we introduce a concept of topological predicates
for fuzzy regions. To clarify the nature of a fuzzy (topological)
predicate, we can draw an analogy between the transition of a crisp
set to a fuzzy set and the transition of a crisp predicate to a fuzzy
predicate. In a similar way as we can generalize the characteristic
function f0;1g to the membership function -
[0; 1], we can generalize a (binary) predicate
a (binary) fuzzy predicate
Hence, the value of
a fuzzy predicate expresses the degree to which the predicate holds
for its operand objects. In case of topological predicates, in this
paper the sets X and Y are both equal to the type region, and the set
f0;1g is equal to the type bool. The sets -
Y are both equal to
the type fregion for fuzzy regions, and for the set [0; 1] we need a
type fbool for fuzzy booleans.
For the definition of fuzzy topological predicates, we take the
view of a fuzzy region as a collection of a-level regions (Section 3),
which are complex crisp regions (Section 2), and assume the set T cr
of topological predicates on these regions. This preparatory work
now enables us to reduce topological predicates on fuzzy regions
to topological predicates on collections of crisp regions.
The approach presented in this section is generic in the sense
that any meaningful collection of topological predicates on crisp
regions could be the basis for our definition of a collection of topological
predicates on fuzzy regions. If the former collection additionally
fulfils the properties of completeness and mutual exclusion
Other structured characterizations given in [10] describe fuzzy regions
as multi-component objects, as three-part crisp regions, and
as a-partitions.
(which is the case for T cr ), the latter collection automatically inherits
these properties.
The open question now is how to compute the topological relationships
of two collections of a-level regions, each collection
describing a fuzzy region. We use the concept of basic probability
assignment [4] for this purpose. A basic probability assignment
m(F a i ) can be associated with each a-level region F a and can be
interpreted as the probability that F a i is the "true" representative of
F . It is defined as
m is built from the differences of successive a i 's. It is easy to see
that the telescoping sum - n
be the value that represents a (binary) property p f
between two fuzzy regions F and G. For reasons of simplicity,
we assume that L -
G =: L. Otherwise, it is not difficult to
F and L -
G by forming their union L := L -
G
and by reordering and renumbering all a-levels. Based on the work
in [4] property p f of F and G can be determined as the summation
of weighted predicates by
cr
cr yields the value of the corresponding property
cr for two crisp a-level regions F a i and Ga j . This formula
is equivalent to
cr
If p f is a topological predicate of T
equal between two fuzzy
regions, we can compute the degree of the corresponding relationship
with the aid of the pertaining crisp topological predicate p cr 2
cr . The value of p cr Once
this value has been determined for all combinations of a-level regions
from F and G, the aggregated value of the topological predicate
can be computed as shown above. The more fine-grained
the level set L for the fuzzy regions F and G is, the more
precisely the fuzziness of topological predicates can be determined.
It remains to show that 0 - p f really
a fuzzy predicate. Since a
since p cr holds. We
can show the other inequality by determining an upper bound for
cr
cr
(since
Hence,
An alternative definition of fuzzy topological predicates, which
pursues a similar strategy like the one discussed so far, is based
on the topological predicates p srh on simple regions with holes
(but without multiple components). If F a is an a-level region, let
us denote its connected components by F a Similarly,
we denote the connected components of an a-level region Ga j by
Ga . We can then define a topological predicate p 0
f as
f
It is obvious that p 0
holds since all factors have a value
greater than or equal to 0. We can also show that p 0
the following transformations:
f
Hence,
holds. As a rule, the predicates p f and p 0
f do
not yield the same results. Assume that F a i and Ga fulfil a predicate
cr . This fact contributes once to the summation process
for p f . But it does not take into account that possibly several
faces F a ik (at least one) of F a i satisfy the corresponding predicate
least one) of Ga . This fact
contributes several times (at most f i \Delta to the summation process
for
f . Hence, the evaluation process for p 0
f is more fine-grained
than for p f .
Both generic predicate definitions reveal their quantitative
character. If the predicate p cr and the predicate
respectively, is never fulfilled, the predicate
respectively, yields false. The more a-level
regions of F and G (simple regions with holes of F a and Ga j ) fulfil
the predicate p cr the more the validity
of the predicate p f (p 0
increases. The maximum is reached if all
topological predicates are satisfied.
5. PROPERTIES
An interesting issue relates to the effect of the number of a-level
regions on the computation results for p f (F;G). What can we expect
if we supplement L with an additional membership value? Can
we make a general statement saying that the value for
then always increase or decrease or stagnate? To answer this ques-
tion, let p n
f denote the predicate p f (F;G) if for its computation
contains n labels except for a We now extend L
by an additional label a rearranging
the indices of the membership values. Without loss of generality
we assume an l 2 ng such that
a enables us to compute the difference
f (F;G) and to investigate whether this difference
is always greater than, less than, or equal to 0. The computation
is simplified by the observation that all addends (a
a cr
f
f
neutralize each other. That is, for p n+1
disjoint cr disjoint cr cr cr
overlap cr cr
contains cr contains cr covers cr cr

Table

1: Evaluation of the predicate comparisons of the first class.
we have only to consider those addends having factors with an index
equal to k. For p n
f we have only to consider addends
having factors with
we obtain:
(p cr cr
cr
cr
(p cr cr
(p cr cr
(p cr cr
cr
(p cr cr
The first line computes the sum of all addends having the factor
a l \Gamma a k . The fourth line does the same for all addends having the
factor a k \Gamma a l+1 . Unfortunately, these sums include addends having
the factor a l \Gamma a l+1 so that these addends have to be subtracted
(second and fifth line). The third, sixth, and seventh line insert
the correct addends. The eighth line subtracts all those addends of
having the factor a l \Gamma a l+1 . The whole expression can be
restructured as follows:
(p cr cr
(p cr cr
(p cr cr
cr
(p cr cr
cr
\Theta n
cr cr
cr cr
cr cr
cr cr
cr cr
cr cr

For a comparison of D with 0 we can observe that the values
of the factors a k \Gamma a l+1 , a
a l+1 are all greater than 0. Hence, the result only depends
on the predicate values. Analyzing the six differences of predi-
cates, we can group them into two classes. The first class contains
the differences p cr cr cr
cr cr cr
structure is p cr . The second class
contains the remaining differences p cr cr
cr cr cr cr
Their common structure is p cr

Table

1 shows the result of comparing the predicates involved
in the differences of the first class. For each predicate combination
cr we first set p cr (F;G) and then
cr both to 1 (true) and 0 (false) (written in bold font). Afterwards
we determine the result of the respective other predicates
and thus obtain four pairs of values. For instance, if disjoint cr
is equal to 0, disjoint cr either equal to 0 or to 1 (in-
dicated by the expression "0 j 1"). Next, we assign the correct
comparison operator =, -, or - reflecting the relationship
of a pair of values to each of the four cases. In the end, we
form the combination of the four comparison operators and obtain
the relationship between p cr (F;G) and p cr G). The symbol
Q indicates that the equality or inequality of the two predicates
cannot be generally decided. The only solution here is to compute
it for each single case. We have omitted the comparisons
for inside and coveredBy, since they are inverse to contains and
covers, respectively. That is, inside cr
coveredBy cr cr
For an investigation of the second class we do not have to consider
the predicates disjoint cr , meet cr , overlap cr , and equal cr ; they
are symmetric in their arguments, that is, p cr cr (G;F).
We also need not consider the predicates covers cr and coveredBy cr ,
since already their predicate combinations in the first class cannot
be decided generally. Thus, only the predicates contains cr and the
inverse inside cr remain. For contains cr we obtain Table 2.
contains cr contains cr

Table

2: Evaluation of the contains comparison of the second
class.
In summary, we obtain a rather negative result. Since the differences
for meet cr , overlap cr , equal cr , covers cr , and coveredBy cr cannot
be decided in general, no general statement can be made about
the difference between p n+1
f
cates. The computation of this difference also fails for contains cr
and inside cr . The problem is that the behavior of both predicates
in the first and second class is opposite to each other. That is, in
the first class contains cr contains cr and in the
second class contains cr contains cr hold. For the
computation of D these two differences are added, and we cannot
generally decide whether the result is less than, greater than, or
equal to 0. Hence, all these predicates do not satisfy some kind of
"monotonicity criterion". A positive exception is only the predicate
disjoint cr for which we obtain disjoint n+1
6. QUERYING WITH FUZZY TOPOLOGICAL
PREDICATES
In this section we demonstrate how fuzzy topological predicates
can be integrated into an SQL-like spatial query language. The fact
that the membership degree yielded by a fuzzy topological predicate
is a computationally determined quantification between 0 and
1, i.e., a fuzzy boolean, impedes a direct integration. First, it is not
very comfortable and user-friendly to use such a numeric value in
a query. Second, spatial selections and spatial joins expect crisp
predicates as filter conditions and are not able to cope with fuzzy
predicates.
As a solution, we propose to embed adequate qualitative linguistic
descriptions of nuances of topological relationships as appropriate
interpretations of the membership values into a spatial
query language. For instance, depending on the membership value
yielded by the predicate inside f , we could distinguish between not
inside, a little bit inside, somewhat inside, slightly inside, quite in-
side, mostly inside, nearly completely inside, and completely inside.
These fuzzy linguistic terms can then be incorporated into spatial
queries together with the fuzzy predicates they modify. We call
these terms fuzzy quantifiers, because their semantics lies between
the universal quantifier for all and the existential quantifier there
exists. It is conceivable that a fuzzy quantifier is either predefined
and anchored in the query language, or user-defined.
We know that a fuzzy topological predicate p f is defined as
fregion \Theta fregion ! [0; 1]. The idea is now to represent each fuzzy
quantifier g 2G= fnot, a little bit, somewhat, slightly, quite, mostly,
nearly completely, completelyg by an appropriate fuzzy set with a
let gp f be a quantified fuzzy predicate (like somewhat inside with
somewhat and Then we can define:
That is, only for those values of p f (F;G) for which - g yields 1, the
predicate gp f is true. A membership function that fulfils this quite
strict condition is, for instance, the crisp partition of [0; 1] into jGj
disjoint or adjacent intervals completely covering [0; 1] and the assignment
of each interval to a fuzzy quantifier. If an interval [a; b]
is assigned to a fuzzy quantifier g, the intended meaning is that
otherwise. For exam-
ple, we could select the intervals [0:0;0:02] for not, [0:02;0:05] for
a little bit, [0:05;0:2] for somewhat, [0:2;0:5] for slightly, [0:5;0:8]
for quite, [0:8;0:95] for mostly, [0:95;0:98] for nearly completely,
and [0:98;1:00] for completely.
Alternative membership functions are shown by the fuzzy sets
in

Figure

2. While we can always find a fitting fuzzy quantifier
for the partition due to the complete coverage of the interval [0; 1],
this is not necessarily the case here. Each fuzzy quantifier is associated
with a fuzzy number having a trapezoidal-shaped membership
function. The transition between two consecutive fuzzy
quantifiers is smooth and here modeled by linear functions. Within
a fuzzy transition area - g yields a value less than 1 which makes
the predicate gp f false. Examples in Figure 2 can be found at 0:2,
0:5, or 0:8. Each fuzzy number associated with a fuzzy quantifier
can be represented as a quadruple (a;b;c;d) where the membership
function starts at (a;0), linearly increases up to (b;1), remains
constant up to (c;1), and linearly decreases up to (d;0). Figure 2
assigns (0:0;0:0;0:0;0:02) to not, (0:01;0:02;0;03;0:08) to a little
bit, (0:03;0:08;0:15;0:25) to somewhat, (0:15;0:25;0:45;0:55)
to slightly, (0:45;0:55;0:75;0:85) to quite, (0:75;0:85;0:92;0:96)
to mostly, (0:92;0:96;0:97;0:99) to nearly completely, and
(0:97;1:0;1:0;1:0) to completely.
So far, the predicate gp f is only true if - g yields 1. We can relax
this strict condition by defining:
In a crisp spatial database system this gives us the chance also to
take the transition zones into account and to let them make the predicate
evaluating a fuzzy spatial selection or join in
a fuzzy spatial database system, we can even set up a weighted
ranking of database objects satisfying the predicate gp f at all and
being ordered by descending membership degree 1 - g ? 0.
A special, optional fuzzy quantifier, denoted by at all, represents
the existential quantifier and checks whether a predicate p f can be
fulfilled to any extent. An example query is: "Do regions A and B
(at all) overlap?" With this quantifier we can determine whether
The following few example queries demonstrate how fuzzy spatial
data types and quantified fuzzy topological predicates can be
integrated into an SQL-like spatial query language. It is not our objective
to give a full description of a specific language. We assume
a relational data model where tables may contain fuzzy regions as
attribute values.
What we need first is a mechanism to declare user-defined fuzzy
quantifiers and to activate predefined or user-defined fuzzy quanti-
fiers. This mechanism should allow to specify trapezoidal-shaped
and triangular-shaped membership functions as well as crisp parti-
tions. In general, this means to define a classification, which could
be expressed in the following way:
create classification fq
(not (0:00;0:00;0:00;0:02);
a little bit (0:01;0:02;0;03;0:08);
somewhat (0:03;0:08;0:15;0:25);
slightly (0:15;0:25;0:45;0:55);
quite (0:45;0:55;0:75;0:85);
mostly (0:75;0:85;0:92;0:96);
nearly completely (0:92;0:96;0:97;0:99);
completely (0:97;1:0;1:0;1:0))
slightly quite mostly
somewhat
a little bit
not
completely
nearly completely
Figure

2: Membership functions for fuzzy quantifiers.
Such a classification could then be activated by
set classification fq
Assuming that we have a relation pollution, which stores among
other things the blurred geometry of polluted zones as fuzzy re-
gions, and a relation areas, which keeps information about the use
of land areas and which stores their vague spatial extent as fuzzy
regions. A query could be to find out all inhabited areas where people
are rather endangered by pollution. This can be formulated in
an SQL-like style as (we here use infix notation for the predicates):
select areas.name
from pollution, areas
inhabited and
pollution.region quite overlaps areas.region
This query and the following two ones represent fuzzy spatial joins.
Another query could ask for those inhabited areas lying almost
entirely in polluted areas:
select areas.name
from pollution, areas
inhabited and
areas.region nearly completely inside
pollution.region
Assume that we are given living spaces of different animal species
in a relation animals and that their vague extent is represented as a
fuzzy region. Then we can search for pairs of species which share
a common living space to some degree:
select A.name, B.name
from animals A, animals B
where A.region at all overlaps B.region
As a last example, we can ask for animals that usually live on land
and seldom enter the water or for species that never leave their land
area (the built-in aggregation function sum is applied to a set of
fuzzy regions and aggregates this set by repeated application of
fuzzy geometric union):
select name
from animals
where (select sum(region) from areas)
nearly completely covers or
completely covers region
7. CONCLUSIONS
We have presented a definition of topological predicates on fuzzy
regions. We have shown that all these predicates with one exception
do not fulfil some kind of "monotonicity criterion" which
documents the independence of topological and metric properties.
Moreover, we have sketched the integration of these predicates into
fuzzy spatial query languages. For that purpose, fuzzy quantifiers
are used that can be incorporated into spatial queries.
8.



--R

Fuzzy Set Theoretic Approaches for Handling Imprecision in Spatial Analysis.
Topological Relationships of Complex Points and Complex Regions.
Geographic Objects with Indeterminate Boundaries.
A General Approach to Parameter Evaluation in Fuzzy Digital Pictures.
Qualitative Spatial Reasoning: A Semi-Quantitative Approach Using Fuzzy Logic
A Topological Data Model for Spatial Databases.
Point Set Topology.
An Introduction to Spatial Database Systems.
Spatial Data Types for Database Systems - Finite Resolution Geometry for Geographic Information Systems
Uncertainty Management for Spatial Data in Databases: Fuzzy Spatial Data Types.
Finite Resolution Crisp and Fuzzy Spatial Objects.
A Design of Topological Predicates for Complex Crisp and Fuzzy Regions.
Incorporating Fuzzy Logic Methodologies into GIS Operations.

--TR
A general approach to parameter evaluation in fuzzy digital pictures
A topological data model for spatial databases
Qualitative spatial reasoning: a semi-quantitative approach using fuzzy logic
An introduction to spatial database systems
Uncertainty Management for Spatial Data in Databases
A Design of Topological Predicates for Complex Crisp and Fuzzy Regions
Topological Relationships of Complex Points and Complex Regions
fuzzy region;fuzzy spatial query language