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

Help with sorting this recursion Expand / Collapse
Author
Message
Posted Monday, February 11, 2013 10:46 AM
SSC-Enthusiastic

SSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-Enthusiastic

Group: General Forum Members
Last Login: Friday, February 22, 2013 10:40 AM
Points: 153, Visits: 323
DECLARE @DateLevel int = 0, @DateLevelUp int, @FTID int = 7

CREATE TABLE #FieldRels
(
FTIDBase int,
FTIDCalc int
)

INSERT INTO #FieldRels(FTIDBase, FTIDCalc)
SELECT 6, 7 UNION ALL
SELECT 7, 8 UNION ALL
SELECT 7, 12 UNION ALL
SELECT 8, 13

/*This is a table showing the relationship between a load of 'FieldIDs'
So, 7 relates to 6, 8 relates to 7, 12 relates to 7 and 13 relates to 8
I want to be able to pass any number into a procedure (hardcoded as 7 above) and return any fields that that ID relates to - both above it (fields it relates to)
and below it (fields that relate to it)

I want the data to be returned, in this case, like this

6
--7
----8
------13
----12

Showing that, for example, 8 and 12 relate to 7, but 13, which relates to 8, appears between them.

Here is what I have so far.
*/

CREATE TABLE #TempLadder (ID int NOT NULL identity(1,1), FTIDBase int, FTIDCalc int, DateLevel int, FieldDesc varchar(255), ThisOne bit, WhereFrom varchar(20))

