2

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

  • 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 '14 at 15:50
  • No limit on depth and it is SQL Server 2012 – Matt20013 Mar 26 '14 at 16:01
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
| improve this answer | |
  • 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 '16 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 at 3:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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