スパニングツリー（WITH RECURSIVE、PostgreSQL 9.5）の検索

Question

私は任意の人数のテーブルidentities（エイリアス）を持っています。各行には以前の名前と新しい名前があります。プロダクションでは、約1M行あります。たとえば：

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 

私は、ユーザーごとにアイデンティティのフルセット（すなわち、スパニングツリー）を生成するために行うには何が必要ですか？

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に適合させました。

パスをtext列に連結する代わりに、Postgres配列機能を使用して効率的に書き込むことができます。

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 
; 

サンプルデータに1行追加しました。(7,X,Y)

SQL Fiddle

結果

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