Multiple Parent-Child relations

Please start any new threads on our new site at https://forums.sqlteam.com. We've got lots of great SQL Server experts to answer whatever question you can come up with.

All Forums

SQL Server 2000 Forums

SQL Server Development (2000)

Multiple Parent-Child relations

Author

Topic

hasanali00
Posting Yak Master

207 Posts

Posted - 2006-06-01 : 05:01:21

I have a table that holds parent and child relations, like:


Parent ID       Child ID
10              8
8               7
7               2
8               6
6               2

Now for a given Child ID, I want to return the full path that is take to reach that Child ID. For instance, if Child ID is 2, I would get:
10 > 8 > 7 > 2
8 > 6 > 2

Any idea what I can do work around this problem?

Looking forward to hearing from you.

regards

chiragkhabaria
Master Smack Fu Yak Hacker

1907 Posts

Posted - 2006-06-01 : 05:06:14

REfer this link
http://www.nigelrivett.net/RetrieveTreeHierarchy.html

If Debugging is the process of removing Bugs then i Guess programming should be process of Adding them.

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2006-06-01 : 05:35:10

quote:
Originally posted by hasanali00

I have a table that holds parent and child relations, like:

Parent ID Child ID
10 8
8 7
7 2
8 6
6 2

Now for a given Child ID, I want to return the full path that is take to reach that Child ID. For instance, if Child ID is 2, I would get:
10 > 8 > 7 > 2
8 > 6 > 2

[code]This is not right
10 > 8 > 7 > 2
8 > 6 > 2

Since 8 is a child of 10 the rows will look like
10 > 8 > 7 > 2
10 > 8 > 6 > 2

It looks like bad design to start with, since the table design allows circular reference!

hasanali00
Posting Yak Master

207 Posts

Posted - 2006-06-01 : 06:10:09

Peso, you are 100% correct. I should get:

10 > 8 > 7 > 2
10 > 8 > 6 > 2

I have read:
http://www.nigelrivett.net/RetrieveTreeHierarchy.html &
http://www.thesitedoctor.co.uk/seventhnight/treestructs/

However, these examples show how to get Child from Parent. But I want to get Parent from Child, which I think is toooo difficut.

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2006-06-01 : 06:18:56

quote:
Originally posted by hasanali00
Peso, you are 100% correct.

Is this table allowing multiple parent and multiple child?

hasanali00
Posting Yak Master

207 Posts

Posted - 2006-06-01 : 06:28:23

Yes, multiple parent and multiple child

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2006-06-01 : 09:08:17

Piece of cake, NOT!

Anyway, here is the code!
-----------------------------------------------------------------------------------------

-- Prepare test data
DECLARE @Nodes TABLE (Parent INT, Child INT)

INSERT @Nodes (Parent, Child)
SELECT 10, 8 UNION ALL
SELECT 8, 7 UNION ALL
SELECT 7, 2 UNION ALL
SELECT 8, 6 UNION ALL
SELECT 6, 2

-- Keep track of path and links
DECLARE @Paths TABLE (Generation INT, Parent INT, Child INT)

DECLARE @Child INT,
@Generation INT

-- Set up start condition
SELECT @Child = 2,
@Generation = 0

-- Insert the child/children to start with
INSERT @Paths (Generation, Parent, Child)
SELECT 0,
Parent,
@Child
FROM @Nodes
WHERE Child = @Child

-- Iterate and get all parents until there is none
-- IMPORTANT!!! Avoid circular reference!
WHILE @@ROWCOUNT > 0
BEGIN
SELECT @Generation = @Generation + 1

INSERT @Paths (Generation, Parent, Child)
SELECT @Generation,
Parent,
Child
FROM @Nodes
WHERE Child IN (SELECT Parent FROM @Paths WHERE Generation = @Generation - 1)
AND Parent NOT IN (SELECT Child FROM @Paths)
END

