Click here to monitor SSC
SQLServerCentral is supported by Red Gate Software Ltd.
 
Log in  ::  Register  ::  Not logged in
 
 
 
        
Home       Members    Calendar    Who's On


Add to briefcase 12»»

Multiple parents tree (or digraph) implementation Expand / Collapse
Author
Message
Posted Tuesday, May 12, 2009 8:55 PM
Grasshopper

GrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopper

Group: General Forum Members
Last Login: Friday, April 23, 2010 4:57 PM
Points: 11, Visits: 27
Hi guys,
I need to implement a multi-parented tree (or digraph) onto SQL Server 2005.
I've read several articles, but most of them uses single-parented trees with a unique root like the following one.
-My PC
-Drive C
-Documents and Settings
-Program Files
-Adobe
-Microsoft
-Folder X
-Drive D
-Folder Y
-Folder Z

In this one, everything derives from a root element (My PC).

In my case, a child could have more than 1 parent, like the following:
G  A
\ /
B
/ \
X C
/ \
D E
\ /
F

So I have the following code:
create table #ObjectRelations
(
Id varchar(20),
NextId varchar(20)
)

insert into #ObjectRelations values ('G', 'B')
insert into #ObjectRelations values ('A', 'B')
insert into #ObjectRelations values ('B', 'C')
insert into #ObjectRelations values ('B', 'X')
insert into #ObjectRelations values ('C', 'E')
insert into #ObjectRelations values ('C', 'D')
insert into #ObjectRelations values ('E', 'F')
insert into #ObjectRelations values ('D', 'F')

declare @id varchar(20)
set @id = 'A';

WITH Objects (Id, NextId) AS
( -- This is the 'Anchor' or starting point of the recursive query
SELECT rel.Id,
rel.NextId
FROM #ObjectRelations rel
WHERE rel.Id = @id
UNION ALL -- This is the recursive portion of the query
SELECT rel.Id,
rel.NextId
FROM #ObjectRelations rel
INNER JOIN Objects -- Note the reference to CTE table name (Recursive Join)
ON rel.Id = Objects.NextId
)
SELECT o.*
FROM Objects o

drop table #ObjectRelations
----------------------------------------

Which returns the following SET:
Id                   NextId
-------------------- --------------------
A B
B C
B X
C E
C D
D F
E F

Expected result SET:
Id                   NextId
-------------------- --------------------
G B
A B
B C
B X
C E
C D
D F
E F

Note that the relation G->B is missing, because it asks for an starting object (which doesn't work for me also, because I don't know the root object from the start) and using A as the start point will ignore the G->B relationship.

So, this code doesn't work in my case because it asks for a starting object, which is obvious in a SINGLE-parent tree (will always be the root object). But in multi-parent tree, you could have more than 1 "root" object (like in the example, G and A are the "root" objects, where root is an object which doesn't have a parent (ancestor)).

So I'm kind of stucked in here... I need to modify the query to NOT ask for a starting object and recursively traverse the entire tree.
I don't know if that's possible with the (Id, NextId) implementation... may be I need to store it like a graph using some kind of Incidence matrix, adjacency matrix or whatever (see http://willets.org/sqlgraphs.html).

Any help? What do you think guys?
Thank you very much for your time =)

Cheers!

Sources:
http://www.sqlservercentral.com/articles/SQL+Server+2005+-+TSQL/recursivequeriesinsql1999andsqlserver2005/1846/
http://www.rcs-solutions.com/blog/2008/09/27/RecursiveQueriesInSQLServer2005.aspx
http://www.experts-exchange.com/Database/Miscellaneous/Q_23102605.html

Post #715602
Posted Tuesday, May 12, 2009 9:22 PM


Ten Centuries

Ten CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen Centuries

Group: General Forum Members
Last Login: Thursday, May 9, 2013 8:07 AM
Points: 1,221, Visits: 2,614
This may help some. I am using an OR in the anchor to use multiple anchors. You still would need to know what the anchors are somehow before running the query.

create table #ObjectRelations
(

Id varchar(20),

NextId varchar(20)
)
insert into #ObjectRelations values ('G', 'B')
insert into #ObjectRelations values ('A', 'B')
insert into #ObjectRelations values ('B', 'C')
insert into #ObjectRelations values ('B', 'X')
insert into #ObjectRelations values ('C', 'E')
insert into #ObjectRelations values ('C', 'D')
insert into #ObjectRelations values ('E', 'F')
insert into #ObjectRelations values ('D', 'F')

