Combining match groups

I have a table that represents a series of matches between IDs from another table like this:

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 directly or indirectly related to each other.

The result will 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 added one more line:

insert into #matches values (7,8)

      

then that would mean 2 of the above groups would be linked, so I would need an 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 think that a recursive generic table expression should do the trick ... if I figure out something elegant, I'll post it

+1


source to share


3 answers


It looks like Disjoint-set is what you need to solve. Here is a list of C # and C ++ implementations.



+1


source


If it can be done in SQL at all, it will be insanely difficult. You must parse this table in whatever programming language you are using.



0


source


If you are using Oracle the CONNECT TO command is great. Tom Keith has a good entry on this, answering what seems to be essentially the same question:

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

Check out the Expanding the Hierarchy section.

0


source







All Articles