связывание групп матчей

Question

У меня есть таблица, которая представляет серию совпадений между идентификаторами из другой таблицы следующим образом:

CREATE TABLE #matches (
  asid1 int,
  asid2 int
)

insert into #matches values (1,2)
insert into #matches values (1,3)
insert into #matches values (3,1)
insert into #matches values (3,4)
insert into #matches values (7,6)
insert into #matches values (5,7)
insert into #matches values (8,1)
insert into #matches values (1,8)
insert into #matches values (8,9)
insert into #matches values (8,3)
insert into #matches values (10,11)
insert into #matches values (12,10)

и я хочу найти группы совпадений, которые прямо или косвенно связаны друг с другом.

Вывод будет выглядеть так:

group  asid
1      1
1      2
1      3
1      4
1      8
1      9
2      5
2      6
2      7
3      10
3      11
3      12

если бы я добавил еще одну строку:

insert into #matches values (7,8)

тогда это будет означать, что 2 из вышеуказанных групп будут связаны, поэтому мне потребуется вывод:

group  asid
1      1
1      2
1      3
1      4
1      5
1      6
1      7
1      8
1      9
2      10
2      11
2      12

Есть идеи?

Редактировать: Дальнейшие исследования приводят меня к мысли, что рекурсивное общее табличное выражение должно сработать ... если я найду что-нибудь элегантное, я опубликую это

Answer 1

Похоже, что Disjoint-set - это то, что вам нужно для решения этой проблемы. Вот список реализации C # и C ++.

Answer 2

Если вы используете Oracle, команда CONNECT TO великолепна. У Тома Кайта есть хорошая статья по этому поводу, и он отвечает на то, что, по сути, является вашим вопросом:

http://www.oracle.com/technology/oramag/oracle/05-may/o35asktom.html

Ознакомьтесь с разделом «Расширение иерархии».

Answer 3

Если это вообще можно сделать в SQL, это будет безумно сложно. Вы должны проанализировать эту таблицу на любом языке программирования, который вы используете.