8 Using Qualitative Information in Query Proc. over Multiresolution Maps
181
8.7.1 Similarity-based Processing
Suppose the user wants to know which roads enter town T 1 and specifies the query:
Q 1 = {r|r is a road, r Overlap T 1 }.
Moreover, suppose the user decides to tolerate an error t = 25% in the result.
If the dimension of towns and roads in the map where the query has to be executed are d 3 and d 4 , the query processor can use the topology distance introduced in
Sect. 8.4 to rewrite the topological predicate Overlap into a set of topological predicates {θ 1 , ..., θ n } ⊆ T REL(d 3 , d 4 ) such that d t (Overlap, (R, R), θ i , (d 3 , d 4 )) ≤ 0.25, i =
1, ..., n. Considering maps M 1 and M 2 in Fig. 8.4, according to Fig. 8.5 we have that:
• Map M 1 : d t (Overlap, (R, R), θ, (R, R)) ≤ 0.25, θ ∈ {Overlap}.
• Map M 2 : d t (Overlap, (R, R), θ, (R, L)) ≤ 0.25, θ ∈ {Cross, T ouch, Cover}.
Thus, depending on the map where the query is executed, query Q 1 is rewritten
as follows:
• Map M 1 : Q
1
1 = {r|r is a road, r Overlap T 1 } (and therefore, roads R 1 , R 2 , R 5 are
returned).
• Map M 2 : Q
2
1 = {r|r is a road, r θ T 1 , θ ∈ {Cross, T ouch, Cover}} (and therefore,
roads R 1 , R 2 , R 3 , R 5 , R 6 are returned).
Notice that, without the use of a threshold value, no result would have been returned from map M 2 .
Similarly, suppose the user wants to know which towns are NorthWest of T 1 .
This query can be specified as follows: Q 2 = {t|t is a town, t NW T 1 }. We notice
that, differently from query Q 1 , single-tile relations are always defined, whatever the
dimension of the reference and target objects are. Suppose, however, the user wants
to execute the query Q 2 up to an error c = 6%. If the dimension of towns in the map
where the query has to be executed is d 3 , the query processor can use the cardinal
distance introduced in Sect. 8.5 to rewrite the cardinal predicate NW into a set of
cardinal predicates {ϕ 1 , ..., ϕ n } ⊆ CREL(d 3 , R) such that d c (NW, (R, R), ϕ i , (d 3 , R)) ≤
0.06, i = 1, ..., n.
Considering maps M 1 and M 2 in Fig. 8.4, as towns are represented as regions in
both maps, according to Fig. 8.8 we have that: d c (NW, (R, R), ϕ,
(R, R)) ≤ 0.06 for ϕ ∈ {NW, N, W, NW:N, NW:W, W:NW:N}. Thus, query Q 2 is
rewritten, by relaxing predicate NW by considering the zones around the NW tile,
as follows:
Q
1
2 = Q
2
2 = {t|t is a town, t ϕ T 1 , ϕ ∈ {NW, N, W, NW:N, NW:W, W:NW:N}}.
From map M 1 , towns T 2 and T 3 are returned. From map M 2 , towns T 2 and T 4 are
returned. Notice that, also in this second case, without the use of a threshold value
the query result would have been unsatisfactory for the user, as only T 2 from map
M 2 would have been returned.
181
8.7.1 Similarity-based Processing
Suppose the user wants to know which roads enter town T 1 and specifies the query:
Q 1 = {r|r is a road, r Overlap T 1 }.
Moreover, suppose the user decides to tolerate an error t = 25% in the result.
If the dimension of towns and roads in the map where the query has to be executed are d 3 and d 4 , the query processor can use the topology distance introduced in
Sect. 8.4 to rewrite the topological predicate Overlap into a set of topological predicates {θ 1 , ..., θ n } ⊆ T REL(d 3 , d 4 ) such that d t (Overlap, (R, R), θ i , (d 3 , d 4 )) ≤ 0.25, i =
1, ..., n. Considering maps M 1 and M 2 in Fig. 8.4, according to Fig. 8.5 we have that:
• Map M 1 : d t (Overlap, (R, R), θ, (R, R)) ≤ 0.25, θ ∈ {Overlap}.
• Map M 2 : d t (Overlap, (R, R), θ, (R, L)) ≤ 0.25, θ ∈ {Cross, T ouch, Cover}.
Thus, depending on the map where the query is executed, query Q 1 is rewritten
as follows:
• Map M 1 : Q
1
1 = {r|r is a road, r Overlap T 1 } (and therefore, roads R 1 , R 2 , R 5 are
returned).
• Map M 2 : Q
2
1 = {r|r is a road, r θ T 1 , θ ∈ {Cross, T ouch, Cover}} (and therefore,
roads R 1 , R 2 , R 3 , R 5 , R 6 are returned).
Notice that, without the use of a threshold value, no result would have been returned from map M 2 .
Similarly, suppose the user wants to know which towns are NorthWest of T 1 .
This query can be specified as follows: Q 2 = {t|t is a town, t NW T 1 }. We notice
that, differently from query Q 1 , single-tile relations are always defined, whatever the
dimension of the reference and target objects are. Suppose, however, the user wants
to execute the query Q 2 up to an error c = 6%. If the dimension of towns in the map
where the query has to be executed is d 3 , the query processor can use the cardinal
distance introduced in Sect. 8.5 to rewrite the cardinal predicate NW into a set of
cardinal predicates {ϕ 1 , ..., ϕ n } ⊆ CREL(d 3 , R) such that d c (NW, (R, R), ϕ i , (d 3 , R)) ≤
0.06, i = 1, ..., n.
Considering maps M 1 and M 2 in Fig. 8.4, as towns are represented as regions in
both maps, according to Fig. 8.8 we have that: d c (NW, (R, R), ϕ,
(R, R)) ≤ 0.06 for ϕ ∈ {NW, N, W, NW:N, NW:W, W:NW:N}. Thus, query Q 2 is
rewritten, by relaxing predicate NW by considering the zones around the NW tile,
as follows:
Q
1
2 = Q
2
2 = {t|t is a town, t ϕ T 1 , ϕ ∈ {NW, N, W, NW:N, NW:W, W:NW:N}}.
From map M 1 , towns T 2 and T 3 are returned. From map M 2 , towns T 2 and T 4 are
returned. Notice that, also in this second case, without the use of a threshold value
the query result would have been unsatisfactory for the user, as only T 2 from map
M 2 would have been returned.