すべてのペアがミラーリングされた組み合わせにも存在すると仮定します(4,5) および(5,4) 。ただし、次のソリューションは、ミラーリングされた複製がなくても機能します。
単純なケース
すべての接続は、単一の昇順で並べることができます fiddle で追加したような複雑な問題 不可能な場合は、rCTEで重複することなくこのソリューションを使用できます：
最小のa_snoを取得することから始めます グループごとに、関連する最小のb_sno ：
SELECT row_number() OVER (ORDER BY a_sno) AS grp
, a_sno, min(b_sno) AS b_sno
FROM data d
WHERE a_sno < b_sno
AND NOT EXISTS (
SELECT 1 FROM data
WHERE b_sno = d.a_sno
AND a_sno < b_sno
)
GROUP BY a_sno;
ウィンドウ関数は集合体上に構築できるため、これには単一のクエリレベルのみが必要です。
結果：
grp a_sno b_sno
1 4 5
2 9 10
3 11 15
分岐や重複した（乗算された）行を避けます-潜在的に多く 長いチェーンではより高価です。 ORDER BY b_sno LIMIT 1を使用しています 相関サブクエリで、再帰CTEでこれを実行します。
パフォーマンスの鍵は、PK制約PRIMARY KEY (a_sno,b_sno)によって提供されるマッチングインデックスです。 ： (b_sno, a_sno)の逆ではありません ：
WITH RECURSIVE t AS (
SELECT row_number() OVER (ORDER BY d.a_sno) AS grp
, a_sno, min(b_sno) AS b_sno -- the smallest one
FROM data d
WHERE a_sno < b_sno
AND NOT EXISTS (
SELECT 1 FROM data
WHERE b_sno = d.a_sno
AND a_sno < b_sno
)
GROUP BY a_sno
)
, cte AS (
SELECT grp, b_sno AS sno FROM t
UNION ALL
SELECT c.grp
, (SELECT b_sno -- correlated subquery
FROM data
WHERE a_sno = c.sno
AND a_sno < b_sno
ORDER BY b_sno
LIMIT 1)
FROM cte c
WHERE c.sno IS NOT NULL
)
SELECT * FROM cte
WHERE sno IS NOT NULL -- eliminate row with NULL
UNION ALL -- no duplicates
SELECT grp, a_sno FROM t
ORDER BY grp, sno;
あまり単純でないケース
ルートから1つ以上のブランチを使用して、すべてのノードに昇順で到達できます（最小のsno 。
今回は、すべてを取得します より大きなsno UNIONで複数回アクセスされる可能性のあるノードの重複を排除します 最後に：
WITH RECURSIVE t AS (
SELECT rank() OVER (ORDER BY d.a_sno) AS grp
, a_sno, b_sno -- get all rows for smallest a_sno
FROM data d
WHERE a_sno < b_sno
AND NOT EXISTS (
SELECT 1 FROM data
WHERE b_sno = d.a_sno
AND a_sno < b_sno
)
)
, cte AS (
SELECT grp, b_sno AS sno FROM t
UNION ALL
SELECT c.grp, d.b_sno
FROM cte c
JOIN data d ON d.a_sno = c.sno
AND d.a_sno < d.b_sno -- join to all connected rows
)
SELECT grp, sno FROM cte
UNION -- eliminate duplicates
SELECT grp, a_sno FROM t -- add first rows
ORDER BY grp, sno;
最初のソリューションとは異なり、ここではNULLの最後の行を取得しません（相関サブクエリが原因です）。
どちらも非常にうまく機能するはずです-特に長いチェーン/多くのブランチで。希望どおりの結果：
SQLフィドル （難易度を示すために行が追加されています）。
無向グラフ
昇順トラバーサルでルートから到達できない極小値がある場合、上記の解決策は機能しません。 Farhęgのソリューション を検討してください この場合。