As a third option, we propose to divide the startpoints' span
for the following reason: after , no more intervals start, i.e. no more intervals are added to the plot. If a breakpoint pk was chosen after that point then the fragments Rk+1 and Qk+1 would hold only intervals that are already in Rk and Qk and thus would already be joined in . Thus a join would be without relevance. It is therefore feasible to divide the startpoints' span rather than the lifespan in order to avoid such a situation.The only significant difference in comparison to uniform lifespan partitioning is that and therefore that the lengths of the segments might be smaller. can be calculated by using the IP-table :
with The algorithm for determining the breakpoints is given in figure 9.5. Figure 9.6 shows the uniform startpoints' partition for the example of figure 5.2.As in the case of uniform range partitioning, incomplete IP-tables might not provide sufficient information to determine the startpoints' span exactly. Nevertheless, the algorithm in figure 9.5 might still calculate a and therefore might still provide some of the benefits of the startpoints' span over the lifespan approach.
The index of a within an IP-table can be stored as an additional parameter in order to avoid to compute it at run time: when two or more IP-tables are merged then the resulting can be computed as
where are the respective maximum startpoints of the IP-tables that participate in the merge.