SQL Anywhere 10.0.1 » SQL Anywhere Server - SQL Usage » Common Table Expressions

Parts explosion problems

The parts explosion problem is a classic application of recursion. In this problem, the components necessary to assemble a particular object are represented by a graph. The goal is to represent this graph using a database table, then to calculate the total number of the necessary elemental parts.

For example, the following graph represents the components of a simple bookshelf. The bookshelf is made up of three shelves, a back, and four feet that are held on by four screws. Each shelf is a board held on with four screws. The back is another board held on by eight screws.

The information in the table below represents the edges of the bookshelf graph. The first column names a component, the second column names one of the subcomponents of that component, and the third column specifies how many of the subcomponents are required.

componentsubcomponentquantity
bookcaseback1
bookcaseside2
bookcaseshelf3
bookcasefoot4
bookcasescrew4
backbackboard1
backscrew8
sideplank1
shelfplank1
shelfscrew4

The following statements create the bookcase table and insert the data shown in the above table.

```CREATE TABLE bookcase (
component      VARCHAR(9),
subcomponent   VARCHAR(9),
quantity       INTEGER,
PRIMARY KEY ( component, subcomponent )
);
INSERT INTO bookcase
SELECT 'bookcase', 'back',      1 UNION
SELECT 'bookcase', 'side',      2 UNION
SELECT 'bookcase', 'shelf',     3 UNION
SELECT 'bookcase', 'foot',      4 UNION
SELECT 'bookcase', 'screw',     4 UNION
SELECT 'back',     'backboard', 1 UNION
SELECT 'back',     'screw',     8 UNION
SELECT 'side',     'plank',     1 UNION
SELECT 'shelf',    'plank',     1 UNION
SELECT 'shelf',    'screw',     4;```

After you have created the bookcase table, you can recreate the table of its parts, shown above, with the following query.

```SELECT * FROM bookcase
ORDER BY component, subcomponent;```

With this table constructed, you can generate a list of the primitive parts and the quantity of each required to construct the bookcase.

```WITH RECURSIVE parts ( component, subcomponent, quantity ) AS
( SELECT component, subcomponent, quantity
FROM bookcase WHERE component = 'bookcase'
UNION ALL
SELECT b.component, b.subcomponent, p.quantity * b.quantity
FROM parts p JOIN bookcase b ON p.subcomponent = b.component )
SELECT subcomponent, SUM( quantity ) AS quantity
FROM parts
WHERE subcomponent NOT IN ( SELECT component FROM bookcase )
GROUP BY subcomponent
ORDER BY subcomponent;```

The results of this query are shown below.

subcomponentquantity
backboard1
foot4
plank5
screw24

Alternatively, you can rewrite this query to perform an additional level of recursion, thus avoiding the need for the subquery in the main SELECT statement:

```WITH RECURSIVE parts ( component, subcomponent, quantity ) AS
( SELECT component, subcomponent, quantity
FROM bookcase WHERE component = 'bookcase'
UNION ALL
SELECT p.subcomponent, b.subcomponent,
IF b.quantity IS NULL
THEN p.quantity
ELSE p.quantity * b.quantity
ENDIF
FROM parts p LEFT OUTER JOIN bookcase b
ON p.subcomponent = b.component
WHERE p.subcomponent IS NOT NULL
)
SELECT component, SUM( quantity ) AS quantity
FROM parts
WHERE subcomponent IS NULL
GROUP BY component
ORDER BY component;```

The results of this query are identical to those of the previous query.