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.
component | subcomponent | quantity |
---|---|---|
bookcase | back | 1 |
bookcase | side | 2 |
bookcase | shelf | 3 |
bookcase | foot | 4 |
bookcase | screw | 4 |
back | backboard | 1 |
back | screw | 8 |
side | plank | 1 |
shelf | plank | 1 |
shelf | screw | 4 |
Execute the following statements to create the bookcase table and insert component and subcomponent data.
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; |
Execute the following statement to generate a list of components and subcomponents and the quantity required to assemble the bookcase.
SELECT * FROM bookcase ORDER BY component, subcomponent; |
Execute the following statement to generate a list of subcomponents and the quantity required to assemble 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.
subcomponent | quantity |
---|---|
backboard | 1 |
foot | 4 |
plank | 5 |
screw | 24 |
Alternatively, you can rewrite this query to perform an additional level of recursion, and avoid the need for the subquery in the main SELECT statement. The results of the following query are identical to those of the previous query.
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; |
Discuss this page in DocCommentXchange.
|
Copyright © 2012, iAnywhere Solutions, Inc. - SQL Anywhere 12.0.1 |