The idea of this strategy is to sequentially fill the fragments R1, R2, ...(Q1, Q2, ..., respectively) such that a given number X of tuples per fragment is `underflowed', i.e. not exceeded. The IP-tables for the individual relations R and Q together with equation (7.1) can be used for this purpose.
The algorithm starts by filling up fragments R1 and Q1 by moving the first breakpoint, p1, as far as possible, i.e. as long as and is guaranteed. When p1 is set, then R2 and Q2 are filled by moving the second breakpoint, p2, as far as possible. The same process is repeated for the following fragments. The number m of fragments is thereby a result of the partitioning process rather than an input parameter as in the case of the uniform strategies.
Figure 9.7 summarises the algorithm that
implements this strategy using the IP-tables of relations R, Q and
. Figure 9.8 shows the partition resulting
from partitioning the example of figure 5.2 using the
basic underflow strategy with X=10.