Поиск остовного леса (WITH RECURSIVE, PostgreSQL 9.5)

Question

У меня есть таблица identities (т. Е. Псевдонимы) для произвольного числа людей. Каждая строка имеет предыдущее имя и новое имя. В производстве имеется около 1 М строк. Например:

id, old, new 
--- 
1, 'Albert', 'Bob' 
2, 'Bob', 'Charles' 
3, 'Mary', 'Nancy' 
4, 'Charles', 'Albert' 
5, 'Lydia', 'Nancy' 
6, 'Zoe', 'Zoe' 

То, что я хочу, чтобы создать список users и ссылки на все их соответствующих идентичностей. Это аналогично нахождение всех узлов в каждом графике подключенных идентичностей, или найти остовный леса:

User 1: Albert, Bob, Charles (identities: 1,2,4) 
User 2: Mary, Nancy, Lydia (identities: 3,5) 
User 3: Zoe (identities: 6) 

Я мастерить с PostgreSQL, WITH RECURSIVE, но она дает оба набор и подмножество для каждого. Например:

1,2,4 <-- spanning tree: good 
2  <-- subset: discard 
3,5 <-- spanning tree: good 
4  <-- subset: discard 
5  <-- subset: discard 
6  <-- spanning tree: good 

Что мне нужно сделать, чтобы производить только полные наборы идентификаторов (т.е. Spanning Tree) для каждого пользователя?

SQLFiddle: http://sqlfiddle.com/#!15/9eaed/4 с моей последней попыткой. Вот код:

WITH RECURSIVE search_graph AS (
    SELECT id 
    , id AS min_id 
    , ARRAY[id] AS path 
    , ARRAY[old,new] AS emails 
    FROM identities 

    UNION 

    SELECT identities.id 
    , LEAST(identities.id, sg.min_id) 
    , (sg.path || identities.id) 
    , (sg.emails || identities.old || identities.new) 

    FROM search_graph sg 
    JOIN identities ON (identities.old = ANY(sg.emails) OR identities.new = ANY(sg.emails)) 
    WHERE identities.id <> ALL(sg.path) 
) 
SELECT array_agg(DISTINCT(p)) from search_graph, unnest(path) p GROUP BY min_id; 

И результаты:

1,2,4 
2 
3,5 
4 
5 
6 

Answer 1

Я написал ответ на аналогичный вопрос некоторое время назад: How to find all connected subgraphs of an undirected graph. В этом вопросе я использовал SQL Server. См. Этот ответ для подробного объяснения промежуточных CTE. Я применил этот запрос к Postgres.

Он может быть написан более эффективно с использованием функции массива Postgres вместо конкатенации пути в столбец text.

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 
; 

Я добавил одну строку (7,X,Y) к вашим данным образца.

SQL Fiddle

Результат

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