Tìm khu rừng bao trùm (VỚI RECURSIVE, PostgreSQL 9.5)

Tôi đã viết câu trả lời cho một câu hỏi tương tự cách đây không lâu: Cách tìm tất cả các đồ thị con được kết nối của một biểu đồ vô hướng . Trong câu hỏi đó, tôi đã sử dụng SQL Server. Xem câu trả lời đó để biết giải thích chi tiết về các CTE trung gian. Tôi đã điều chỉnh truy vấn đó thành Postgres.

Nó có thể được viết hiệu quả hơn bằng cách sử dụng tính năng mảng Postgres thay vì nối đường dẫn vào một text cột.

WITH RECURSIVE
CTE_Idents
AS
(
    SELECT old AS Ident
    FROM identities

    UNION

    SELECT new AS Ident
    FROM identities
)
,CTE_Pairs
AS
(
    SELECT old AS Ident1, new AS Ident2
    FROM identities
    WHERE old <> new

    UNION

    SELECT new AS Ident1, old AS Ident2
    FROM identities
    WHERE old <> new
)
,CTE_Recursive
AS
(
    SELECT
        CTE_Idents.Ident AS AnchorIdent 
        , Ident1
        , Ident2
        , ',' || Ident1 || ',' || Ident2 || ',' AS IdentPath
        , 1 AS Lvl
    FROM 
        CTE_Pairs
        INNER JOIN CTE_Idents ON CTE_Idents.Ident = CTE_Pairs.Ident1

    UNION ALL

    SELECT 
        CTE_Recursive.AnchorIdent 
        , CTE_Pairs.Ident1
        , CTE_Pairs.Ident2
        , CTE_Recursive.IdentPath || CTE_Pairs.Ident2 || ',' AS IdentPath
        , CTE_Recursive.Lvl + 1 AS Lvl
    FROM
        CTE_Pairs
        INNER JOIN CTE_Recursive ON CTE_Recursive.Ident2 = CTE_Pairs.Ident1
    WHERE
        CTE_Recursive.IdentPath NOT LIKE ('%,' || CTE_Pairs.Ident2 || ',%')
)
,CTE_RecursionResult
AS
(
    SELECT AnchorIdent, Ident1, Ident2
    FROM CTE_Recursive
)
,CTE_CleanResult
AS
(
    SELECT AnchorIdent, Ident1 AS Ident
    FROM CTE_RecursionResult

    UNION

    SELECT AnchorIdent, Ident2 AS Ident
    FROM CTE_RecursionResult
)
,CTE_Groups
AS
(
  SELECT
    CTE_Idents.Ident
    ,array_agg(COALESCE(CTE_CleanResult.Ident, CTE_Idents.Ident) 
        ORDER BY COALESCE(CTE_CleanResult.Ident, CTE_Idents.Ident)) AS AllIdents
  FROM
    CTE_Idents
    LEFT JOIN CTE_CleanResult ON CTE_CleanResult.AnchorIdent = CTE_Idents.Ident
  GROUP BY CTE_Idents.Ident
)
SELECT AllIdents
FROM CTE_Groups
GROUP BY AllIdents
;

Tôi đã thêm một hàng (7,X,Y) vào dữ liệu mẫu của bạn.

SQL Fiddle

Kết quả

|          allidents |
|--------------------|
|   Lydia,Mary,Nancy |
| Albert,Bob,Charles |
|                X,Y |
|                Zoe |