Allen's interval algebra

The theory for temporal data in a relational model started to evolve more than thirty years ago. I will define quite a few useful Boolean operators and a couple of operators that work on intervals and return an interval. These operators are known as Allen's operators, named after J. F. Allen, who defined a number of them in a 1983 research paper on temporal intervals. All of them are still accepted as valid and needed. A DBMS could help you deal with application times by implementing these operators out of the box.

Let me first introduce the notation I will use. I will work on two intervals, denoted as i1 and i2. The beginning time point of the first interval is b1, and the end is e1; the beginning time point of the second interval is b2 and the end is e2. Allen's Boolean operators are defined in the following table:

Name

Notation

Definition

Equals

(i1 = i2)

(b1 = b2) AND (e1 = e2)

Before

(ibefore i2)

(e< b2)

After

(iafter i2)

(ibefore i1)

Includes

(i i2)

(b≤ b2) AND (e≥ e2)

Properly includes

(i⊃ i2)

(i i2) AND (i≠ i2)

Meets

(i1meets i2)

(b2 = e1 + 1) OR (b1 = e2 + 1)

Overlaps

(ioverlaps i2)

(b≤ e2) AND (b≤ e1)

Merges

(imerges i2)

(i1 overlaps i2) OR (i1 meets i2)

Begins

(ibegins i2)

(b1= b2) AND (e≤ e2)

Ends

(iends i2)

(e= e2) AND (b≥ b2)

In addition to Boolean operators, three of Allen's operators accept intervals as input parameters and return an interval. These operators constitute simple interval algebra. Note that these operators have the same name as relational operators you are probably already familiar with: Union, Intersect, and Minus. However, they don't behave exactly like their relational counterparts.

In general, using any of the three interval operators, if the operation will result in an empty set of time points or in a set that cannot be described by one interval, then the operator should return NULL. A union of two intervals makes sense only if the intervals meet or overlap. An intersection makes sense only if the intervals overlap. The Minus interval operator makes sense only in some cases. For example, (3:10) Minus (5:7) returns NULL because the result cannot be described by one interval. The following table summarizes the definitions of the operators in interval algebra:

Name

Notation

Definition

Union

(i1 union i2)

(Min(b1, b2) : Max(e1, e2)), when (i1 merges i2);

NULL otherwise

Intersect

(iintersect i2)

(Max(b1, b2) : Min(e1, e2)), when (i1 overlaps i2);

NULL otherwise

Minus

(iminus i2)

(b1: Min(b2 - 1, e1)), when (b< b2) AND (e≤ e2);

(Max(e2 + 1, b1) : e1), when (b≥ b2) AND (e> e2);

NULL otherwise

The following figure shows the interval algebra operators graphically:

Interval algebra operators
..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
3.145.202.61