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
 
Search WWH ::




Custom Search