views:

83

answers:

3

I have a table that represents a series of matches between ids from another table as follows:

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)

and I want to find groups of matches that are linked directly or indirectly to one another.

The output would look like this:

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

if I were to add another row:

insert into #matches values (7,8)

then this would mean that 2 of the groups above would be linked, so I would require output:

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

Any ideas?

Edit: Further research leads me to believe that a recursive common table expression should do the trick... if I figure out something elegant I'll post it

+1  A: 

It appears that a Disjoint-set is what you need to solve this. Here is a listing of a C# and C++ implementation.

EndangeredMassa
this algo turned out to be exactly the kind of thing we were after. many thanks for pointing me in the right direction. the sql version is still pending :)
spender
No problem! I had to implement my own C++ version in college. That's the only reason I remembered what it even was.
EndangeredMassa
A: 

If this can be done at all within SQL, it's going to be insanely difficult. You should analyze that table in whatever programming language you're using.

chaos
A: 

If you're using Oracle, the CONNECT TO command is brilliant. Tom Kyte has a nice writeup about this, answering what appears to be essentially your same question:

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

Check out the section "Hierarchy Expansion".

Jamie Love
Unfortunately we're using MSSQL... otherwise it would be the perfect solution.
spender