8 Using Qualitative Information in Query Proc. over Multiresolution Maps
163
°
A
A
R(A, B) =
A
◦
∩ B
◦ A
◦
∩ ∂B
∂A ∩ B
◦
∂A ∩ ∂B
R(A, B) =
¬∅ ¬∅
¬∅ ¬∅
(a)
(b)
(c)
°
A
A
A
-
R(A, B) =
⎛
⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝
A
◦
∩ B
◦ A
◦
∩ ∂B A
◦
∩ B
−
∂A ∩ B
◦
∂A ∩ ∂B ∂A ∩ B
−
A
−
∩ B
◦ A
−
∩ ∂B A
−
∩ B
−
⎞
⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠
R(A, B) =
⎛
⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝
¬∅ ¬∅ ¬∅
¬∅ ¬∅ ¬∅
¬∅ ¬∅ ¬∅
⎞
⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠
(d)
(e)
(f)
A
B A
B
A
B
A
B A
B
(g)
(h)
(i)
(l)
(m)
Fig. 8.1. Models for topological relationships: (a) object representation in the 4-intersection
model; (b) the 4-intersection matrix; (c) 4-intersection matrix for Overlap between regions;
(d) object representation in the 9-intersection model; (e) the 9-intersection matrix; (f) 9intersection matrix for Overlap between regions; (g) A Dis joint B; (h) A T ouch B; (i) A In B;
(l) A Overlap B; (m) B Cross A
grouping together similar matrices and assigning a name to each group. The result is
the definition of the following set of binary, jointly exhaustive, and pairwise disjoint
topological relationships: REL = {Dis joint, T ouch, In, Overlap, Cross}, shown in
Fig. 8.1(g)–(m) for regions. Such relationships are now at the basis of query processors of well-known spatial and geographical database systems.
It is important to remark that not all relationships can be defined for any pair of
dimensions; for example, relation Overlap (see Fig. 8.1(l)) is defined only between
pairs of regions or pairs of lines.
Multiresolution has been mainly considered in the definition of ad hoc operators to generalize/specialize map objects while maintaining map consistency. In [8],
topological relationships are considered and a similarity measure between maps, defined as a deviation from consistency, has also been provided. In [15], a formal model
based on planar abstract cell complexes, for representing multiresolution maps and
for their consistent generalization has been proposed. The consistency test is defined
at the combinatorial level by means of homeomorphisms.
In [7], a method for checking similarity between topological relations over
regions, defined according to the 9-intersection model, is presented. Similarity is
determined by comparing two 9-intersection matrices and computing the number of
different values of each intersection (topology distance).
Using this function, a partial order over topological relations has been defined
and used to evaluate how two relations are far from each other. In [5], topology
163
°
A
A
R(A, B) =
A
◦
∩ B
◦ A
◦
∩ ∂B
∂A ∩ B
◦
∂A ∩ ∂B
R(A, B) =
¬∅ ¬∅
¬∅ ¬∅
(a)
(b)
(c)
°
A
A
A
-
R(A, B) =
⎛
⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝
A
◦
∩ B
◦ A
◦
∩ ∂B A
◦
∩ B
−
∂A ∩ B
◦
∂A ∩ ∂B ∂A ∩ B
−
A
−
∩ B
◦ A
−
∩ ∂B A
−
∩ B
−
⎞
⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠
R(A, B) =
⎛
⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝
¬∅ ¬∅ ¬∅
¬∅ ¬∅ ¬∅
¬∅ ¬∅ ¬∅
⎞
⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠
(d)
(e)
(f)
A
B A
B
A
B
A
B A
B
(g)
(h)
(i)
(l)
(m)
Fig. 8.1. Models for topological relationships: (a) object representation in the 4-intersection
model; (b) the 4-intersection matrix; (c) 4-intersection matrix for Overlap between regions;
(d) object representation in the 9-intersection model; (e) the 9-intersection matrix; (f) 9intersection matrix for Overlap between regions; (g) A Dis joint B; (h) A T ouch B; (i) A In B;
(l) A Overlap B; (m) B Cross A
grouping together similar matrices and assigning a name to each group. The result is
the definition of the following set of binary, jointly exhaustive, and pairwise disjoint
topological relationships: REL = {Dis joint, T ouch, In, Overlap, Cross}, shown in
Fig. 8.1(g)–(m) for regions. Such relationships are now at the basis of query processors of well-known spatial and geographical database systems.
It is important to remark that not all relationships can be defined for any pair of
dimensions; for example, relation Overlap (see Fig. 8.1(l)) is defined only between
pairs of regions or pairs of lines.
Multiresolution has been mainly considered in the definition of ad hoc operators to generalize/specialize map objects while maintaining map consistency. In [8],
topological relationships are considered and a similarity measure between maps, defined as a deviation from consistency, has also been provided. In [15], a formal model
based on planar abstract cell complexes, for representing multiresolution maps and
for their consistent generalization has been proposed. The consistency test is defined
at the combinatorial level by means of homeomorphisms.
In [7], a method for checking similarity between topological relations over
regions, defined according to the 9-intersection model, is presented. Similarity is
determined by comparing two 9-intersection matrices and computing the number of
different values of each intersection (topology distance).
Using this function, a partial order over topological relations has been defined
and used to evaluate how two relations are far from each other. In [5], topology