PostgreSQL 将数据从递归 CTE 传递到函数

Question

我有以下问题:我试图发现从源节点 (node_s) 到目标节点 (node_t) 的所有可能路径。

带图边的原始表格格式很简单:|节点 x |节点_y | strength | ，其中“node_x”->“node_y”是一条直接边，边的强度是“weight”。

这个想法是，如果在探索路径的任何时候我们发现其子节点中的一个节点有目标node_t，我们记录这条路径并停止从这个节点探索路径，否则继续探索.

简单的解决方案是使用 PostgreSQL 的递归 CTE，它构造图的传递闭包:

  WITH RECURSIVE transitive_closure (source, target, weight, path_string) AS
  ( 
   --non-recurive term
   SELECT b.node_x, b.node_y, b.strength, b.node_x || '.' || b.node_y || '.' AS path_string
   FROM best_path b
   WHERE b.node_x = node_s --source_node

   UNION

   --recurive term
   SELECT tc.source, b.node_y, least(tc.weight,b.strength), tc.path_string || b.node_y || '.' AS path_string
   FROM best_path AS b JOIN transitive_closure AS tc ON b.node_x = tc.target
   WHERE tc.path_string NOT LIKE '%' || b.node_y || '.%'
  )
  SELECT * 
  FROM transitive_closure tc
  WHERE tc.target = node_t --target_node

上面的代码将从源节点node_s 发现所有 可能的路径。只有在构建传递闭包之后，我才能选择从源节点到目标节点所需的路径行(参见最后的 SELECT 语句)。

例子:

best_path 表有以下数据:

 node_x | node_y | strength 
--------+--------+----------
      1 |      2 |        1
      1 |      3 |        1
      2 |      4 |        1
      2 |      5 |        1
      3 |      6 |        1
      3 |      7 |        1
      4 |      8 |        1
      4 |      9 |        1
      5 |     10 |        1
      5 |     11 |        1

查询:

找到从源节点 = 1 到目标节点 = 4 的路径

结果:

 source | target | strength | path_string
--------+--------+----------+------------
      1 |      2 |        1 | 1.2.
      1 |      3 |        1 | 1.3.
      1 |      4 |        1 | 1.2.4.
      1 |      5 |        1 | 1.2.5.
      1 |      6 |        1 | 1.3.6.
      1 |      7 |        1 | 1.3.7.
      1 |      8 |        1 | 1.2.4.8.
      1 |      9 |        1 | 1.2.4.9.
      1 |     10 |        1 | 1.2.5.10.
      1 |     11 |        1 | 1.2.5.11.

这不是我需要的。由于已经有从节点 2 到节点 4(目标)的直接边，我不需要路径 1.2.5.、1.2.4.8.、1.2.4.9.、1.2.5.10.、1.2.5.11.，路径探索对于节点 2，应该在发现从 2 到 4 的路径时停止。

总而言之，如果节点已经有到目标节点的直接边，我不想发现该节点的路径。这意味着在 CTE 的递归项中，我希望有一些条件可以说明以下内容，伪代码如下:

  WITH RECURSIVE transitive_closure (source, target, weight, path_string) AS
  ( 
   --non-recurive term (as before)
   SELECT b.node_x, b.node_y, b.strength, b.node_x || '.' || b.node_y || '.' AS path_string
   FROM best_path b
   WHERE b.node_x = node_s --source_node

   UNION

   --recurive term
   SELECT tc.source, b.node_y, least(tc.weight,b.strength), tc.path_string || b.node_y || '.' AS path_string
   FROM best_path AS b JOIN transitive_closure AS tc ON b.node_x = tc.target
   WHERE tc.path_string NOT LIKE '%' || b.node_y || '.%'
     AND b.node_y = node_t 
     --will select only rows with direct edge to target

   UNION (second union is not allowed in CTE)

   SELECT those rows which do not have direct edge to target 
   AND which parents did not contribute to constructing the query above. 
   i.e. b.node_x = tc.target where there is no direct edge between b.node_x to node_t
  )

作为查找从源节点 = 1 到目标节点 = 4 的路径的查询结果，我想要以下内容:

 source | target | strength | path_string
--------+--------+----------+------------
      1 |      2 |        1 | 1.2.
      1 |      3 |        1 | 1.3.
      1 |      4 |        1 | 1.2.4.
      1 |      6 |        1 | 1.3.6.
      1 |      7 |        1 | 1.3.7.

预先感谢您的帮助!

我已经尝试了很多方法:例如FROM/WHERE 子句中的条件，试图将 CTE 传递给函数，但没有成功。

如有任何建议，我们将不胜感激。

我有自己的递归函数来实现我想要的，但是，它在处理大量数据时速度非常慢；并且 PostgreSQL 的 CTE 显然经过了很好的优化，所以我想更深入地研究一下。

Answer 1

如果从底部开始，您可以更有效地搜索路径。从 children 开始。如果您从父级开始，则需要遍历所有子级；而如果您从 child 搜索，它只有一个 parent ，因此不会浪费时间寻找源和目标之间的路径。

with recursive find_parent(source, target, recentness) as
(
    select source, target, 0 
    from tbl
    where target = 9

    union all

    select i.source, i.target, fp.recentness + 1
    from tbl i
    join find_parent fp on i.target = fp.source
),
construct_path(source, target, recentness, path) as
(
  select source, target, recentness, source || '.' || target
  from find_parent 
  where recentness = (select max(recentness) from find_parent)

  union

  select dd.source, dd.target, dd.recentness, cp.path || '.' || dd.target
  from find_parent dd
  join construct_path cp on dd.recentness = cp.recentness - 1  
)
select source, target, path 
from construct_path
order by recentness desc

输出:

SOURCE   TARGET   PATH
1        2        1.2
2        4        1.2.4
4        9        1.2.4.9

现场测试:http://www.sqlfiddle.com/#!1/13e6b/1

与此类似:How to get the parent given a child in SQL SERVER 2005

---

这是优化的，如果它已经找到特定的(源)，则减少对父级的递归。

来源 = 2

目标 = 9

with recursive find_parent(source, target, recentness) as
(
    select source, target, 0 
    from tbl
    where target = 9

    union all

    select i.source, i.target, fp.recentness + 1
    from tbl i
    join find_parent fp on i.target = fp.source 
         -- despite the name, this target is another one's source
         and i.target <> 2
)
,construct_path(source, target, recentness, path) as
(
    select source, target, recentness, source || '.' || target
    from find_parent 
    where recentness = (select max(recentness) from find_parent)

    union

    select dd.source, dd.target, dd.recentness, cp.path || '.' || dd.target
    from find_parent dd
    join construct_path cp on dd.recentness = cp.recentness - 1  

)
select source, target, path
from construct_path
order by recentness desc

输出:

SOURCE   TARGET  PATH
2        4       2.4
4        9       2.4.9

现场测试:http://www.sqlfiddle.com/#!1/13e6b/16