用于传递闭包的递归查询 [英] Recursive query used for transitive closure

问题描述

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

I've created a simple example to illustrate transitive closure using recursive queries in PostgreSQL.

但是，我的递归查询有些问题。我现在还不熟悉语法，因此这个要求对我来说完全是个废话，对此我深表歉意。如果运行查询，您将看到节点1在路径结果中重复。有人可以帮我弄清楚如何调整SQL吗？

However, something is off with my recursive query. I'm not familiar with the syntax yet so this request may be entirely noobish of me, and for that I apologize in advance. If you run the query, you will see that node 1 repeats itself in the path results. Can someone please help me figure out how to tweak the 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;

推荐答案

您可以在几个地方进行简化（假设 acct_id 和 parent_id 是 NOT NULL ）：

You can simplify in several places (assuming acct_id and parent_id are NOT NULL):

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 ，深度，周期只是查询中的噪音。


• WHERE 条件必须提前一步退出递归，即之前出现来自顶部节点的重复条目。


• The columns acct_id, depth, cycle are just noise in your query.
• The WHERE condition has to exit the recursion one step earlier, before the duplicate entry from the top node is in the result. That was an "off-by-one" in your original.

其余的正在格式化。

如果您知道图形中唯一可能的圆是自引用，我们可以便宜一些：

If you know the only possible circle in your graph is a self-reference, we can have that cheaper:

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小提琴。

请注意会出现问题（至少在pg v9.4以下）对于带有修饰符的数据类型（例如 varchar（5）），因为数组级联会丢失修饰符，但rCTE坚持严格匹配类型：

Note there would be problems (at least up to pg v9.4) for data types with a modifier (like varchar(5)) because array concatenation loses the modifier but the rCTE insists on types matching exactly:



• 具有类型修饰符的数据类型的惊人结果


• Surprising results for data types with type modifier

这篇关于用于传递闭包的递归查询的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！