Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

I have a table with two id columns id1 and id2. Each row shows that 2 id values have been linked together. My actual data has both id columns as varchar(20) but I have used integers in the example below to illustrate the problem.

id1 id2
--- ---
1    2
1    3
3    4
3    5
6    7

I want to group together ids so that all linked ids are grouped together even if there is not a direct link between 2 id values.

id group_id
-- ----
1   1
2   1
3   1
4   1
5   1
6   2
7   2   

I would like to achieve this in sql without using cursors if possible.

All advice gratefully received.

Update: I thought it would be useful to add a bit more background on the data this represents. The data represents records for businesses sourced from different data sources

The main table looks like this

id business_name postal_address business_classification x y group_id

The main table can contain duplicates / similar records which need to be associated. The table with id1 and id2 columns is a result of de-duplication using fuzzy string matching (levenshtein, word matching etc) and spatial proximity matching. I think that this table is actually an undirected graph containing many disconnected sub graphs e.g. group_id 1 and 2.I want to join all ids in the same network and update the group_id in the main table.

I think that the question is now how to identify all disconnected sub graphs on a graph using SQL server Find All Disconnected Sub Graphs - Java

share|improve this question
    
I don't understand why 1,2,3,4,5 are in group 1, and 6,7 are in group 2. –  Aaron Bertrand Mar 26 at 15:45
4  
How derp can this hierarchy go? –  billinkc Mar 26 at 15:59
1  
Also, which version of SQL Server are you using (please say 2012) –  billinkc Mar 26 at 16:00
1  
Is the data guaranteed to have no cycles? I.e., (1, 2), (2, 3), (3, 1) is not possible? –  Jon Seigel Mar 26 at 17:09
1  
The data can have cycles unfortunately –  Matt20013 Mar 26 at 17:19

1 Answer 1

up vote 0 down vote accepted

Well this worked for the given sample data but not the cycles scenario / may not work for a more complex data set. Thought I would post anyway as a starter for 10:

DECLARE @t TABLE ( id1 INT, id2 INT )

INSERT INTO @t VALUES
    ( 1, 2 ),
    ( 1, 3 ),
    ( 3, 4 ),
    ( 3, 5 ),
    ( 6, 7 )

    --( 1, 2 ),
    --( 2, 3 ),
    --( 3, 1 )

;WITH cte AS
(
SELECT ROW_NUMBER() OVER( ORDER BY id1 ) group_id, id1 id 
FROM @t a
    CROSS APPLY ( SELECT TOP 1 id2 FROM @t c WHERE a.id1 = c.id1 ) d 
WHERE NOT EXISTS ( SELECT * FROM @t b WHERE a.id1 = b.id2 )
  AND a.id2 = d.id2
UNION ALL
SELECT group_id, t.id2
FROM cte c
    INNER JOIN @t t ON c.id = t.id1
)
SELECT *
FROM cte
ORDER BY 1, 2
share|improve this answer
    
This looks great. I have also looked at the cycles. The direction of id1, id2 does not matter in my data set so I can break the cycle by changing the direction using update @t set id1 = id2, id2 = id1 where id2 < id1 which then works with the cycle above. This brings back some duplicates so I changed the final select statement to SELECT distinct id1,id2 FROM cte ORDER BY 1, 2 –  Matt20013 Mar 27 at 10:18
    
That's good news Matt. I did wonder if there might be a simpler way, eg with LAG/LEAD but sometimes it's good to get something working and build on it. –  wBob Mar 27 at 10:33

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.