En supposant que toutes les paires existent également dans leur combinaison en miroir (4,5) et (5,4) . Mais les solutions suivantes fonctionnent tout aussi bien sans doublons en miroir.
Cas simple
Toutes les connexions peuvent être alignées dans une séquence ascendante unique et des complications comme j'ai ajouté dans le violon ne sont pas possibles, nous pouvons utiliser cette solution sans doublons dans le rCTE :
Je commence par obtenir au minimum a_sno par groupe, avec le b_sno minimum associé :
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;
Cela ne nécessite qu'un seul niveau de requête puisqu'une fonction de fenêtre peut être construite sur un agrégat :
Résultat :
grp a_sno b_sno
1 4 5
2 9 10
3 11 15
J'évite les branches et les lignes dupliquées (multipliquées) - potentiellement beaucoup plus cher avec de longues chaînes. J'utilise ORDER BY b_sno LIMIT 1 dans une sous-requête corrélée pour faire voler cela dans un CTE récursif.
La clé de la performance est un index correspondant, qui est déjà présent fourni par la contrainte PK PRIMARY KEY (a_sno,b_sno) :pas l'inverse (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;
Cas moins simple
Tous les nœuds peuvent être atteints dans l'ordre croissant avec une ou plusieurs branches à partir de la racine (le plus petit sno ).
Cette fois, obtenez tous plus grand sno et dédupliquer les nœuds qui peuvent être visités plusieurs fois avec UNION à la fin :
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;
Contrairement à la première solution, nous n'obtenons pas ici une dernière ligne avec NULL (causée par la sous-requête corrélée).
Les deux devraient très bien fonctionner - en particulier avec de longues chaînes / de nombreuses branches. Résultat souhaité :
SQL Fiddle (avec des rangées ajoutées pour démontrer la difficulté).
Graphe non orienté
S'il existe des minima locaux qui ne peuvent pas être atteints à partir de la racine avec une traversée ascendante, les solutions ci-dessus ne fonctionneront pas. Considérez la solution de Farhęg dans ce cas.
