iAnywhere.com - 部件激增问题

部件激增问题

部件激增问题是递归的典型应用。在此问题中，组合特定对象所必需的组件由图形表示。目标是使用数据库表表示此图形，然后计算必需元素部件的总数。

例如，下图显示了一个简单书架的组件。书架由三层架板、一块背板和四条腿组成，四条腿用四个螺钉固定。每块架板用四个螺钉固定。背板用八个螺钉固定。

Graph representing hierarchical relationship of bookshelf subcomponents

下表中的信息表示书架图形的边。第一列命名组件，第二列命名该组件的其中一个子组件，第三列指定需要多少个子组件。

组件	子组件	数量
书架	背面	1
书架	侧面	2
书架	架子	3
书架	底部	4
书架	螺钉	4
背面	背板	1
背面	螺钉	8
侧面	厚板	1
架子	厚板	1
架子	螺钉	4

下面的语句创建了书架表并插入了上表中显示的数据。

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;

下面显示了此查询的结果。

子组件	数量
背板	1
底部	4
厚板	5
螺钉	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
  WHERE p.subcomponent = b.component AND
        p.subcomponent IS NOT NULL
 )
SELECT component, sum(quantity) FROM parts
WHERE subcomponent IS NULL
GROUP BY component
ORDER BY component;

此查询的结果与上一个查询的那些结果相同。