IF EXISTS(SELECT 0 FROM #FieldRels WHERE FTIDCalc = @FTID) --the field passed in has a parent - work up the chain to the parent
BEGIN
--find the fields above the one passed in working up
;WITH rCTE(FTIDBase, FTIDCalc, DateLevel) AS
(
SELECT FTIDBase, FTIDCalc, @DateLevel
FROM #FieldRels
WHERE FTIDCalc = @FTID
UNION ALL
SELECT e.FTIDBase, e.FTIDCalc, @DateLevel + 1
FROM #FieldRels e
INNER JOIN rCTE c ON e.FTIDCalc = c.FTIDBase
)

INSERT INTO #TempLadder
SELECT FTIDBase, FTIDCalc, DateLevel, 'Field Description', 'false' AS [ThisOne], 'first'
FROM rCTE
ORDER BY DateLevel DESC --sort DESC as we have worked our way up - to get the one furthest from the field passed in to be first

SET @DateLevelUp = (SELECT MAX(DateLevel) FROM #TempLadder)

UPDATE #TempLadder SET DateLevel = @DateLevelUp - DateLevel --because we inserted using Sort DESC, reverse DateLevels
SET @DateLevel = (SELECT MAX(DateLevel) FROM #TempLadder) + 1


IF NOT EXISTS(SELECT 0 FROM #FieldRels WHERE FTIDBase = @FTID) --if the field passed in is not a parent itself, the field is at the bottom, so add it.
BEGIN
INSERT INTO #TempLadder
SELECT FTIDBase, FTIDCalc, @DateLevel, 'Field Description', 'true' AS [ThisOne], 'second'
FROM #FieldRels
WHERE #FieldRels.FTIDCalc = @FTID

SET @DateLevel = (SELECT MAX(DateLevel) FROM #TempLadder) + 1

END

END


IF EXISTS(SELECT 0 FROM #FieldRels WHERE FTIDCalc = @FTID) AND EXISTS(SELECT 0 FROM #FieldRels WHERE FTIDBase = @FTID) --this field has fields above and fields below
BEGIN

INSERT INTO #TempLadder
SELECT FTIDBase, FTIDCalc, @DateLevel, 'Field Description', 'true' AS [ThisOne], 'third'
FROM #FieldRels
WHERE #FieldRels.FTIDCalc = @FTID

SET @DateLevel = (SELECT MAX(DateLevel) FROM #TempLadder) + 1

END


IF EXISTS(SELECT 0 FROM #FieldRels WHERE FTIDBase = @FTID) --the field passed in has a child - work down the chain to furthest child
BEGIN

IF NOT EXISTS(SELECT 0 FROM #FieldRels WHERE FTIDCalc = @FTID)
BEGIN

INSERT INTO #TempLadder
SELECT TOP 1 FTIDBase, FTIDCalc, @DateLevel, 'Field Description', 'true' AS [ThisOne], 'fourth'
FROM #FieldRels
WHERE #FieldRels.FTIDBase = @FTID

SET @DateLevel = (SELECT MAX(DateLevel) FROM #TempLadder) + 1

END


;WITH rCTE(FTIDCalc, FTIDBase, DateLevel) AS
(
SELECT FTIDCalc, FTIDBase, @DateLevel
FROM #FieldRels
WHERE FTIDBase = @FTID
UNION ALL
SELECT e.FTIDCalc, e.FTIDBase, @DateLevel + 1
FROM #FieldRels e
INNER JOIN rCTE d ON e.FTIDBase = d.FTIDCalc
)

INSERT INTO #TempLadder
SELECT FTIDBase, FTIDCalc, DateLevel, 'Field Description', CASE WHEN FTIDCalc = @FTID THEN 'true' ELSE 'false' END AS [ThisOne], 'fifth'
FROM rCTE

END

SELECT * FROM #TempLadder


DROP TABLE #TempLadder
DROP TABLE #FieldRels

This is returning:
FTIDBase FTIDCalc DateLevel ... the levels are being calculated okay, but item 13 (second column, last row is in the wrong order)
6-------------7------------0
6-------------7------------1
7-------------8------------2
7-------------12-----------2
8-------------13-----------3

The data being returned above has two things wrong with it. From the point of view of joining to another table to get the real Field Descriptions I really need the data returned to look like this:
FTIDBase FTIDCalc DateLevel
6-------------6------------0 this is the topmost row - Item 6 - level 0
6-------------7------------1 item 7 relates to item 6 - level 1
7-------------8------------2 item 8 relates to item 7 - level 2
8-------------13-----------3 item 13 relates to item 8 - level 3
7-------------12-----------2 Item 12 relates to item 7 - back in to level 2

Any help to get this sorted properly would be much appreciated. Been at it for days now.
Post #1418560
Posted Monday, February 11, 2013 12:31 PM
SSC-Enthusiastic

SSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-Enthusiastic

Group: General Forum Members
Last Login: Friday, February 22, 2013 10:40 AM
Points: 153, Visits: 323
I see 45 people have looked at this ... but no comments.

Is my question not clear? Or am I going about it the wrong way? Any comment at all? If you think it is not possible to sort as required could you say please? And I'll start thinking about the old cursors!
Post #1418604
Posted Monday, February 11, 2013 3:26 PM


SSC-Dedicated

SSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-Dedicated

Group: General Forum Members
Last Login: Today @ 11:36 AM
Points: 32,890, Visits: 26,759
The old cursors wouldn't work any better. Recusive CTE's are just another rendition of RBAR.

What you're missing is a "Hierarchical Path" to preserve the correct sort order. Please see the following article...
http://www.sqlservercentral.com/articles/T-SQL/72503/


--Jeff Moden
"RBAR is pronounced "ree-bar" and is a "Modenism" for "Row-By-Agonizing-Row".

First step towards the paradigm shift of writing Set Based code:
Stop thinking about what you want to do to a row... think, instead, of what you want to do to a column."

For better, quicker answers on T-SQL questions, click on the following...
http://www.sqlservercentral.com/articles/Best+Practices/61537/

For better answers on performance questions, click on the following...
http://www.sqlservercentral.com/articles/SQLServerCentral/66909/
Post #1418658
Posted Monday, February 11, 2013 5:05 PM
SSC-Enthusiastic

SSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-Enthusiastic

Group: General Forum Members
Last Login: Friday, February 22, 2013 10:40 AM
Points: 153, Visits: 323
Ahhhh! Thank you, thank you and thank you again.

Spent most of the weekend on that and today. I've got a bin full of paper with drawings of little tables with numbers ... desperately trying to fathom how to add something in to do the sorting. I even resorted to changing rooms and going on the whiteboard - but I got fed up continously rubbing things out.
Post #1418689
Posted Monday, February 11, 2013 9:05 PM
SSC Veteran

SSC VeteranSSC VeteranSSC VeteranSSC VeteranSSC VeteranSSC VeteranSSC VeteranSSC Veteran

Group: General Forum Members
Last Login: Today @ 11:23 AM
Points: 283, Visits: 1,237
You have what you need right there already (except maybe a sort value to break ties...I used FTIDCalc for that). I created an artificial sort key based on your parent-child relationships.


--this is just your sample data inserted into a temp table

IF OBJECT_ID('tempdb..#TempLadder') IS NOT NULL
DROP TABLE #TempLadder

CREATE TABLE #TempLadder
(
ID INT NOT NULL IDENTITY(1,1)
,FTIDBase INT
,FTIDCalc INT
,DateLevel INT
,FieldDesc VARCHAR(255)
,ThisOne BIT
,WhereFrom VARCHAR(20)
)

INSERT INTO #TempLadder
(
FTIDBase
,FTIDCalc
,DateLevel
,FieldDesc
,ThisOne
,WhereFrom
)
SELECT 6,7,0,'Base Level Item',0,'first'
UNION ALL
SELECT 6,7,1,'1st Level Item',1,'third'
UNION ALL
SELECT 7,8,2,'2nd Level Item',0,'fifth'
UNION ALL
SELECT 7,12,2,'2nd Level Item',0,'fifth'
UNION ALL
SELECT 8,13,3,'3rd Level Item',0,'fifth'

SELECT
ID
,FTIDBase
,FTIDCalc
,DateLevel
,FieldDesc
,ThisOne
,WhereFrom
FROM
#TempLadder


Here's the code to sort it hierarchically. This is sorted by hierarchy level as you indicated in your post above. If you want it to be a NESTED hierarchy you can use a recursive CTE. The recursive half of that is mostly just using the code below and attaching it to a base case. (It's a little more than that, but it's not too hard.)


SELECT
CAST(FieldDesc AS VARCHAR(MAX)) AS FieldDesc
,ThisOne
,WhereFrom
,FTIDBase
,FTIDCalc
,REPLICATE('0',4-(LEN(DateLevel))) + CAST(DateLevel AS VARCHAR(MAX)) + '.'
+ REPLICATE('0',4-(LEN(FTIDBase))) + CAST(FTIDBase AS VARCHAR(MAX)) + '.'
+ REPLICATE('0',4-(LEN(FTIDCalc))) + CAST(FTIDCalc AS VARCHAR(MAX)) + '.'
AS SortKey
,DateLevel AS HierarchyLevel
FROM
#TempLadder


The output:


FieldDesc ThisOne WhereFrom FTIDBase FTIDCalc SortKey HierarchyLevel
Base Level Item 0 first 6 7 0000.0006.0007. 0
1st Level Item 1 third 6 7 0001.0006.0007. 1
2nd Level Item 0 fifth 7 8 0002.0007.0008. 2
2nd Level Item 0 fifth 7 12 0002.0007.0012. 2
3rd Level Item 0 fifth 8 13 0003.0008.0013. 3


Post #1418732
Posted Tuesday, February 12, 2013 1:52 AM
SSC-Enthusiastic

SSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-Enthusiastic

Group: General Forum Members
Last Login: Friday, February 22, 2013 10:40 AM
Points: 153, Visits: 323
Hi, and thank you for your answer.

Following Jeff Moden's answer (and link) - I modified my code to have a sort key that ended up returning...

\6
\6\7
\6\7\12
\6\7\8
\6\7\8\13

... which seems to do what I need.

Is there some advantage to creating the sort key in the form you used (using REPLICATE etc.)?

Also, when you said 'if I wanted a nested hierarchy' - what do you mean by that? I thought I had (now, with the sort key) got a nested hierarchy. Items that belong to each other are now appearing in order and their Level allows me, in the front end, to indent as required to physically display the list with nested indents?
Post #1418798
Posted Tuesday, February 12, 2013 11:10 AM
SSC Veteran

SSC VeteranSSC VeteranSSC VeteranSSC VeteranSSC VeteranSSC VeteranSSC VeteranSSC Veteran

Group: General Forum Members
Last Login: Today @ 11:23 AM
Points: 283, Visits: 1,237
sku370870 (2/12/2013)
Is there some advantage to creating the sort key in the form you used (using REPLICATE etc.)?

At least with this sort key method you have to keep in mind that it's a string and thus will sort in ASCII order. So if you had two nodes like 6 and 12, then 12 would sort higher than the 6. So I use replicate to pad with leading zeroes to make sure each part of the sort key has the correct priority. If more levels are added or anticipated, then more leading zeroes may be necessary.

sku370870 (2/12/2013)
Is
Also, when you said 'if I wanted a nested hierarchy' - what do you mean by that? I thought I had (now, with the sort key) got a nested hierarchy. Items that belong to each other are now appearing in order and their Level allows me, in the front end, to indent as required to physically display the list with nested indents?

Say we have these elements SORTED by level:

[Level] [Parent] [Item]
Level1 0 1
Level1 0 2
Level1 0 6
Level2 1 3
Level2 1 4
Level2 2 5
Level3 4 7
Level3 5 8
Level3 5 9

Now if they were NESTED or hierarchical:

[Level] [Parent] [Item]
Level1 0 1
Level2 1 3
Level2 1 4
Level3 4 7
Level1 0 2
Level2 2 5
Level3 5 8
Level3 5 9
Level1 0 6


 
Post #1419127
Posted Tuesday, February 12, 2013 3:04 PM
SSC Veteran

SSC VeteranSSC VeteranSSC VeteranSSC VeteranSSC VeteranSSC VeteranSSC VeteranSSC Veteran

Group: General Forum Members
Last Login: Today @ 11:23 AM
Points: 283, Visits: 1,237
By coincidence one of my colleagues asked me this afternoon how to do a hierarchical query. So I dug out something from my toolbox. Here's a scrubbed down generic version I handed over to get him started in the right direction. It will demonstrate what I was talking about above concerning nested hierarchies.

Create a table for sample data.


IF OBJECT_ID('tempdb..#TempTable') IS NOT NULL
DROP TABLE #TempTable

CREATE TABLE #TempTable
(
[ID] [int] NOT NULL
,[ItemDesc] [char](250) NULL
,[Sort] [int] NULL
,[ParentID] [int] NULL
,[HLevel] [int] NULL
,[LocationID] [int] NOT NULL
,PRIMARY KEY (ID)
)

INSERT INTO #TempTable
SELECT 1,'Food Products',10,0,0,22
UNION
SELECT 2,'Fruit',10,1,1,22
UNION
SELECT 3,'Vegetables',20,1,1,22
UNION
SELECT 4,'Apples',10,2,2,22
UNION
SELECT 5,'Granny Smith',10,4,3,22
UNION
SELECT 6,'Ozark Gold',20,4,3,22
UNION
SELECT 7,'Red Delicious',30,4,3,22
UNION
SELECT 8,'Oranges',20,2,2,22
UNION
SELECT 9,'Valencia',10,8,3,22
UNION
SELECT 10,'Hamlin',20,8,3,22
UNION
SELECT 11,'Squash',10,3,2,22
UNION
SELECT 12,'Gold Acorn',10,11,3,22
UNION
SELECT 13,'Turban',20,11,3,22
UNION
SELECT 14,'Yellow',20,11,3,22
UNION
SELECT 15,'Beans',20,3,2,22
UNION
SELECT 16,'Dry',10,15,3,22
UNION
SELECT 17,'Pinto',10,16,4,22
UNION
SELECT 18,'Navy',20,16,4,22
UNION
SELECT 19,'Green',20,15,3,22
UNION
SELECT 20,'Red Swan',10,19,4,22
UNION
SELECT 21,'Blue Lake',20,19,4,22


Now for the code which uses a recursive CTE to build the hierarchy.


;WITH ProductLevels (LocationID,ID,ParentID,HLevel,Hierarchy,SortCode)
AS (
SELECT
LocationID
,ID
,ParentID
,0 AS HLevel
,CAST('//' + REPLACE(REPLACE(REPLACE(REPLACE(ItemDesc,'&',''),'?',''),' ',''),'.','') AS NVARCHAR(255)) AS Hierarchy
,REPLICATE('0',3-LEN(LocationID))
+ CAST(LocationID AS VARCHAR) + '/' +
+ REPLICATE('0',6-LEN(ROW_NUMBER() OVER (ORDER BY Sort)))
+ CONVERT(VARCHAR(MAX),RIGHT(CONVERT(VARCHAR,ROW_NUMBER() OVER (ORDER BY Sort)),6)) AS SortCode
FROM
#TempTable
WHERE
ParentID = 0
AND Sort > 0

UNION ALL

SELECT
t.LocationID
,t.ID
,t.ParentID
,r.HLevel + 1
,CAST(r.Hierarchy + '//'+ REPLACE(REPLACE(REPLACE(REPLACE(t.ItemDesc,'&',''),'?',''),' ',''),'.','') AS NVARCHAR(255)) AS Hierarchy
,CONVERT(VARCHAR(MAX),r.SortCode + '/'
+ REPLICATE('0',5-LEN(ROW_NUMBER() OVER (ORDER BY t.Sort)))
+ CAST(r.[HLevel] AS VARCHAR)+RIGHT(CONVERT(VARCHAR,ROW_NUMBER() OVER (ORDER BY t.Sort)),6)) AS SortCode
FROM
#TempTable AS t
INNER JOIN
ProductLevels AS r
ON t.ParentID = r.ID
WHERE
t.Sort > 0
)
SELECT
LocationID
,ID
,ISNULL(ParentID,0) AS ParentID
,HLevel
,Hierarchy
,SortCode
FROM
ProductLevels
ORDER BY
SortCode
OPTION (MAXRECURSION 0)


The output:


ID ParentID HLevel Hierarchy
1 0 0 //FoodProducts
2 1 1 //FoodProducts//Fruit
4 2 2 //FoodProducts//Fruit//Apples
5 4 3 //FoodProducts//Fruit//Apples//GrannySmith
6 4 3 //FoodProducts//Fruit//Apples//OzarkGold
7 4 3 //FoodProducts//Fruit//Apples//RedDelicious
8 2 2 //FoodProducts//Fruit//Oranges
9 8 3 //FoodProducts//Fruit//Oranges//Valencia
10 8 3 //FoodProducts//Fruit//Oranges//Hamlin
3 1 1 //FoodProducts//Vegetables
11 3 2 //FoodProducts//Vegetables//Squash
12 11 3 //FoodProducts//Vegetables//Squash//GoldAcorn
13 11 3 //FoodProducts//Vegetables//Squash//Turban
14 11 3 //FoodProducts//Vegetables//Squash//Yellow
15 3 2 //FoodProducts//Vegetables//Beans
16 15 3 //FoodProducts//Vegetables//Beans//Dry
17 16 4 //FoodProducts//Vegetables//Beans//Dry//Pinto
18 16 4 //FoodProducts//Vegetables//Beans//Dry//Navy
19 15 3 //FoodProducts//Vegetables//Beans//Green
20 19 4 //FoodProducts//Vegetables//Beans//Green//RedSwan
21 19 4 //FoodProducts//Vegetables//Beans//Green//BlueLake


 
Post #1419209
Posted Tuesday, February 12, 2013 11:06 PM


SSC-Dedicated

SSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-Dedicated

Group: General Forum Members
Last Login: Today @ 11:36 AM
Points: 32,890, Visits: 26,759
sku370870 (2/12/2013)
Hi, and thank you for your answer.

Following Jeff Moden's answer (and link) - I modified my code to have a sort key that ended up returning...

\6
\6\7
\6\7\12
\6\7\8
\6\7\8\13

... which seems to do what I need.

Is there some advantage to creating the sort key in the form you used (using REPLICATE etc.)?

Also, when you said 'if I wanted a nested hierarchy' - what do you mean by that? I thought I had (now, with the sort key) got a nested hierarchy. Items that belong to each other are now appearing in order and their Level allows me, in the front end, to indent as required to physically display the list with nested indents?


That was "step 1".

Shifting gears, you can use a similar method to what Steve used for his hierarchical path to sort on. You can also make it a bit more scalable if you don't mind it being less readable by humans using a BINARY(4) conversion. It will definitely sort an 8 before a 12, as well. I explain how and why you might want to do that in the articles listed further below.

The other thing is the "nested hierarchy". If it's what I'm thinking, the correct term is actually "Nested Sets Hierarchy" or just "Nested Sets" for short. For more information on that miracle of efficiency, please see the following links...

This link explains how nested sets work and how to build them. Unfortunately, they posted the code as graphics instead of as I gave it to them but the explanation of how nested sets work make it worth the visit.
http://blogs.msdn.com/b/mvpawardprogram/archive/2012/06/25/hierarchies-convert-adjacency-list-to-nested-sets.aspx

The following article contains a much more detailed explanation and slightly more performant code for converting an "Adjacency List" (Parent/Child table like what you have) to Nested Sets.
http://www.sqlservercentral.com/articles/Hierarchy/94040/

Then we take a bold step into the inner space of the "Black Arts" of SQL. The following article shows a method to answer most hierarchical questions all in one nice, easy to use, preaggregated table not unlike a precalculated cube.
http://www.sqlservercentral.com/articles/Hierarchy/94040/

Yeah... I know. Looks like a whole lot of self promotion. I apologize for that but I believe the articles really are worth the read if you're going to have to work with hierarchies (Directed Acyclic Graphs like Org Charts, BOMs, etc).


--Jeff Moden
"RBAR is pronounced "ree-bar" and is a "Modenism" for "Row-By-Agonizing-Row".

First step towards the paradigm shift of writing Set Based code:
Stop thinking about what you want to do to a row... think, instead, of what you want to do to a column."

For better, quicker answers on T-SQL questions, click on the following...
http://www.sqlservercentral.com/articles/Best+Practices/61537/

For better answers on performance questions, click on the following...
http://www.sqlservercentral.com/articles/SQLServerCentral/66909/
Post #1419300
« Prev Topic | Next Topic »

Add to briefcase

Permissions Expand / Collapse