Parts-explosion problem

When you use a cursor supplemented by program logic, you can solve problems that plain SQL cannot solve. One of these problems is the parts-explosion problem, sometimes called bill-of-materials processing. At the heart of this problem is a recursive relationship among objects; one object contains other objects, which contain yet others.

The problem is usually stated in terms of a manufacturing inventory. A company makes a variety of parts, for example. Some parts are discrete, but some are assemblages of other parts.

These relationships are documented in a single table, which might be called contains. The column contains.parent holds the part numbers of parts that are assemblages. The column contains.child has the part number of a part that is a component of the parent. If part number 123400 is an assembly of nine parts, nine rows exist with 123400 in the first column and other part numbers in the second. The following figure shows one of the rows that describe part number 123400.

This figure is described in the surrounding text. — Figure 1. Parts-explosion problem

Here is the parts-explosion problem: given a part number, produce a list of all parts that are components of that part. The following example is a sketch of one solution, as implemented in Informix® ESQL/C:

int part_list[200];

boom(top_part)
int top_part;
{
   long this_part, child_part;
   int next_to_do = 0, next_free = 1;
   part_list[next_to_do] = top_part;

   EXEC SQL DECLARE part_scan CURSOR FOR
      SELECT child INTO child_part FROM contains
         WHERE parent = this_part;
   while(next_to_do < next_free)
   {
      this_part = part_list[next_to_do];
      EXEC SQL OPEN part_scan;
      while(SQLCODE == 0)
      {
         EXEC SQL FETCH part_scan;
         if(SQLCODE == 0)   
         {
            part_list[next_free] = child_part;
            next_free += 1;
         }
      }
      EXEC SQL CLOSE part_scan;
      next_to_do += 1;
   }
   return (next_free - 1);
}

Technically speaking, each row of the contains table is the head node of a directed acyclic graph, or tree. The function performs a breadth-first search of the tree whose root is the part number passed as its parameter. The function uses a cursor named part_scan to return all the rows with a particular value in the parent column. The innermost while loop opens the part_scan cursor, fetches each row in the selection set, and closes the cursor when the part number of each component has been retrieved.

This function addresses the heart of the parts-explosion problem, but the function is not a complete solution. For example, it does not allow for components that appear at more than one level in the tree. Furthermore, a practical contains table would also have a column count, giving the count of child parts used in each parent. A program that returns a total count of each component part is much more complicated.

The iterative approach described previously is not the only way to approach the parts-explosion problem. If the number of generations has a fixed limit, you can solve the problem with a single SELECT statement using nested, outer self-joins.

If up to four generations of parts can be contained within one top-level part, the following SELECT statement returns all of them:

SELECT a.parent, a.child, b.child, c.child, d.child
   FROM contains a
      OUTER (contains b,
         OUTER (contains c, outer contains d) )
   WHERE a.parent = top_part_number
      AND a.child = b.parent
      AND b.child = c.parent
      AND c.child = d.parent

This SELECT statement returns one row for each line of descent rooted in the part given as top_part_number. Null values are returned for levels that do not exist. (Use indicator variables to detect them.) To extend this solution to more levels, select additional nested outer joins of the contains table. You can also revise this solution to return counts of the number of parts at each level.