递归查询用于传递闭包。

Question

我已经创建了一个简单的示例，使用PostgreSQL中的递归查询来说明传递闭包。

然而，我的递归查询有些问题。我还不熟悉语法，所以这个请求可能完全是新手的问题，对此我提前道歉。如果你运行查询，你会发现节点1在路径结果中重复出现了。请问有人可以帮助我调整SQL吗？

/*           1
           /   \
          2     3
         / \   /
        4  5  6
       /
      7
     / \
    8   9
*/

create table account(
acct_id INT,
parent_id INT REFERENCES account(acct_id),
acct_name VARCHAR(100),
PRIMARY KEY(acct_id)
);

insert into account (acct_id, parent_id, acct_name) values (1,1,'account 1');
insert into account (acct_id, parent_id, acct_name) values (2,1,'account 2');
insert into account (acct_id, parent_id, acct_name) values (3,1,'account 3');
insert into account (acct_id, parent_id, acct_name) values (4,2,'account 4');
insert into account (acct_id, parent_id, acct_name) values (5,2,'account 5');
insert into account (acct_id, parent_id, acct_name) values (6,3,'account 6');
insert into account (acct_id, parent_id, acct_name) values (7,4,'account 7');
insert into account (acct_id, parent_id, acct_name) values (8,7,'account 8');
insert into account (acct_id, parent_id, acct_name) values (9,7,'account 9');

WITH RECURSIVE search_graph(acct_id, parent_id, depth, path, cycle) AS (
        SELECT g.acct_id, g.parent_id, 1,
          ARRAY[g.acct_id],
          false
        FROM account g
      UNION ALL
        SELECT g.acct_id, g.parent_id, sg.depth + 1,
          path || g.acct_id,
          g.acct_id = ANY(path)
        FROM account g, search_graph sg
        WHERE g.acct_id = sg.parent_id AND NOT cycle
)
SELECT path[1] as Child,parent_id as Parent,path || parent_id as path FROM search_graph
ORDER BY path[1],depth;

- Dowwie

---

你的测试设置很稳定且有用，但请详细解释一下你的结果应该是什么样子？仅仅加入“传递闭包”这个关键词并不足以作为解释。 - Erwin Brandstetter

Answer 1

你可以在几个地方进行简化（假设acct_id和parent_id不为空）：

WITH RECURSIVE search_graph AS (
   SELECT parent_id, ARRAY[acct_id] AS path
   FROM   account

   UNION  ALL
   SELECT g.parent_id, sg.path || g.acct_id
   FROM   search_graph sg
   JOIN   account g ON g.acct_id = sg.parent_id 
   WHERE  g.acct_id <> ALL(sg.path)
   )
SELECT path[1] AS child
     , path[array_upper(path,1)] AS parent
     , path
FROM   search_graph
ORDER  BY path;

• 在您的查询中，acct_id、depth和cycle列只是噪音。
• WHERE条件必须比原始查询提前一个递归步骤退出，在从顶部节点开始的重复项进入结果之前。这是您原始查询中的“偏移量为一”。

其余部分是格式化。

如果您知道图表中唯一可能的循环是自我引用，那么我们可以更便宜地实现：

WITH RECURSIVE search_graph AS (
   SELECT parent_id, ARRAY[acct_id] AS path, acct_id <> parent_id AS keep_going
   FROM   account

   UNION  ALL
   SELECT g.parent_id, sg.path || g.acct_id, g.acct_id <> g.parent_id
   FROM   search_graph sg
   JOIN   account g ON g.acct_id = sg.parent_id 
   WHERE  sg.keep_going
)
SELECT path[1] AS child
     , path[array_upper(path,1)] AS parent
     , path
FROM   search_graph
ORDER  BY path;

SQL Fiddle.

请注意，对于带有修饰符的数据类型（比如varchar(5)），存在问题（至少在pg v9.4之前），因为数组连接会丢失修饰符，但是rCTE坚持要求类型完全匹配：

• 数据类型带类型修饰符时会出现意外结果

- Erwin Brandstetter

---

非常感谢您周到的回复！两个查询（即使是后者）都完全按照我的意图工作。 - Dowwie

Answer 2

您已将帐户1设置为其自身的父级。如果您将该帐户的父级设置为null，则可以避免该帐户同时成为起始节点和结束节点（按照您的逻辑设置，您将包括一个循环，但然后不会添加到该循环中，这似乎是合理的）。还有一点需要注意的是，将最终的“路径”列更改为类似于case when parent_id is not null then path || parent_id else path end的内容，以避免在末尾出现null，这样看起来更加美观。

- yieldsfalsehood

---

你运行了我的示例并确认了吗？当我将账户1的插入更改为null父级时，结果并没有改善。 - Dowwie