如何使用递归 CTE 找到最终的 "link in the chain"

Question

我很接近这个但遗漏了一些东西。如何只获取链中的第一个和最后一个链接，例如 A->B、B->C？我怎样才能得到 A->C？

CREATE TEMP TABLE IF NOT EXISTS chains (
    cname TEXT PRIMARY KEY,
    becomes TEXT
);

INSERT INTO chains
VALUES
    ('A', NULL),
    ('B', 'C'),
    ('C', 'D'),
    ('D', 'E'),
    ('E', NULL)
;

WITH RECURSIVE
final_link AS (
SELECT
    chains.cname,
    chains.becomes
FROM
    chains

UNION

SELECT
    chains.cname,
    final_link.becomes
FROM
    chains
    INNER JOIN final_link
    ON chains.becomes = final_link.cname
)
SELECT * FROM final_link;

我想要的结果是：

cname | becomes
------|--------
'B'   | 'E'
'C'   | 'E'
'D'   | 'E'

Answer 1

这是一种方法：

with recursive final_link as (
    select cname, becomes, cname original_cname, 0 lvl 
    from chains 
    where becomes is not null
    union all
    select c.cname, c.becomes , f.original_cname, f.lvl + 1
    from chains c
    inner join final_link f on f.becomes = c.cname
    where c.becomes is not null
)
select distinct on (original_cname) original_cname, becomes 
from final_link 
order by original_cname, lvl desc

想法是让子查询跟踪起始节点以及树中每个节点的级别。然后，您可以在外部查询中使用 distinct on 进行过滤。

Demo on DB Fiddle:

original_cname | becomes
:------------- | :------
B              | E      
C              | E      
D              | E

Answer 2

您可以通过仅从链末端而不是所有链接开始递归来实现此目的，然后像您已经在做的那样迭代地预先添加链接：

WITH RECURSIVE final_link AS (
  SELECT cname, becomes
  FROM chains c
  WHERE (SELECT becomes IS NULL FROM chains WHERE cname = c.becomes)
UNION
  SELECT c.cname, fl.becomes
  FROM chains c
  INNER JOIN final_link fl ON c.becomes = fl.cname
)
SELECT * FROM final_link;

(Demo)

如何使用递归 CTE 找到最终的 "link in the chain"

How do I find the final "link in the chain" using a recursive CTE

sql

postgresql

select

recursive-query

common-table-expression