3.5 Limiting Region Size

3.5.1 Problem

You want to find regions of a certain size. In our example, let's say that you want to find all those regions in which there are exactly two containers of 100 purity. Such regions can be packed automatically for shipment; others must be sorted manually.

3.5.2 Solution

Because we used increasing ContainerId numbers, we can limit the size of a region in the WHERE clause of our query by limiting the distance between indices using the formula SIZE-1. Since we are looking for the regions of size 2, we use 2-1 or 1:

SELECT p1.ContainerId RegBeg, p2.ContainerId RegEnd
FROM ProductionLine p1, ProductionLine p2
WHERE (p1.ContainerId < p2.ContainerId) AND
   p2.ContainerId-p1.ContainerId=1 AND
   NOT EXISTS(SELECT * FROM ProductionLine p3 
      WHERE (p3.Purity!=100 AND 
      p3.ContainerId BETWEEN p1.ContainerId AND p2.ContainerId))

RegBeg      RegEnd      
----------- ----------- 
1           2
10          11
11          12

3.5.3 Discussion

This query is commonly used in various combinatorial problems. It is similar to the query in the previous recipe, but with two important differences. First, it limits the size of the region to a fixed size. Since the table has arithmetically increasing ContainerId values, this can be achieved by a restriction on the difference between two indices.

p2.ContainerId-p1.ContainerId=1

The second difference is that you do not need to search for the largest possible regions, so the last two conditions in the WHERE clause of the previous recipe's subquery can be omitted from this query.

It is very easy to extend this recipe to find all regions that are larger or smaller than a certain size. For example, to find all regions of two or more containers, use the following WHERE clause restriction:

...
p2.ContrainerId - p1.ContainerId >=1
...

In the same way, you could limit the query to all regions having five or fewer rows:

...
p2.ContrainerId - p1.ContainerId <=4
...

These last two modifications would return all candidate regions, even those smaller regions that are inside larger regions. Depending on the results you want, if you use one of these modifications, you may wish to add back those two WHERE conditions from the previous recipe that limited the regions returned to only those that are not contained within another larger region.