PostgresSQL SQL 查询 return 所有图形节点（连接的组件），提供了一个节点来查询

Question

在我的 Postgresql 数据库中，我有一个或多个有向无环图，由以下 tables 表示：

表格：

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

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

如果我在最左边的图中查询 any 节点，我希望查询到该图中的 return all 节点（不包括数据库中其他图中的任何节点）

也许另一种思考方式是，对于此查询，我想将图视为无向图，return 所有具有 any[=40 的节点=] 查询节点的路径。

我在类似的 table 结构中找到了，但它似乎超出了我想要完成的目标。我只想 return 一个子图 - 特别是包含我要查询的节点的子图。我想我可以过滤我感兴趣的节点的输出，但这似乎效率低下 - 搜索整组图，然后只 returning 一个。一定有更好的方法，但我对 SQL 还是很陌生。

这是一个 regarding graphs in R, and ，但我真的想在数据库中而不是在外部代码中执行此操作。

编辑：我还根据该答案找到了 , but it doesn't seem to work as expected. If I select node 1 as the starting point, all's good. But other nodes within the same graph don't provide the expected output of all the nodes in that graph. Here's an sqlfiddle。想法？我错过了什么吗？

Answer 1

您可以使用递归 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

结果：

参见 DB Fiddle 中的运行示例。

PostgresSQL SQL 查询 return 所有图形节点（连接的组件），提供了一个节点来查询

PostgreSQL SQL Query to return all graph nodes (the connected components), provided a node to query upon

sql

postgresql

graph

subgraph