構成部品の問題

構成部品の問題は、再帰を適用できる典型例です。この問題では、特定のオブジェクトを組み立てるために必要なコンポーネントが図で表されます。目的は、この図をデータベース・テーブルを使用して表し、次に必要な要素部品の総数を計算することです。

たとえば、次の図は単純な本棚のコンポーネントを表しています。この本棚は、3 段の棚、背、そして 4 本のねじで固定される 4 本の足から構成されています。各棚は、4 つのねじで固定される板です。背には、8 つのねじで固定される別の板が使われています。

次のテーブル内の情報は、本棚の図のエッジを表しています。最初のカラムはコンポーネントを、2 番目のカラムはそのコンポーネントのサブコンポーネントの 1 つを、そして 3 番目のカラムは必要なサブコンポーネント数を示しています。

コンポーネント	サブコンポーネント	数量
本棚	背	1
本棚	側面	2
本棚	棚	3
本棚	脚	4
本棚	ねじ	4
背	背板	1
背	ねじ	8
側面	厚板	1
棚	厚板	1
棚	ねじ	4

次の文を実行して、bookcase テーブルを作成し、コンポーネント・データとサブコンポーネント・データを挿入します。

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;

次の文を実行して、本棚の組み立てに必要なコンポーネント、サブコンポーネント、およびその数量のリストを生成します。

SELECT * FROM bookcase
ORDER BY component, subcomponent;

次の文を実行して、本棚の組み立てに必要なサブコンポーネントとその数量のリストを生成します。

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;

このクエリの結果を次に示します。

subcomponent	quantity
backboard	1
foot	4
plank	5
screw	24

また、このクエリを別の再帰レベルを実行するように書き直すこともできます。こうすると、メインの SELECT 文内でサブクエリを記述する必要がなくなります。次のクエリの結果は、前述のクエリの結果とまったく同じです。

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;