DECLARE @Stage TABLE(Path VARCHAR(8000), Parent INT, Child INT)
DECLARE @Temp TABLE(Path VARCHAR(8000), Parent INT, Child INT)

SELECT @Child = MAX(Generation),
@Generation = 1
FROM @Paths

INSERT @Stage
SELECT CONVERT(VARCHAR, Parent) + ' > ' + CONVERT(VARCHAR, Child),
Parent,
Child
FROM @Paths
WHERE Generation = 0

WHILE @Generation <= @Child
BEGIN
DELETE
FROM @Temp

INSERT @Temp
SELECT CONVERT(VARCHAR, p.Parent) + ' > ' + s.Path,
p.Parent,
s.Parent
FROM @Stage s
LEFT JOIN (
SELECT Parent, Child FROM @Paths WHERE Generation = @Generation
) p ON p.Child = s.Parent

IF (SELECT COUNT(*) FROM @Temp WHERE Path IS NULL) > 0
BEGIN
DELETE
FROM @Temp
WHERE Path IS NULL

INSERT @Temp
SELECT Path,
Parent,
Child
FROM @Stage
END

DELETE
FROM @Stage

INSERT @Stage
SELECT Path,
Parent,
Child
FROM @Temp

SELECT @Generation = @Generation + 1
END

-- Output the paths
SELECT Path
FROM @Stage
ORDER BY LEN(Path),
REVERSE(Path)
-----------------------------------------------------------------------------------------
Enjoy!

Seventhnight
Master Smack Fu Yak Hacker

2878 Posts

Posted - 2006-06-01 : 10:48:02

I believe the easiest way to deal with multiple parents is to start at the bottom of the tree (nodes with no children) and work your way up.

I wrote an example the other day... I'll see if I can find it.

be back!

Corey

Co-worker on children "...when I have children, I'm going to beat them. Not because their bad, but becuase I think it would be fun ..."

Seventhnight
Master Smack Fu Yak Hacker

2878 Posts

Posted - 2006-06-01 : 10:55:39

I found it.... look at the bottom of this thread: http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=66466

Corey

Co-worker on children "...when I have children, I'm going to beat them. Not because their bad, but becuase I think it would be fun ..."

RyanRandall
Master Smack Fu Yak Hacker

1074 Posts

Posted - 2006-06-02 : 11:39:44

Hi all,

Here's my stab at something simple...

--data
DECLARE @Nodes TABLE (Parent INT, Child INT)

INSERT @Nodes (Parent, Child)
SELECT 10, 8 UNION ALL
SELECT 11, 7 UNION ALL --for multiple top nodes
SELECT 8, 7 UNION ALL
SELECT 7, 8 UNION ALL --for infinite loop
SELECT 7, 2 UNION ALL
SELECT 8, 6 UNION ALL
SELECT 6, 2

--input
declare @Child int
set @Child = 2

--calculation
declare @NodePaths table (Path varchar(8000), TopNode int)
insert @NodePaths select @Child, @Child

while @@rowcount > 0
    insert @NodePaths
    select cast(Parent as varchar(10)) + ' > ' + p.Path, Parent
    from @NodePaths p inner join @Nodes n on n.Child = p.TopNode
    where 
        charindex(' > ' + cast(Parent as varchar(10)) + ' > ', ' > ' + Path + ' > ') = 0 --prevent going round in circles
        and cast(Parent as varchar(10)) + ' > ' + p.Path not in (select Path from @NodePaths) --prevent redoing paths already done

select Path from @NodePaths where TopNode not in (select Child from @Nodes) order by Path

/*results
Path                                                                                                 
---------------------
10 > 8 > 6 > 2
10 > 8 > 7 > 2
11 > 7 > 2
11 > 7 > 8 > 6 > 2
*/

Ryan Randall
www.monsoonmalabar.com London-based IT consultancy

Solutions are easy. Understanding the problem, now, that's the hard part.

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2006-06-02 : 15:00:35

