如何在postgresql中高效遍历节点？

Question

我正在尝试使用 PostgreSQL 中的递归子句从特定节点遍历节点。（顺便说一句，我是 Postgresql 的新手）这是我的数据库表的简单版本：

 table: nodes
|--------------|------------------|
|      id      |     node_name    |
|--------------|------------------|
|      1       |         A        |
|--------------|------------------|
|      2       |         B        |
|--------------|------------------|
|      3       |         C        |
|--------------|------------------|
|      4       |         D        |
|--------------|------------------|
|      5       |         E        |


table: links
|--------------|---------------------|-----------------|
|      id      |        id_from      |      id_to      |
|--------------|---------------------|-----------------|
|      1       |           1         |         2       |
|--------------|---------------------|-----------------|
|      2       |           1         |         3       |
|--------------|---------------------|-----------------|
|      3       |           2         |         4       |
|--------------|---------------------|-----------------|
|      4       |           3         |         4       |
|--------------|---------------------|-----------------|
|      5       |           4         |         5       |

所以，就是这个简单的有向图。（所有边从左到右）

    B
  /   \
 A     D - E
  \   /
    C

在这种情况下，获取从 A 开始的所有可访问顶点的有效方法是什么？

我尝试了什么：

在 Simple Graph Search Algorithm in SQL (PostgreSQL)

找到的 dfs 解决方案

with recursive graph(node1, node2, path) as
(
    select id_from, id_to, ARRAY[id_from] from links
        where id_from = 1
    union all
    select nxt.id_from, nxt.id_to,array_append(prv.path, nxt.id_from)
    from links nxt, graph prv
    where nxt.id_from = prv.node2
    and nxt.id_from != ALL(prv.path)
)
select * from graph

它给了我几乎所有的路径。但是它访问了 D 顶点两次。（执行两次D -> E逻辑）我想忽略访问过的顶点以提高效率。

那么，我该如何实现呢？提前致谢！

Answer 1

没那么简单。在单个查询中，所有递归路径都是完全独立的。所以，每条路径都不知道兄弟路径上发生了什么。它不知道某个节点已经被兄弟访问过。

因为SQL查询不支持某种全局变量，所以不可能以这种方式在递归路径之间共享此类信息。

我建议编写一个函数，您可以在其中使用 plsql 语法，以更“通用的编程”方式解决问题。

如何在postgresql中高效遍历节点？

How to traverse nodes efficiently in postgresql?

database

postgresql

graph

breadth-first-search

graph-databases