sql - 从sql中的点数据库中获取路径

Question

假设我有一个点表，每个点都有 2 个坐标。例如:

Source       |       Destination 
1            |       2
2            |       3
3            |       7
5            |       7
9            |       12

我想用 SQL 编写一个查询，它会提供以下信息:

1. 这些点构成的所有路径。每条路径都必须有连接点，因为下一个点的源坐标与前一个点的目标点相同。
2. 路径不能是循环的。

例如，在上表中，运行查询应该返回 3*paths:

1. (1,2) (2,3) (3,7)
2. (5,7)
3. (9,12)

我想到复制点数表，我们称它们为A和B，然后设置一个条件:

SELECT source, destination 
FROM A, B
WHERE A.source = B.destination

但我不确定答案，我几乎可以肯定它不是最优的。

Answer 1

使用带有array[array[source, destination]] 的递归 cte 作为聚合列:

with recursive cte(source, destination, path) as (
    select source, destination, array[array[source, destination]]
    from points
union all
    select p.source, p.destination, path || array[p.source, p.destination]
    from cte c
    join points p on c.destination = p.source
    where not array[array[p.source, p.destination]] <@ path
)
select distinct on (path[1:1]) path
from (
    select distinct on (source, destination) *
    from cte
    order by source, destination, array_length(path, 1) desc
    ) s    
order by path[1:1], array_length(path, 1) desc;

        path         
---------------------
 {{1,2},{2,3},{3,7}}
 {{5,7}}
 {{9,12}}
(3 rows)