quote:

while @@rowcount > 0
insert @NodePaths
select cast(Parent as varchar(10)) + ' > ' + p.Path, Parent
from @NodePaths p inner join @Nodes n on n.Child = p.TopNode
where
charindex(' > ' + cast(Parent as varchar(10)) + ' > ', ' > ' + Path + ' > ') = 0 --prevent going round in circles
and cast(Parent as varchar(10)) + ' > ' + p.Path not in (select Path from @NodePaths) --prevent redoing paths already done

Excellent! Sometimes I think you're a wizard...

RyanRandall
Master Smack Fu Yak Hacker

1074 Posts

Posted - 2006-06-05 : 05:21:26

quote:
Excellent! Sometimes I think you're a wizard...

The feeling is mutual, Peso...

Ryan Randall
www.monsoonmalabar.com London-based IT consultancy

Solutions are easy. Understanding the problem, now, that's the hard part.

hasanali00
Posting Yak Master

207 Posts

Posted - 2006-06-05 : 10:24:36

Thanks everyone

Yes, Ryan's solution works very well.

Prior to Ryan's solution, I was working on my own and very limited solution.

I defined a temp table with 5 columns, like:



declare @tempID int

create Table #ParentCategories (id int identity(1,1), category5 int, category4 int , category3 int, category2 int , category1 int)

insert into #ParentCategories (category5, category4)

select @ChildID, ParentID from CategoryRelations where childID = @ChildID
-- UPDATE CATEGORY 3

 select @tempID = ParentID from CategoryRelations C , #ParentCategories P where c.childID = P.category4  and category5 = 
select  childid from CategoryRelations ,  #ParentCategories  where parentid = CATEGORY4

My logic is to update #ParentCategories.Category3 with the parentID of #ParentCategories.Category4 WHERE #ParentCategories.Category5 is the ChildID of #ParentCategories.Category4

I think the logic is OK, but I could not get the SQL to work.

Just out of interest, if I was carrying on with my approach, how can I make my SQL work.

Kind regards

sqldev80
Yak Posting Veteran

68 Posts

Posted - 2006-06-16 : 11:47:23

This code find out the parent of the child. If I want to change it and want to enter the parent and find all the children of the parent how would that be done.

so result would be in opposite way and will show all the children
once the parent id is input

2 < 6 < 8 < 10
2 < 7 < 8 < 10
2 < 7 < 11
2 < 6 < 8 < 7 < 11

DECLARE @Nodes TABLE (Parent INT, Child INT)

INSERT @Nodes (Parent, Child)
SELECT 10, 8 UNION ALL
SELECT 11, 7 UNION ALL --for multiple top nodes
SELECT 8, 7 UNION ALL
SELECT 7, 8 UNION ALL --for infinite loop
SELECT 7, 2 UNION ALL
SELECT 8, 6 UNION ALL
SELECT 6, 2
--input
declare @Child int
set @Child = 2

--calculation
declare @NodePaths table (Path varchar(8000), TopNode int)
insert @NodePaths select @Child, @Child

while @@rowcount > 0
insert @NodePaths
select cast(Parent as varchar(10)) + ' > ' + p.Path, Parent
from @NodePaths p inner join @Nodes n on n.Child = p.TopNode
where
charindex(' > ' + cast(Parent as varchar(10)) + ' > ', ' > ' + Path + ' > ') = 0 --prevent going round in circles
and cast(Parent as varchar(10)) + ' > ' + p.Path not in (select Path from @NodePaths) --prevent redoing paths already done

