3

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

2
  • 1 is linked to 3, 3 is linked to 4 therefore 1 is linked to 4 because there is a common link to 3. By the same theory 1 is linked to 5 because of the common link to 3. Hope that makes some sense. No limit on depth and it is SQL Server 2012. The data can have cycles unfortunately.
    – Matt20013
    Mar 26, 2014 at 15:50
  • No limit on depth and it is SQL Server 2012
    – Matt20013
    Mar 26, 2014 at 16:01

1 Answer 1

3

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
2
  • Hi. I checked your code and it not works on cycles or self-links (ex. 3, 3) - no data returns. If the initial set more complex (ex. ( 1, 2 ), ( 1, 3 ), ( 3, 3 ), ( 1, 4 ), ( 5, 7 ), ( 6, 5 ), ( 7, 7 )), the error of max recursion level received.
    – Sandr
    Nov 29, 2016 at 14:15
  • I added this dataset and came out with 2 groups when it should be 1 group. Input: (59, 625), (280,625) Result: group_id id 1 59 1 625 2 280 2 625
    – Rich Le
    Aug 28, 2020 at 3:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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