Suchen der Spanning-Gesamtstruktur (MIT RECURSIVE, PostgreSQL 9.5)

Question

Ich habe eine Tabelle identities (d. H. Aliase) für eine beliebige Anzahl von Personen. Jede Zeile hat einen vorherigen Namen und einen neuen Namen. In der Produktion gibt es etwa 1 M Reihen. Zum Beispiel:

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

Was ich will ist die Liste der users und verweisen alle ihre jeweiligen Identitäten zu generieren. Dies ist analog zu allen Knoten in jeder graphischen Darstellung der verbundenen Identitäten zu finden, oder der Suche nach den Spanning Wald:

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

Ich habe mit PostgreSQL bastelt WITH RECURSIVE, aber es ergibt sich beide Sätze und Teilsätze für jeden. Zum Beispiel:

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

Was muß ich tun, um nur die vollständigen Sätze von Identitäten zu erzeugen (das heißt der Spanning-Tree) für jeden Benutzer?

SQLFiddle: http://sqlfiddle.com/#!15/9eaed/4 mit meinem neuesten Versuch. Hier ist der Code:

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; 

Und die Ergebnisse:

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

Answer 1

ich eine Antwort auf eine ähnliche Frage vor einer Weile geschrieben: How to find all connected subgraphs of an undirected graph. In dieser Frage habe ich SQL Server verwendet. Siehe diese Antwort für eine detaillierte Erläuterung der Zwischen-CTEs. Ich habe diese Abfrage an Postgres angepasst.

Es kann effizienter mit Postgres-Array-Funktion geschrieben werden, anstatt den Pfad in eine text-Spalte verketten.

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 
; 

Ich fügte eine Zeile (7,X,Y) zu Ihren Beispieldaten hinzu.

SQL Fiddle

Ergebnis

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