Agrupamento SQL de linhas de interseção/sobreposição

Supondo que todos os pares existam em sua combinação espelhada também (4,5) e (5,4) . Mas as soluções a seguir também funcionam sem dupes espelhados.

Caso simples

Todas as conexões podem ser alinhadas em uma única sequência ascendente e complicações como eu adicionei no fiddle não são possíveis, podemos usar esta solução sem duplicatas no rCTE:

Começo obtendo o mínimo de a_sno por grupo, com o mínimo associado 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;

Isso precisa apenas de um único nível de consulta, pois uma função de janela pode ser construída em um agregado:

Obtenha a soma distinta de uma coluna de tabela unida

Resultado:

grp  a_sno  b_sno
1    4      5
2    9      10
3    11     15

Evito ramificações e linhas duplicadas (multiplicadas) - potencialmente muito mais caro com cadeias longas. Eu uso ORDER BY b_sno LIMIT 1 em uma subconsulta correlacionada para fazer isso voar em um CTE recursivo.

Crie um índice exclusivo em uma coluna não exclusiva

A chave para o desempenho é um índice de correspondência, que já está presente fornecido pela restrição PK PRIMARY KEY (a_sno,b_sno) :não o contrário ~~(b_sno, a_sno)~~ :

Um índice composto também é bom para consultas no primeiro campo?

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;

Caso menos simples

Todos os nós podem ser alcançados em ordem crescente com um ou mais ramos da raiz (menor sno ).

Desta vez, obtenha todos maior sno e desduplicar nós que podem ser visitados várias vezes com UNION no final:

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;

Ao contrário da primeira solução, não obtemos uma última linha com NULL aqui (causada pela subconsulta correlacionada).

Ambos devem ter um desempenho muito bom - especialmente com cadeias longas/muitos ramos. Resultado conforme desejado:

SQL Fiddle (com linhas adicionadas para demonstrar dificuldade).

Gráfico não direcionado

Se houver mínimos locais que não podem ser alcançados a partir da raiz com travessia ascendente, as soluções acima não funcionarão. Considere a solução da Farhęg nesse caso.