168
Paola Podest` a, Barbara Catania, and Alberto Belussi
In the following, we consider three distinct maps M 1 , M 2 , and M 3 , sketched in
Fig. 8.4. They represent roads (identified by R i ), towns (identified by T i ), and pollution areas (identified by PA i ). Roads, towns, and pollution areas have dimensions
(2,2,2) in map M 1 , (1,2,2), in map M 2 , and (1,0,2) in map M 3 .
8.3.2 Similarity-based Processing Scenario
Suppose a user wants to query some spatial data available on the Web, without having a detailed knowledge about such data. When the users specify the query, they
may not know the resolution of the underlying database, therefore they may not be
able to specify the query in an exact way as spatial predicates could change when
changing object dimensions. As a consequence, the quality of the result obtained
may be reduced because interesting pairs may not be returned.
As an example, suppose the user wants to know which roads enter town T 1 (see
Fig. 8.4), this query can be specified as follows:
Q 1 = {r|r is a road, r Overlap T 1 }.
If roads and towns are represented as regions, as in map M 1 , predicate Overlap
is defined and can be executed (see Sect. 8.4 for details). However, if roads are represented as lines and towns as regions, as in map M 2 , predicate Overlap is not defined.
In this context, a similarity-based approach could be very useful. The user could
specify the query by: (i) assuming data have the maximal dimension, that is all feature types have dimension 2 (in order to made available to the user the largest set of
topological predicates); (ii) providing a threshold value. Such value can be used to
increase the quality of the generated result, for example, to return more information,
even if not necessarily significant, to the user.
In general, suppose the user wants to execute query Q 1 up to an error t . Actually,
this error depends on the user’s application and needs. The basic idea is to rewrite
each topological relation θ in Q 1 into one or more topological relations with distance
at most t from θ, say θ 1 ,. . .,θ n , by considering the possible dimension change of the
features involved in θ in the map where the query has to be executed. As a consequence, Q 1 is rewritten into a sequence of new queries Q
1
1 ,. . .,Q
m
1 , one for each map
over which Q 1 has to be executed.
To apply the previous processing, a distance function d t defined over pairs of
topological relationships, possibly defined over different pairs of object dimensions,
is needed. With this function at hand, assuming that M i is the map over which query
Q 1 has to be executed, d 3 is the dimension of roads and d 4 is the dimension of towns
in M i , query Q 1 can be rewritten as follows:
Q
i
1 = {r|r is a road, ∃θ
(d t (Overlap, (R, R), θ
, (d 3 , d 4 )) ≤ t ∧ r θ
T 1 )}.
In the previous query specification, d t (Overlap, (R, R), θ
, (d 3 , d 4 )) denotes the
distance between relation Overlap defined over dimensions (R, R) and relation θ
defined over dimensions (d 3 , d 4 ). In order to apply the previous processing, in Sects.
8.4 and 8.5 we present two distance functions, one for topological relations (d t ) and
one for cardinal relations (d c ), taking into account feature dimensions.
Paola Podest` a, Barbara Catania, and Alberto Belussi
In the following, we consider three distinct maps M 1 , M 2 , and M 3 , sketched in
Fig. 8.4. They represent roads (identified by R i ), towns (identified by T i ), and pollution areas (identified by PA i ). Roads, towns, and pollution areas have dimensions
(2,2,2) in map M 1 , (1,2,2), in map M 2 , and (1,0,2) in map M 3 .
8.3.2 Similarity-based Processing Scenario
Suppose a user wants to query some spatial data available on the Web, without having a detailed knowledge about such data. When the users specify the query, they
may not know the resolution of the underlying database, therefore they may not be
able to specify the query in an exact way as spatial predicates could change when
changing object dimensions. As a consequence, the quality of the result obtained
may be reduced because interesting pairs may not be returned.
As an example, suppose the user wants to know which roads enter town T 1 (see
Fig. 8.4), this query can be specified as follows:
Q 1 = {r|r is a road, r Overlap T 1 }.
If roads and towns are represented as regions, as in map M 1 , predicate Overlap
is defined and can be executed (see Sect. 8.4 for details). However, if roads are represented as lines and towns as regions, as in map M 2 , predicate Overlap is not defined.
In this context, a similarity-based approach could be very useful. The user could
specify the query by: (i) assuming data have the maximal dimension, that is all feature types have dimension 2 (in order to made available to the user the largest set of
topological predicates); (ii) providing a threshold value. Such value can be used to
increase the quality of the generated result, for example, to return more information,
even if not necessarily significant, to the user.
In general, suppose the user wants to execute query Q 1 up to an error t . Actually,
this error depends on the user’s application and needs. The basic idea is to rewrite
each topological relation θ in Q 1 into one or more topological relations with distance
at most t from θ, say θ 1 ,. . .,θ n , by considering the possible dimension change of the
features involved in θ in the map where the query has to be executed. As a consequence, Q 1 is rewritten into a sequence of new queries Q
1
1 ,. . .,Q
m
1 , one for each map
over which Q 1 has to be executed.
To apply the previous processing, a distance function d t defined over pairs of
topological relationships, possibly defined over different pairs of object dimensions,
is needed. With this function at hand, assuming that M i is the map over which query
Q 1 has to be executed, d 3 is the dimension of roads and d 4 is the dimension of towns
in M i , query Q 1 can be rewritten as follows:
Q
i
1 = {r|r is a road, ∃θ
(d t (Overlap, (R, R), θ
, (d 3 , d 4 )) ≤ t ∧ r θ
T 1 )}.
In the previous query specification, d t (Overlap, (R, R), θ
, (d 3 , d 4 )) denotes the
distance between relation Overlap defined over dimensions (R, R) and relation θ
defined over dimensions (d 3 , d 4 ). In order to apply the previous processing, in Sects.
8.4 and 8.5 we present two distance functions, one for topological relations (d t ) and
one for cardinal relations (d c ), taking into account feature dimensions.