Information Technology Reference
In-Depth Information
Fig. 1.
Basic relations of the Interval Algebra
which does not necessarily imply that it is consistent. In some special cases, the PC-
algorithm can be used to decide the consistency of a qualitative network and to get the
minimal one.
2.1
Interval Algebra and Point Algebra
Allen's
Interval Algebra
(IA) allows one to constrain the relative position of two time
intervals [1]. An interval
I
is usually interpreted as a closed interval over the rational
numbers
[
I
−
,I
+
]
, whose
endpoints
I
−
and
I
+
satisfy the relation
I
−
<I
+
.Let
B
ia
be the set of the thirteen
basic interval relations
capturing all possible ways to order the
four endpoints of two intervals, usually denoted by the symbols
b,o,d,m,s,f,e,bi,oi,
di, mi
,
si
,and
fi
. The semantics of basic IA-relations is defined in terms of ordering
relations between the endpoints of the intervals, as shown in Figure 1. Notice that, given
a basic relation
r
between two intervals
I
and
J
, the inverse relation
ri
is defined by
simply exchanging the roles of
I
and
J
(see Figure 1). IA can be viewed as a constraint
algebra defined by the power set
2
B
ia
and the operations of intersection, inverse (
−
1
),
and composition (
) of relations.
IA subsumes
Point Algebra
(PA) [25], a simpler qualitative calculus whose binary
relations specify the relative position of pairs of time points. PA binary relations are
<,>,
=
(basic) and
◦
=
,
?
(disjunctive), plus the empty relation. The endpoint re-
lations defining a basic IA-relation (Figure 1) are basic relations of PA.
≤
,
≥
,
2.2
Rectangle Algebra
Rectangle Algebra
(RA), proposed by Balbiani et al. (1998), is an extension of IA to
a bidimensional space. We assume here the domain of RA to consist of the set of ra-
tional rectangles whose sides are parallel to the axes of the Euclidean plane. To avoid
a notational overload, with a little abuse of notation, hereafter we will denote by
a, b
both rectangles in the domain of RA and constraint (rectangle) variables. A rectangle
a
is completely characterized by a pair of intervals
(
a
x
,a
y
)
,where
a
x
and
a
y
are the
projections of
a
onto the
x
-and
y
-axis, respectively. We call
B
ra
the set of basic rela-
tions of RA, which is obtained by considering all possible pairs of basic IA-relations.
