x
login about faq Site discussion (meta-askssc)

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                    
more ▼

asked May 27 '10 at 06:25 AM in Default

Plectrum gravatar image

Plectrum
1 1 1 1

what is the version of SQL Server are you using ?

May 27 '10 at 10:48 AM Squirrel 1

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.

May 27 '10 at 11:19 AM Plectrum
(comments are locked)
10|1200 characters needed characters left

1 answer: sort newest

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            
more ▼

answered May 28 '10 at 07:32 PM

Scot Hauder gravatar image

Scot Hauder
5.7k 13 15 18

(comments are locked)
10|1200 characters needed characters left
Your answer
toggle preview:

Up to 2 attachments (including images) can be used with a maximum of 524.3 kB each and 1.0 MB total.

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments



Facebook logo Follow Ask SSC on Facebook
Find Ask SSC on Google+
linkedin logo Find us on LinkedIn

Topics:

x321
x13
x4

asked: May 27 '10 at 06:25 AM

Seen: 619 times

Last Updated: Jun 01 '10 at 10:07 PM

Copyright © 2002-2012 Simple Talk Publishing. All Rights Reserved. If you have any queries, please contact the site administrators.
Ask SQL Server Central is a community service provided by Red Gate.