SQL группирует интересные/перекрывающиеся строки

Предполагая, что все пары существуют в их зеркальной комбинации, а также (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

• Создайте уникальный индекс для неуникального столбца

Ключом к производительности является соответствующий индекс, который уже присутствует в ограничении 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;

Менее простой случай

Все узлы могут быть достигнуты в порядке возрастания с одной или несколькими ветвями от корня (наименьший 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 Fiddle (с добавленными строками для демонстрации сложности).

Неориентированный граф

Если есть локальные минимумы, которые не могут быть достигнуты из корня при обходе по возрастанию, приведенные выше решения не будут работать. В этом случае рассмотрим решение Farhęg.

Хочу сказать по другому, может пригодится, сделать можно в 2 шага:

1. возьмите max(sno) за каждую группу:

  select q.sno,
         row_number() over(order by q.sno) gn
  from(
    select distinct d.a_sno sno
    from data d
    where not exists (
      select b_sno
      from data
      where b_sno=d.a_sno
      and a_sno>d.a_sno
     )
    )q

результат:

sno gn
7   1
14  2
15  3

2. используйте recursive cte, чтобы найти всех связанных участников в группах:

with recursive cte(sno,gn,path,cycle)as(
  select q.sno,
         row_number() over(order by q.sno) gn,
         array[q.sno],false
  from(
    select distinct d.a_sno sno
    from data d
    where not exists (
      select b_sno
      from data
      where b_sno=d.a_sno
      and a_sno>d.a_sno
     )
    )q
  union all
  select d.a_sno,c.gn,
         d.a_sno || c.path,
         d.a_sno=any(c.path)
  from data d
  join cte c on d.b_sno=c.sno 
  where not cycle
 )
 select distinct gn,sno from cte
 order by gn,sno

Результат:

gn  sno
1   4
1   5
1   6
1   7
2   9
2   10
2   13
2   14
3   11
3   15

вот демонстрация того, что я сделал.

Вот начало, которое может дать некоторые идеи о подходе. Рекурсивный запрос начинается с a_sno каждой записи, а затем пытается следовать по пути b_sno, пока не достигнет конца или не сформирует цикл. Путь представлен массивом из sno целых чисел.

Функция unnest разбивает массив на строки, поэтому значение sno сопоставляется с массивом путей, например:

4, {6, 5, 4}

будет преобразован в строку для каждого значения в массиве:

4, 6
4, 5
4, 4

Затем array_agg меняет операцию, объединяя значения обратно в путь, но избавляясь от дубликатов и упорядочения.

Теперь каждый a_sno связан с путем, и путь образует группу. dense_rank можно использовать для сопоставления группировки (кластера) с числовым значением.

SELECT array_agg(DISTINCT map ORDER BY map) AS cluster
      ,sno
  FROM ( WITH RECURSIVE x(sno, path, cycle) AS (
             SELECT a_sno, ARRAY[a_sno], false FROM  data
             UNION ALL
             SELECT b_sno, path || b_sno, b_sno = ANY(path)
               FROM data, x
               WHERE a_sno = x.sno
                 AND NOT cycle
         )
         SELECT sno, unnest(path) AS map FROM x ORDER BY 1
       ) y
  GROUP BY sno
  ORDER BY 1, 2

Выход:

   cluster    | sno 
--------------+-----
 {4,5,6,7}    |   4
 {4,5,6,7}    |   5
 {4,5,6,7}    |   6
 {4,5,6,7}    |   7
 {9,10,13,14} |   9
 {9,10,13,14} |  10
 {9,10,13,14} |  13
 {9,10,13,14} |  14
 {11,15}      |  11
 {11,15}      |  15
(10 rows)

Оберните это еще раз для рейтинга:

SELECT dense_rank() OVER(order by cluster) AS rank
      ,sno
  FROM (
    SELECT array_agg(DISTINCT map ORDER BY map) AS cluster
          ,sno
      FROM ( WITH RECURSIVE x(sno, path, cycle) AS (
                 SELECT a_sno, ARRAY[a_sno], false FROM  data
                 UNION ALL
                 SELECT b_sno, path || b_sno, b_sno = ANY(path)
                   FROM data, x
                   WHERE a_sno = x.sno
                     AND NOT cycle
             )
             SELECT sno, unnest(path) AS map FROM x ORDER BY 1
           ) y
      GROUP BY sno
      ORDER BY 1, 2
) z

Выход:

 rank | sno 
------+-----
    1 |   4
    1 |   5
    1 |   6
    1 |   7
    2 |   9
    2 |  10
    2 |  13
    2 |  14
    3 |  11
    3 |  15
(10 rows)