Information Technology Reference
In-Depth Information
Fig. 3.
Translation from basic RCD-relations to RA-relations via the
toRA
mapping
can always determine the strongest RA-relation it implies. As an example, the strongest
RA-relation implied by
NW
:
N
is
{
fi,o
}×{
mi,bi
}
. Notice that such an RA-relation,
which is entailed by a basic RCD-relation, is not a basic RA-relation.
The weaker expressive power of the RCD-calculus with respect to RA is not nec-
essarily a problem. As an example, if we are interested in pure cardinal information
only, the expressiveness of RCD-relations suffices. Moreover, the constraint language
of the RCD-calculus is closer to the natural language than the one of the RA. For
example, stating that “rectangle
a
lies partly to the northwest and partly to the north
of
b
”(
a
b
) is much more natural than stating that “the
x
-projection of
a
is overlapping or finished by the
x
-projection of
b
,andthe
y
-projection of
b
is ...”
(
a
{
NW
:
N
}
b
).
Figure 3 describes a translation function, called
toRA
, to map a basic RCD-relation
into the strongest entailed
RA
-relation. This mapping can be extended to translate ar-
bitrary relations, constraints, and networks of the RCD-calculus to their RA counter-
parts, preserving consistency. More precisely, given a disjunctive relation
R
,
toRA
(
R
)
is obtained as the union of the translation of the basic relations in
R
, while, given an
RCD-network
N
=(
V,C
)
, the corresponding RA-network
toRA
(
N
)
is obtained by
replacing each relation
R
ij
in
C
by
toRA
(
R
ij
)
. As the following theorem states, to
decide the consistency of an RCD-network
N
, one can compute
toRA
(
N
)
and then
apply to it any algorithm for deciding the consistency of RA-networks [18].
Theorem 2.
An RCD-network
N
is consistent if and only if
toRA
(
N
)
is consistent.
{
fi,o
}×{
mi,bi
}
3.2
The Convex Fragment of the RCD-Calculus
In [18], the authors show that the consistency problem for the RCD-calculus is NP-
complete and they identify a large tractable subset of RCD-relations. Such a fragment,
called
convex RCD-calculus
, consists of all and only the RCD-relations
R
whose trans-
lation
toRA
(
R
)
is a convex RA-relation. It is possible to show that there exist
400