时间戳

首页 > 解决方案 > 去除树状结构中的过多关系

sql - 去除树状结构中的过多关系

问题描述

该表包括两个带有 nodes_id 的字段和一个带有关系的字段（只有一个变体：'Include'）

删除标记为红色的关系

如果两个其他节点之间有任何中间节点，我需要删除过多的关系

带有示例的表格

CREATE TABLE relationships (
node_id_1 varchar (255),
node_id_2 varchar (255),
relationship varchar(255)
);

INSERT INTO relationships
VALUES ('node_1', 'node_2', 'Include'),
       ('node_1', 'node_3', 'Include'),
       ('node_1', 'node_4', 'Include'),
       ('node_1', 'node_5', 'Include'),
       ('node_1', 'node_6', 'Include'),
       ('node_1', 'node_7', 'Include'),
       ('node_1', 'node_8', 'Include'),
       ('node_1', 'node_9', 'Include'),
       ('node_1', 'node_10', 'Include'),
       ('node_1', 'node_11', 'Include'),
       ('node_3', 'node_5', 'Include'),
       ('node_4', 'node_5', 'Include'),
       ('node_6', 'node_7', 'Include'),
       ('node_8', 'node_9', 'Include'),
       ('node_9', 'node_10', 'Include');
);

标签： sqlpostgresql

解决方案

您的测试数据似乎与您的测试图不匹配（没有 8-10 或 8-11 链接，但有 1-10）。您可以使用递归 CTE 来跟踪路径。这部分查询几乎与文档中的示例相同：https ://www.postgresql.org/docs/current/queries-with.html尽管我们不会使用查询的循环部分：

WITH RECURSIVE search_graph(node_id_1, node_id_2, depth, path, cycle) AS (
 SELECT node_id_1, node_id_2, 1, ARRAY[node_id_1::text, node_id_2::text], false
 FROM relationships
 UNION ALL
 SELECT r.node_id_1, r.node_id_2, sg.depth + 1, path || r.node_id_2::text, r.node_id_1 = ANY(PATH)
 FROM relationships r, search_graph sg
 WHERE r.node_id_1 = sg.node_id_2 --AND NOT cycle
)
select * from search_graph;
 node_id_1 | node_id_2 | depth |              path              | cycle
-----------+-----------+-------+--------------------------------+-------
 node_1    | node_2    |     1 | {node_1,node_2}                | f
 node_1    | node_3    |     1 | {node_1,node_3}                | f
 node_1    | node_4    |     1 | {node_1,node_4}                | f
 node_1    | node_5    |     1 | {node_1,node_5}                | f
 node_1    | node_6    |     1 | {node_1,node_6}                | f
 node_1    | node_7    |     1 | {node_1,node_7}                | f
 node_1    | node_8    |     1 | {node_1,node_8}                | f
 node_1    | node_9    |     1 | {node_1,node_9}                | f
 node_1    | node_10   |     1 | {node_1,node_10}               | f
 node_1    | node_11   |     1 | {node_1,node_11}               | f
 node_3    | node_5    |     1 | {node_3,node_5}                | f
 node_4    | node_5    |     1 | {node_4,node_5}                | f
 node_6    | node_7    |     1 | {node_6,node_7}                | f
 node_8    | node_9    |     1 | {node_8,node_9}                | f
 node_9    | node_10   |     1 | {node_9,node_10}               | f
 node_3    | node_5    |     2 | {node_1,node_3,node_5}         | t
 node_4    | node_5    |     2 | {node_1,node_4,node_5}         | t
 node_6    | node_7    |     2 | {node_1,node_6,node_7}         | t
 node_8    | node_9    |     2 | {node_1,node_8,node_9}         | t
 node_9    | node_10   |     2 | {node_1,node_9,node_10}        | t
 node_9    | node_10   |     2 | {node_8,node_9,node_10}        | t
 node_9    | node_10   |     3 | {node_1,node_8,node_9,node_10} | t
(22 rows)

我们可以自连接此查询的结果，以挑选出连接一侧的路径的开始和结束与另一侧的 node_id_1 和 node_id_2 匹配且深度较小的行：

WITH RECURSIVE search_graph(node_id_1, node_id_2, depth, path, cycle) AS (
 SELECT node_id_1, node_id_2, 1, ARRAY[node_id_1::text, node_id_2::text], false
 FROM relationships
 UNION ALL
 SELECT r.node_id_1, r.node_id_2, sg.depth + 1, path || r.node_id_2::text, r.node_id_1 = ANY(PATH)
 FROM relationships r, search_graph sg
 WHERE r.node_id_1 = sg.node_id_2 --AND NOT cycle
)
SELECT distinct sg1.node_id_1, sg1.node_id_2
FROM search_graph sg1
JOIN search_graph sg2 ON sg1.node_id_1 = sg2.path[1] AND sg1.node_id_2 = sg2.path[array_length(sg2.path, 1)]
  AND sg1.depth < sg2.depth;
 node_id_1 | node_id_2
-----------+-----------
 node_1    | node_10
 node_1    | node_5
 node_1    | node_7
 node_1    | node_9
(4 rows)

推荐阅读