x

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&lt;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 voted first

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.9k 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.

New code box

There's a new way to format code on the site - the red speech bubble logo will automatically format T-SQL for you. The original code box is still there for XML, etc. More details here.

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

SQL Server Central

Need long-form SQL discussion? SQLserverCentral.com is the place.

Topics:

x362
x14
x4

asked: May 27 '10 at 06:25 AM

Seen: 871 times

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