时间戳

首页 > 解决方案 > PostgreSQL SQL 查询返回所有图形节点（连接的组件），提供一个节点来查询

sql - PostgreSQL SQL 查询返回所有图形节点（连接的组件），提供一个节点来查询

问题描述

在我的 Postgresql DB 中，我有一个或多个有向无环图，由下表表示：

表：

nodes_table
    id

edges_table
    id
    parent_id -- a nodes_table id
    child_id -- a nodes_table id

假设我有以下数据，这是一个示例，其中 3 个单独的图表存储在数据库中。请注意，这三个图表之间没有任何联系：

nodes_table
1
2
3
4
5
6
7
8
9
10
11
12
13

edges_table
1, 1, 2
2, 1, 5
3, 2, 3
4, 3, 4
5, 5, 10
6, 9, 5
7, 9, 11
8, 3, 10
9, 6, 7
10, 8, 12
11, 8, 13

Output (3 separate graph structures, with the roots at the top):
 
  1   9         6       8
 / \ / \        |      / \
2   5   11      7     12 13
|   |
|   |
3   |
| \ |
4   10

有没有一种方法可以让所有节点以任何方式（包括通过其他节点，上下给定图形）提供查询节点？

如果我查询最左边图中的任何节点，我希望我的查询返回该图中的所有节点（不包括数据库中其他图中的任何节点）

也许另一种思考方式是，对于这个查询，我想将图形视为无向图，并返回所有具有任何路径到查询节点的节点。

我找到了这个答案，它在一个类似的表结构中找到了所有连接的子图，但对于我想要完成的事情来说，这似乎太过分了。我只想返回一个子图 - 特别是包含我要查询的节点的子图。我想我可以过滤我感兴趣的节点的输出，但这似乎效率低下 - 搜索整个图表集，然后只返回一个。必须有更好的方法，但我对 SQL 还是很陌生。

这是关于 R 中的图形的类似问题，以及使用 NetworkX 的方法，但我真的想在数据库中而不是在外部代码中执行此操作。

编辑：我也找到了类似问题的答案，但它似乎没有按预期工作。如果我选择节点 1 作为起点，一切都很好。但是同一图中的其他节点不提供该图中所有节点的预期输出。这是基于该答案的sqlfiddle 。想法？我错过了什么吗？

标签： sqlpostgresqlgraphsubgraph

解决方案

您可以使用递归 CTE 来获取所有相关节点。

例如：

with recursive
n as (
  select 5 as id -- starting node
 union
  select case when e.child_id = n.id then e.parent_id else e.child_id end
  from n
  join edges_table e on e.parent_id = n.id or e.child_id = n.id
)
select * from n

结果：

id 
-- 
5  
1  
10 
9  
2  
3  
11 
4

请参阅DB Fiddle上的运行示例。

推荐阅读