select Path from @NodePaths where TopNode not in (select Child from @Nodes) order by Path
/*results
Path
---------------------
10 > 8 > 6 > 2
10 > 8 > 7 > 2
11 > 7 > 2
11 > 7 > 8 > 6 > 2

RyanRandall
Master Smack Fu Yak Hacker

1074 Posts

Posted - 2006-06-16 : 12:05:39

A few cheeky reversals will do it...

--data
DECLARE @Nodes TABLE (Parent INT, Child INT)

INSERT @Nodes (Parent, Child)
SELECT 10, 8 UNION ALL
SELECT 11, 7 UNION ALL --for multiple top nodes
SELECT 8, 7 UNION ALL
SELECT 7, 8 UNION ALL --for infinite loop
SELECT 7, 2 UNION ALL
SELECT 8, 6 UNION ALL
SELECT 6, 2

--input
declare @Parent int
set @Parent = 11

--calculation
declare @NodePaths table (Path varchar(8000), EndNode int)
insert @NodePaths select @Parent, @Parent

while @@rowcount > 0
insert @NodePaths
select cast(Child as varchar(10)) + ' < ' + p.Path, Child
from @NodePaths p inner join @Nodes n on n.Parent = p.EndNode
where 
charindex(' < ' + cast(Child as varchar(10)) + ' < ', ' < ' + Path + ' < ') = 0 --prevent going round in circles
and cast(Child as varchar(10)) + ' < ' + p.Path not in (select Path from @NodePaths) --prevent redoing paths already done

select Path from @NodePaths where EndNode not in (select Parent from @Nodes) order by Path

/*results
Path               
-------------------
2 < 6 < 8 < 7 < 11
2 < 7 < 11
*/

Ryan Randall
www.monsoonmalabar.com London-based IT consultancy

Solutions are easy. Understanding the problem, now, that's the hard part.

sqldev80
Yak Posting Veteran

68 Posts

Posted - 2006-06-16 : 12:37:51

Thanks Ryan,

I more question. I have column like

Parent , child
1 10
1 11
10 12
12 14
I do not want my data entry people at any cost enter this in the data base and make a circulare referece:
Parent Child
12 10
10 12
14 12
I do not want to break hierarchy at any cost.
What is the best way to prevent it. Thanks

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2006-06-16 : 14:33:29

quote:
Originally posted by sqldev80

Thanks Ryan,

I more question. I have column like

Parent , child
1 10
1 11
10 12
12 14
I do not want my data entry people at any cost enter this in the data base and make a circulare referece:
Parent Child
12 10
10 12
14 12
I do not want to break hierarchy at any cost.
What is the best way to prevent it. Thanks

Ryan's function is well equiped to handle circulare references. Try it!

Peter Larsson
Helsingborg, Sweden

sqldev80
Yak Posting Veteran

68 Posts

Posted - 2006-06-16 : 14:39:02

which funtion is it?

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2006-06-16 : 16:46:43

quote:
Originally posted by sqldev80

which funtion is it?

The two functions Ryan has written in this topic. There is a remark where he says that circular refernence is taken care of, so that the loop doesn't continue forever.

And it is true. I have tried to break it. Both with first level circular reference (a -> a) and second level (a -> b -> a) and at last third level (a -> b -> c -> a)

Try it for yourself.

Peter Larsson
Helsingborg, Sweden

sqldev80
Yak Posting Veteran

68 Posts

Posted - 2006-06-16 : 17:06:28

I know that. But i need some clause in the table which even prevents such sort of data entry
He has entered that data and is taking care of it.
I would like to avoid that type to data entry
So any time there is an entry where the hierarchy level is broken
it should give an error.

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2006-06-16 : 17:36:27

quote:
Originally posted by sqldev80

I know that. But i need some clause in the table which even prevents such sort of data entry
He has entered that data and is taking care of it.
I would like to avoid that type to data entry
So any time there is an entry where the hierarchy level is broken
it should give an error.

A very easy way is to make a function that returns bit true/false if circular reference exists. then use this function as constraint for table.

Peter Larsson
Helsingborg, Sweden

Next Page

Subscribe to SQLTeam.com

SQLTeam.com Articles via RSS

SQLTeam.com Weblog via RSS

- Advertisement -

Resources