Next: Search Space Up: The Interval Partitioning Problem Previous: Preliminaries

Problem Definition

We can now formally define the interval partitioning (IP) problem. An instance of IP consists of a collection R of intervals and a limit X for the maximum number of intervals allowed in a partition fragment. The reason why we have to allow collections rather than sets is the following: In a temporal relation, for example, two tuples may be distinct yet but can have the same timestamp interval. In the partitioning process it might be necessary to count every tuple but actually neglect all attribute values apart from the timestamp. Intervals that originate from one or more temporal relations can therefore appear more than once and it is important to know how many times.

Figure 5.2 shows an example of such a situation using a simple, uniform partition of the time domain. There are twenty intervals - represented as bold bars - and a uniform partition of the time line that goes from 0 to 20. The breakpoints - 5, 10 and 15 in this case - are shown by vertical lines. The breakpoints themselves belong to the respective left fragment. The figure then gives the resulting loads of the fragments in circles which add up to a total of 39. This means that the partitioning process caused 19 overlaps, i.e. 19 times intervals cross breakpoint lines.

**Figure:** A collection of intervals that has been uniformly partitioned.
$\begin{figure} \epsfxsize=0.9\textwidth \centerline{ \epsffile{/home/tz/work/thesis/fig/ip-uniform.ps}} \centerline{ } \end{figure}$

The goal is now to find an integer m and a partition $P = \{p_1,$ ..., $p_{m-1}\}$ of the span L(R). m can hold any suitable value. The intervals of R are partitioned such that $r \in R$ is put into a fragment R_k if and only if r intersects with the partition range (p_k-1,p_k] that corresponds to R_k ( $k=1,\dots,m$ ). There are two constraints for an optimal P :

1.: The total numbers of intervals that overlap the partition points p₁, ..., p_m-1 is minimal.
2.: No R_k can hold more than X intervals ( $k=1,\dots,m$ ).

The definition is summarised in figure 5.3.

Definition: Interval Partitioning - IP

Instance:

A collection R of intervals ,
a positive number X.

Question:
Is there a partition of R with p_k-1<p_k for that minimises

(14)

such that

(15)

for all $k=1,\dots,m$ where

Definition of IP

Please note the following: the number of intervals within a fragment R_k can be calculated from the value of the functions $s_{\scriptscriptstyle R}$ and $o_{\scriptscriptstyle R}$ . Intervals that intersect with the partition range (p_k-1,p_k] either

start within the partition range, i.e. ; the number of intervals with this property is
or they have started at p_k-1 or before and overlap p_k-1; the number of intervals that have this property is

Consequently, the number of intervals falling into R_k is the sum of these two figures. This is summarised in the following

Lemma 28638

Given a collection R of intervals and a partition is given by the number of intervals falling into a fragment by the equation

(16)

Proof:

See explanation above.

Next: Search Space Up: The Interval Partitioning Problem Previous: Preliminaries

Thomas Zurek