April 15, 2014 at 3:51 am
We have a table containing a 'recursive' structure.
Metadata:
Parentname,
Childname,
A child 'points' to a parent.
Starting at a topparent (level 0), I want to have the direct children (level 1), the grandchildren (level 2) etc.
Problem the structure is not completely hierarchical and in the meta data there can be 'loops', a structure might point to itself directly or indirectly. I want to have all relations and levels, but prevent loops.
Example
A toplevel 0
B points to A level 1 (child)
C points to B level 2 (grandchild)
D points to B level 2 (grandchild)
D points to C level 3 (D is also a greatgrandchild).
C points to D level 4
D ponts to C level 5 <<<<< Loop D points to C is already level 3
At the moment I have build a script with distinct code for each level.
(At each level repeats of the same structure are removed last row is a repeat).
I would like to have the same code with a CTE but am confused by the loops in the structure. The last row in the example above results in an endless loop, so this should be avoided.
ben
April 15, 2014 at 6:55 am
ben besides the join, i think you also have to be able to say where the level < previous level as well; that avoids the endless recursion
here's a rough example; if you can show your table structure and sample data, we can hemp a lot better.
IF OBJECT_ID('tempdb.[dbo].[#sample]') IS NOT NULL
DROP TABLE [dbo].[#sample]
create table #sample(sno int identity,ChildID int, ParentID int,task varchar(50))
insert into #sample (ChildID,ParentID,task) values(1,10,'tactical')
insert into #sample (ChildID,ParentID,task) values(10,20,'basket')
insert into #sample (ChildID,ParentID,task) values(20,40,'aerospace')
insert into #sample (ChildID,ParentID,task) values(40,10,'robot')
insert into #sample (ChildID,ParentID,task) values(10,40,'tackle')
insert into #sample (ChildID,ParentID,task) values(40,60,'trick')
--only works as hierarchy if the child has higher # than parent.
;WITH rCTE AS (
SELECT sno, ChildID, ParentID, task, 0 AS [Level]
FROM #sample
WHERE ChildID = 1
UNION ALL
SELECT c.sno, c.ChildID, c.ParentID, c.task, p.[level] + 1
FROM #sample c
INNER JOIN rCTE p ON p.ParentID = c.ChildID AND p.sno < c.sno
)
SELECT DISTINCT sno, ChildID, ParentID, task
FROM rCTE
WHERE [Level] BETWEEN 1 AND 4
Lowell
April 16, 2014 at 3:38 am
Thanks Lowell for the example.
I am trying to order the data which I have. Which is the relations between the 'child' and 'parent'.
So I took your example and 'removed' the info which gave an ordering to the order of rows (identity), my dataset lacks such an ordering. And also removed an ordering in the identities of the parent child, by making them character fields.
Also I added a row with the same parent child combination, but a 'different' role which is visible in the task column.
(I also think something dropped from your anwser)
Preventing the loop is most important.
Second I do not know the number of levels which is present in the data. (Probably less than 10, certainly less than 20).
Here is the adjusted example (thanks for the example.)
IF OBJECT_ID('tempdb.[dbo].[#sample]') IS NOT NULL
DROP TABLE [dbo].[#sample]
create table #sample(sno int identity,ChildID (varchar(30), ParentID varchar(30),task varchar(50))
insert into #sample (ChildID,ParentID,task) values('222','111','aerospace')
insert into #sample (ChildID,ParentID,task) values('111','333','robot')
insert into #sample (ChildID,ParentID,task) values('333','111','tackle')
insert into #sample (ChildID,ParentID,task) values('444','333','tactical')
insert into #sample (ChildID,ParentID,task) values('444','333','SecondRole')
insert into #sample (ChildID,ParentID,task) values('333','222','basket')
insert into #sample (ChildID,ParentID,task) values('111','666','trick')
--
-- No order in the rows, identity is a 'random' order.
-- No order in the id's of the child and the parent.
-- Only information available is the identity of the child and the parent, the identities have no ordering.
--
Thanks for your time and attention.
Ben
April 16, 2014 at 6:50 am
IF OBJECT_ID('tempdb.[dbo].[#sample]') IS NOT NULL
DROP TABLE [dbo].[#sample];
create table #sample(sno int identity,ChildID varchar(30), ParentID varchar(30),task varchar(50));
--Corrected code by removing extra paren preventing table creation.
insert into #sample (ChildID,ParentID,task) values('222','111','aerospace');
insert into #sample (ChildID,ParentID,task) values('111','333','robot');
insert into #sample (ChildID,ParentID,task) values('333','111','tackle');
insert into #sample (ChildID,ParentID,task) values('444','333','tactical');
insert into #sample (ChildID,ParentID,task) values('444','333','SecondRole');
insert into #sample (ChildID,ParentID,task) values('333','222','basket');
insert into #sample (ChildID,ParentID,task) values('111','666','trick');
--
-- No order in the rows, identity is a 'random' order.
-- No order in the id's of the child and the parent.
-- Only information available is the identity of the child and the parent, the identities have no ordering.
--
FYI: I added semi-colons to the above statements so you don't have to stick a ; before the WITH CTE statement. Not that it helps. Your lines don't have the proper hierarchy for the CTE to work. Before futzing with the CTE, I ran this statement:
SELECT * FROM #sample ORDER BY ParentID, ChildID;
Looking at the returned data, the CTE won't work because of this bit of data:
snoChildIDParentIDtask
2111333robot
If ordering truly is a problem (i.e., ParentID is not always less than ChildID), then I don't know how you're going to resolve your problem because you don't have a truly recursive structure in place. Unless, possibly, this was just a bad data sample?
April 16, 2014 at 6:57 am
Another note.
Even if that one data line is bad, I don't think the CTE will work because you're using VARCHAR for the ChildID and ParentID. In such a case, they really aren't ID fields, therefore are pretty much uncomparable. In character fields, A will always come before H, and special characters have their own ANSI codes which will cause them to filter oddly in SQL Server.
Can you give us more appropriate sample data (not using Lowell's but using information that is more like what your table contains) and a more appropriate table DDL?
April 16, 2014 at 7:50 am
"Cycles" in hierarchies is always a problem for these types of things. It's usually because people (for example) can hold more than one position in an org chart (for example). My recommendation where such things are needed is to make a hierarchy of job positions (for example) where each job postion is a unique ID and then assign people to those position instead of assigning people to people.
--Jeff Moden
Change is inevitable... Change for the better is not.
April 16, 2014 at 8:11 am
Brandie Tarvin (4/16/2014)
FYI: I added semi-colons to the above statements so you don't have to stick a ; before the WITH CTE statement. Not that it helps. Your lines don't have the proper hierarchy for the CTE to work. Before futzing with the CTE, I ran this statement:
SELECT * FROM #sample ORDER BY ParentID, ChildID;
Looking at the returned data, the CTE won't work because of this bit of data:
snoChildIDParentIDtask
2111333robot
If ordering truly is a problem (i.e., ParentID is not always less than ChildID), then I don't know how you're going to resolve your problem because you don't have a truly recursive structure in place. Unless, possibly, this was just a bad data sample?
First all thanks for your thoughts.
The data is very similar to the example.
The example represents only a fraction of the actual data.
Example contains:
A loop of three 'nodes' or members: 111, 222, 333.
It contains a loop of two 'nodes' : 111, 333
It contains a double reference (two roles between the same parent child): 444, 333.
It even contains a 'top' node in this case: 666
Possible but not in the example a self referencing node or member.
As said it is not completely hierarchical.
The identifiers for the child and the parent are actual varchar fields.
Alphabetic ordering is of no consequence. (Ordering on basis of length or on basis of the third character would have the same value).
Actual in the real example there are two character fields involved for each member.
Starting at the top of 666 ( no nodes above) this would be level 0.
111 is level 1 because it reverences to level 0.
222 and 333 are level 2 because you need two references to level 0
444 is level 3.
Next to the levels the reference like between 222 and 333 are stil important, although on the sme level.
Or going a level down from 111 to 333 is also important.
The structure would be different is we would start at a different top node.
So no this is not a bad data sample, just a complex 'network' structure.
Were I want to start at an node (666 as top for example) and go 'down' the structure in the correct order.
The actual structure is Meta data.
Content follows the same structure, but not all content has all references.
Still hoping for a CTE sollution, otherwise the stepped version I have just has to be sufficient.
Thanks,
Ben
Viewing 7 posts - 1 through 6 (of 6 total)
You must be logged in to reply to this topic. Login to reply