;
WITH Objects (Id, NextId) AS
( -- This is the 'Anchor' or starting point of the recursive query

SELECT rel.Id,
rel.NextId
FROM #ObjectRelations rel
WHERE rel.Id = 'A' OR rel.Id = 'G'

UNION ALL -- This is the recursive portion of the query

SELECT rel.Id,
rel.NextId
FROM #ObjectRelations rel
INNER JOIN Objects -- Note the reference to CTE table name (Recursive Join)
ON rel.Id = Objects.NextId
)

SELECT distinct o.*
FROM Objects o

drop table #ObjectRelations
----------------------------------------



Ken Simmons
http://twitter.com/KenSimmons
Post #715610
Posted Tuesday, May 12, 2009 9:49 PM
Grasshopper

GrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopper

Group: General Forum Members
Last Login: Friday, April 23, 2010 4:57 PM
Points: 11, Visits: 27
Yes, that could work. I've tried that, I think I can determine the starting objects in first place...

What it's not satisfying me is that G->B is the last row and in the expected set it should be in the 1st or 2nd position. I don't know yet if not being "well-ordered" is going to work for me.

But thanks for the quick answer!
Post #715620
Posted Tuesday, May 12, 2009 10:02 PM


SSCrazy Eights

SSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy Eights

Group: General Forum Members
Last Login: Thursday, June 5, 2014 10:54 AM
Points: 9,902, Visits: 9,480
Which is it, a multi-parent tree or a digraph? They are not the same thing.

In particular, a multi-parent tree would be a digraph that is connected and has no cycles. A digraph is not necessarily connected and can have cycles.


-- RBarryYoung, (302)375-0451 blog: MovingSQL.com, Twitter: @RBarryYoung
Proactive Performance Solutions, Inc.
"Performance is our middle name."
Post #715627
Posted Tuesday, May 12, 2009 10:12 PM
Grasshopper

GrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopper

Group: General Forum Members
Last Login: Friday, April 23, 2010 4:57 PM
Points: 11, Visits: 27
You're right, they're not the same thing.

It's a multi-parent tree. It doesn't have cycles and it's connected.

Sorry for the mislabeling in the topic title
Post #715630
Posted Tuesday, May 12, 2009 10:22 PM


Ten Centuries

Ten CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen Centuries

Group: General Forum Members
Last Login: Thursday, May 9, 2013 8:07 AM
Points: 1,221, Visits: 2,614
How about adding a level for the ordering.

create table #ObjectRelations
(

Id varchar(20),

NextId varchar(20)
)
insert into #ObjectRelations values ('G', 'B')
insert into #ObjectRelations values ('A', 'B')
insert into #ObjectRelations values ('B', 'C')
insert into #ObjectRelations values ('B', 'X')
insert into #ObjectRelations values ('C', 'E')
insert into #ObjectRelations values ('C', 'D')
insert into #ObjectRelations values ('E', 'F')
insert into #ObjectRelations values ('D', 'F')

;
WITH Objects --(lvl, Id, NextId)
AS
( -- This is the 'Anchor' or starting point of the recursive query

SELECT 1 AS Lvl,
rel.Id,
rel.NextId
FROM #ObjectRelations rel
WHERE rel.Id = 'A' OR rel.Id = 'G'

UNION ALL -- This is the recursive portion of the query

SELECT lvl + 1,
rel.Id,
rel.NextId
FROM #ObjectRelations rel
INNER JOIN Objects -- Note the reference to CTE table name (Recursive Join)
ON rel.Id = Objects.NextId
)

SELECT distinct o.*
FROM Objects o
Order by lvl

drop table #ObjectRelations



Ken Simmons
http://twitter.com/KenSimmons
Post #715635
Posted Tuesday, May 12, 2009 10:22 PM
Grasshopper

GrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopper

Group: General Forum Members
Last Login: Friday, April 23, 2010 4:57 PM
Points: 11, Visits: 27
So I've got this approach:

create table #ObjectRelations
(
Id varchar(20),
NextId varchar(20)
)

