链表：查询存储在SQLtable中链表的第一个和最后一个元素

Question

我有一个 SQL table，其中“行”表示链表的元素。例如，我可以有以下记录：

(id, previous_id)
------------------
(1, NULL)
(2, NULL)
(3, 2)
(4, 3)
(5, NULL)
(6, 4)
(7, 5)

我们在这个 table 中有 3 个列表：

(1,)
(2,3,4,6)
(5,7)

我想找到每个列表的最后一个元素和列表中元素的数量。我正在寻找的查询将输出：

last, len
1, 1
6, 4
7, 2

这在 SQL 中可行吗？

Answer 1

您可以使用递归 CTE：

with recursive cte as (
      select l.previous_id as id, id as last
      from lines l
      where not exists (select 1 from lines l2 where l2.previous_id = l.id)
      union all
      select l.previous_id, cte.last
      from cte join
           lines l
           on cte.id = l.id
     )
select cte.last, count(*)
from cte
group by cte.last;

Here 是一个 db<>fiddle.

Answer 2

WITH RECURSIVE cte AS (
   SELECT id AS first, id AS last, 1 as len
   FROM   lines
   WHERE  previous_id IS NULL

   UNION ALL
   SELECT c.first, l.id, len + 1
   FROM   cte   c
   JOIN   lines l ON l.previous_id = c.last
   )
SELECT DISTINCT ON (first)
       last, len  -- , first -- also?
FROM   cte
ORDER  BY first, len DESC;

db<>fiddle here

准确生成您的结果。

如果您也想要第一个元素，如您的标题所述，那很容易获得。

Answer 3

这是 Microsoft SQL Server 2016 db<>fiddle

中的一个实现

WITH chain
 AS (SELECT l.id AS [first], 
            l.id AS [last], 
            1 AS [len]
     FROM lines AS l
     WHERE l.previous_id IS NULL
     UNION ALL
     SELECT c.[first], 
            l.id, 
            c.[len] + 1 AS [len]
     FROM chain AS c
          JOIN lines AS l ON l.previous_id = c.[last]),
 result
 AS (SELECT DISTINCT 
            c.[first], 
            c.[last], 
            c.[len], 
            ROW_NUMBER() OVER(PARTITION BY c.[first] ORDER BY c.[len] DESC) AS rn
     FROM chain as c)
 SELECT r.[first], 
        r.[last], 
        r.[len]
 FROM result AS r
 WHERE r.rn = 1
 ORDER BY r.[first];

链表：查询存储在SQLtable中链表的第一个和最后一个元素

Linked lists: query first and last element of chained lists stored in SQL table

sql

postgresql

linked-list

recursive-cte

singly-linked-list