create a group for objects related to one another

Question

question

Plectrum asked May 27, '10

create a group for objects related to one another

I would like to know the most efficient way to create a group for objects related to one another. The data is in the form:

ObjectId1   ObjectId2                    
1           2                    
2           1                    
1           1                    
3           2                    
2           3                    
3           3

So 1 is related to 2 (and all objects are related to themselves) and 3 is related to 2. As both 1 and 3 are related to 2, I would like to know they are also related to each other. So the final output would be:

Group   ObjectId                    
A       1                    
A       2                    
A       3

The group doesn't have to be called a letter, I've just used this as an example to show it's not an object id.

The solution I have come up with is below, but it doesn't seem as efficient as it could be and over complicated:

--sample data                    
DECLARE @Links TABLE(                    
    ObjectId1 int,                    
    ObjectId2 int,                    
    Primary Key(ObjectId1,ObjectId2)                    
)                    
                    
INSERT INTO @Links                    
SELECT 1,2 UNION ALL SELECT 1,1 UNION ALL SELECT 2,3 UNION ALL SELECT 2,1 UNION ALL SELECT 2,2 UNION ALL                     
SELECT 3,2 UNION ALL SELECT 3,3 UNION ALL SELECT 3,4 UNION ALL SELECT 4,3 UNION ALL SELECT 4,4 UNION ALL                     
SELECT 4,5 UNION ALL SELECT 5,5 UNION ALL SELECT 5,4 UNION ALL SELECT 1,6 UNION ALL SELECT 6,1 UNION ALL                     
SELECT 6,2 UNION ALL SELECT 2,6 UNION ALL SELECT 6,6 UNION ALL SELECT 5,7 UNION ALL SELECT 7,5 UNION ALL                     
SELECT 7,7 UNION ALL SELECT 8,8 UNION ALL SELECT 9,9 UNION ALL SELECT 10,9 UNION ALL SELECT 9,10 UNION ALL                     
SELECT 10,3 UNION ALL SELECT 3,10 UNION ALL SELECT 15,16 UNION ALL SELECT 16,15 UNION ALL SELECT 1,5 UNION ALL                     
SELECT 4,1 UNION ALL SELECT 10,10 UNION ALL SELECT 15,15 UNION ALL SELECT 16,16                     
                    
                    
                    
--get rid of duplicate information, only take one link between two objects                    
DECLARE @TempGroups TABLE(                    
    ObjectId int,                    
    LowestObjectId int                    
)                    
                    
INSERT INTO @TempGroups                    
SELECT ObjectId2,ObjectId1                     
FROM @Links                    
WHERE ObjectId1<ObjectId2                    
                    
                    
                    
--loop relates all groups to the same lowestid                    
DECLARE @UpdateRows int                    
SET @UpdateRows=1                    
                    
WHILE @UpdateRows>0 --run until now further updates                    
BEGIN                    
                    
    --relates lowestids to ids                    
                    
    --i.e.                    
    --lowestid  id                    
    --1         2                    
    --2         3                    
    --goes to                    
    --1         2                    
    --1         3                    
    UPDATE High                    
    SET LowestObjectId=Low.LowestObjectId                       
    FROM                    
        @TempGroups Low                    
            JOIN                    
                @TempGroups High ON                    
                    Low.ObjectId=High.LowestObjectId                    
    SET @UpdateRows=@@Rowcount                    
                    
                    
    --relates ids                    
    --i.e.                    
    --lowestid  id                    
    --1         3                    
    --2         3                    
    --goes to                    
    --1         3                    
    --1         2                    
    UPDATE High                    
    SET LowestObjectId=Low.LowestObjectId,ObjectId=High.LowestObjectId                    
    FROM                    
        @TempGroups Low                    
            JOIN                    
                @TempGroups High ON                    
                    Low.ObjectId=High.ObjectId                    
                    AND                    
                    Low.LowestObjectId<High.LowestObjectId                    
                    
    SET @UpdateRows=@UpdateRows+@@Rowcount                    
END                    
                    
--get into final form                    
DECLARE @Groups TABLE(                    
    ObjectId int,                    
    GroupId int,                    
    Primary Key(ObjectId)                    
)                    
                    
--only show unique results                    
INSERT INTO @Groups                    
SELECT DISTINCT ObjectId,LowestObjectId FROM @TempGroups                    
                    
--lowest object ids belong to their own groups                    
INSERT INTO @Groups                    
SELECT DISTINCT LowestObjectId,LowestObjectId FROM @TempGroups                    
                    
--not really needed but creates arbitary group ids rather than those based on object ids                    
UPDATE G                    
SET GroupId=NG.NewGroupId                    
FROM                    
    @Groups G                    
        JOIN                    
            (                    
                SELECT DISTINCT                    
                    GroupId,                    
                    NewGroupId=DENSE_RANK() OVER(ORDER BY GroupId)                    
                FROM                    
                    @Groups                    
            ) NG ON                    
                NG.GroupId=G.GroupId                    
                    
--show results                    
SELECT * FROM @Groups

query hierarchical-query hierarchyid

2

10 |1200

Attachments: Up to 2 attachments (including images) can be used with a maximum of 512.0 KiB each and 1.0 MiB total.

Squirrel 1 commented · May 27, 2010 at 10:48 AM

what is the version of SQL Server are you using ?

0 ·

Plectrum commented · May 27, 2010 at 11:19 AM

SQL 2008. I've written this query so it works in 2005 and possibly 2000 as perhaps there was a solution that wasn't version dependent. I'm happy to use a 2008 specific solution though.

0 ·

Answer 1 · 2010-05-28T19:32:41Z

Scot Hauder answered May 28, '10

You could use an hierarchyid and do something like this:

            
CREATE TABLE #ObjectRelationship            
(            
     ObjectNode hierarchyid PRIMARY KEY CLUSTERED            
    ,ParentNode AS ObjectNode.GetAncestor(1) PERSISTED            
    ,[Level] AS ObjectNode.GetLevel() PERSISTED            
    ,ObjectID int            
)            
CREATE UNIQUE INDEX idxLevelObjectNode ON #ObjectRelationship([Level], ObjectNode)            
            
INSERT #ObjectRelationship (ObjectNode, ObjectID)            
SELECT '/1/',1 union             
SELECT '/1/2/',2 union             
SELECT '/1/5/',5 union             
SELECT '/1/6/',6 union             
SELECT '/1/2/3/',3 union             
SELECT '/1/2/6/',6 union             
SELECT '/1/2/3/4/',4 union             
SELECT '/1/2/3/10/',10 union             
SELECT '/1/2/3/4/5/',5 union             
SELECT '/1/2/3/4/5/7/',7 union             
SELECT '/9/',9 union             
SELECT '/9/10/',10 union             
SELECT '/15/',15 union            
SELECT '/15/16/',16             
            
            
SELECT DISTINCT x.ObjectID, [GroupID] = DENSE_RANK() OVER(ORDER BY ParentNode)            
FROM #ObjectRelationship [ObjRel]            
CROSS APPLY (SELECT ObjectID FROM #ObjectRelationship            
             WHERE 1 = ObjectNode.IsDescendantOf([ObjRel].ParentNode)) [x]            
WHERE [Level] = 2            
ORDER BY GroupID, ObjectID            
            
DROP TABLE #ObjectRelationship

10 |1200

Attachments: Up to 2 attachments (including images) can be used with a maximum of 512.0 KiB each and 1.0 MiB total.

question