insert into #ObjectRelations values ('G', 'B')
insert into #ObjectRelations values ('A', 'B')
insert into #ObjectRelations values ('B', 'C')
insert into #ObjectRelations values ('B', 'X')
insert into #ObjectRelations values ('C', 'E')
insert into #ObjectRelations values ('C', 'D')
insert into #ObjectRelations values ('E', 'F')
insert into #ObjectRelations values ('D', 'F')

declare @startIds table
(
Id varchar(20) primary key
)

;WITH
Ids (Id) AS
(
SELECT Id
FROM #ObjectRelations
),
NextIds (Id) AS
(
SELECT NextId
FROM #ObjectRelations
)
INSERT INTO @startIds
SELECT DISTINCT
Ids.Id
FROM
Ids
LEFT JOIN
NextIds on Ids.Id = NextIds.Id
WHERE
NextIds.Id IS NULL

;WITH Objects (Id, NextId) AS
( -- This is the 'Anchor' or starting point of the recursive query
SELECT rel.Id,
rel.NextId
FROM #ObjectRelations rel
WHERE rel.Id IN (SELECT Id FROM @startIds)
UNION ALL -- This is the recursive portion of the query
SELECT rel.Id,
rel.NextId
FROM #ObjectRelations rel
INNER JOIN Objects -- Note the reference to CTE table name (Recursive Join)
ON rel.Id = Objects.NextId
)
SELECT DISTINCT *
FROM Objects

drop table #ObjectRelations

It determines the starting objects (which are those who doesn't have a parent).
Is there a way to sort the last select to put first the starting objects?
Like
Id                   NextId
------------ --------------
A B
G B
B C
B X
C D
C E
D F
E F

Post #715636
Posted Tuesday, May 12, 2009 10:26 PM
Grasshopper

GrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopper

Group: General Forum Members
Last Login: Friday, April 23, 2010 4:57 PM
Points: 11, Visits: 27
This works!

create table #ObjectRelations
(
Id varchar(20),
NextId varchar(20)
)

insert into #ObjectRelations values ('G', 'B')
insert into #ObjectRelations values ('A', 'B')
insert into #ObjectRelations values ('B', 'C')
insert into #ObjectRelations values ('B', 'X')
insert into #ObjectRelations values ('C', 'E')
insert into #ObjectRelations values ('C', 'D')
insert into #ObjectRelations values ('E', 'F')
insert into #ObjectRelations values ('D', 'F')

declare @startIds table
(
Id varchar(20) primary key
)

;WITH
Ids (Id) AS
(
SELECT Id
FROM #ObjectRelations
),
NextIds (Id) AS
(
SELECT NextId
FROM #ObjectRelations
)
INSERT INTO @startIds
SELECT DISTINCT
Ids.Id
FROM
Ids
LEFT JOIN
NextIds on Ids.Id = NextIds.Id
WHERE
NextIds.Id IS NULL

;WITH Objects (Id, NextId, [Level]) AS
( -- This is the 'Anchor' or starting point of the recursive query
SELECT rel.Id,
rel.NextId,
0
FROM #ObjectRelations rel
WHERE rel.Id IN (SELECT Id FROM @startIds)
UNION ALL -- This is the recursive portion of the query
SELECT rel.Id,
rel.NextId,
[Level] + 1
FROM #ObjectRelations rel
INNER JOIN Objects -- Note the reference to CTE table name (Recursive Join)
ON rel.Id = Objects.NextId
)
SELECT DISTINCT *
FROM Objects
ORDER BY [Level]

drop table #ObjectRelations

Post #715639
Posted Tuesday, May 12, 2009 10:28 PM
Grasshopper

GrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopper

Group: General Forum Members
Last Login: Friday, April 23, 2010 4:57 PM
Points: 11, Visits: 27
@Ken: Sorry, didn't see your reply, but yes, that works! =)
Post #715642
Posted Tuesday, May 12, 2009 11:03 PM


SSCrazy Eights

SSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy Eights

Group: General Forum Members
Last Login: Thursday, June 5, 2014 10:54 AM
Points: 9,902, Visits: 9,480
FYI, then this problem is called a "Topological Sort".

-- RBarryYoung, (302)375-0451 blog: MovingSQL.com, Twitter: @RBarryYoung
Proactive Performance Solutions, Inc.
"Performance is our middle name."
Post #715657
« Prev Topic | Next Topic »

Add to briefcase 12»»

Permissions Expand / Collapse