Алгоритм разбиения на группы двух связанных множеств

[rockclimber]

Есть таблица примерно такого вида:

 columnA    columnB
      A          1
      B          1
      B          2
      C          2
      C          3
      D          4
      D          5
      E          5
      E          6

Надо разбить строки таблицы на группы таким образом, чтобы никакие две группы не содержали общих элементов:

 columnA    columnB   group
      A          1       1
      B          1       1
      B          2       1
      C          2       1
      C          3       1
      D          4       2
      D          5       2
      E          5       2
      E          6       2

В данном случае группа 1 содержит строки, в которых в первом столбце встречается A, B и C, а во втором - 1, 2 и 3. Группа 2 содержит D, E и 4, 5, 6 соответственно.
Сам алгоритм я более-менее представляю, как реализовать.
Но задача осложняется тем, что алгоритм надо реализовать на SQL, исходных данных будет много (десятки тысяч строк), а алгоритм использует рекурсию. А рекурсия в SQL при таких объемах часто требует слишком много времени работы (а то и просто можно всю память выбрать). Если существуют алгоритмы без рекурсии, буду благодарен за подсказку.

[venco]

Ищите "поиск связных компонент в ширину", или "BFS (breadth-first search) of connected components".

[Alexu007]

Ничё не понимаю. Последовательно проходим всю таблицу от начала до конца, где тут прикрутить рекурсию?

[rockclimber]

Alexu007 в сообщении #944639 писал(а):

Ничё не понимаю. Последовательно проходим всю таблицу от начала до конца, где тут прикрутить рекурсию?

Чтобы пройти последовательно, надо сначала расположить строки в правильной последовательности. В моем примере это только для наглядности сделано, в реальных данных такого нет.
Но если все так просто - напишите SQL запрос. Без CONNECT BY и Recursive WITH, желательно, но на худой конец и с ними пойдет.

-- 12.12.2014, 02:24 --

venco
Спасибо. Посмотрел по диагонали - показалось, что задача, видимо, не совсем для SQL. Завтра буду в деталях разбираться.

[rockclimber]

Если вдруг кому интересно - решение я нашел еще пару лет назад. Не шибко производительное (мягко говоря), с рекурсией, но зато на SQL. Требуется Oracle 11.2 или выше.

with t as (select 'A' a, 1 b from dual union all
           select 'B' a, 1 b from dual union all
           select 'B' a, 2 b from dual union all
           select 'C' a, 2 b from dual union all
           select 'C' a, 3 b from dual union all
           select 'D' a, 4 b from dual union all
           select 'D' a, 5 b from dual union all
           select 'E' a, 5 b from dual union all
           select 'E' a, 6 b from dual),
     s (a, b, root_a) as (
        select a, b, connect_by_root a root_a
                from t
             connect by nocycle (prior a =  a and prior b <> b)
                             or (prior a <> a and prior b =  b))
  select root_a, listagg(a, ',') within group (order by a) a_list
          from (select distinct root_a, a
                  from s)
         group by root_a;

Результат:

ColumnA   Group
A         A,B,C
B         A,B,C
C         A,B,C
D         D,E
E         D,E