rknowles


I need to traverse a hierarchy of objects and return an XML element for members of that hierarchy that are of a certain type. I have already written several functions that can traverse the hierarchy (recursion is great, ain't it ) to do certain things but, I am at a loss to figure out how to filter for certain types (by CLASS_ID, in the specific table I am using) but continue the recursion regardless of whether I return an element for the current row, or not.

Here is my example.

ALTER FUNCTION [dbo].[fn_GetSceneHeirarchyXML](@SceneID int)
RETURNS XML
WITH RETURNS NULL ON NULL INPUT
BEGIN
RETURN
(SELECT s.ID As "@id",
s.PARENT_ID as "@parentID",
s.CLASS_ID as "@clsID",
s.TITLE as "@title",
CASE WHEN s.PARENT_ID=@SceneID
THEN dbo.fn_GetSceneHeirarchyXML(s.ID)
END
FROM dbo.SCENE s
WHERE s.PARENT_ID = @SceneID
FOR XML PATH('Scene'), TYPE)
END

How can I filter the results by returning a 'Scene' element for only those records that have a CLASS_ID = 201, but continue through the recursion, regardless of the CLASS_ID that of the current row

I hope I am explaining my problem clearly enough.

Thanks in advance for any advice you can give.




Re: Here is a real brain twister for a recursive function!

hunchback


Can you post some sample data and expected result

AMB







Re: Here is a real brain twister for a recursive function!

rknowles

Thank you for your response.

Source Table:
ID PARENT_ID CLASS_ID TITLE
1017 1016 201 Scene #1 Title
1018 1017 401 Scene #2 Title
1019 1018 201 Scene #3 Title
1020 1019 201 Scene #4 Title


Desired Result:
<Scene id="1017" parentID="1016" clsID="201" title="Scene #1 Title">
<Scene id="1019" parentID="1018" clsID="201" title="Scene #3 Title">
<Scene id="1020" parentID="1019" clsID="201" title="Scene #4 Title">
</Scene>
</Scene>
</Scene>

The sample data has been dramatically simplified. The "child" scenes would not necessarily come directly after their parents in the real data but, I think this will be enough to give you the idea. I don't want to include Scene #2 in my result but, I do want the recursion to continue on to the "descendants" of Scene #2.

Thanks again for your response and any advice you can give.







Re: Here is a real brain twister for a recursive function!

hunchback

I am not handy with XML and it is difficult for me to implement what you want with the model you are suing to represent the hierarchy (Adjacency List). May be you can consider using another model like "Materialized Path".

You can read about "Materialized Path", in the book:

Inside SQL Server 2005: T-SQL Querying (by Itzik Ben-Gan, Lubor Kollar and Dejan Sarka)

Chapter 9 - Graphs, Trees, Hierarchies, and Recursive Queries

Code Snippet

use northwind

go

create function dbo.mat_path (

@ID int

)

returns varchar(256)

as

begin

declare @lvl int

declare @s varchar(256)

set @lvl = 0

;with cte

as

(

select ID, PARENT_ID, convert(varchar(256), ID) as mat_path, @lvl as lvl

from dbo.t1

where ID = @ID

union all

select

p.ID, p.PARENT_ID, convert(varchar(256), ltrim(p.ID) + '.' + c.mat_path), c.lvl + 1

from dbo.t1 as p inner join cte as c on p.ID = c.PARENT_ID

)

select top 1 @s = mat_path

from cte

order by lvl DESC

return @s

end

go

create table dbo.t1 (

ID int not null unique,

PARENT_ID int null references dbo.t1(ID),

CLASS_ID int,

TITLE varchar(50),

mat_path varchar(256)

)

go

insert into dbo.t1(ID, PARENT_ID, CLASS_ID, TITLE) values(1016, NULL, 201, 'Scene #0 Title')

insert into dbo.t1(ID, PARENT_ID, CLASS_ID, TITLE) values(1017, 1016, 201, 'Scene #1 Title')

insert into dbo.t1(ID, PARENT_ID, CLASS_ID, TITLE) values(1018, 1017, 401, 'Scene #2 Title')

insert into dbo.t1(ID, PARENT_ID, CLASS_ID, TITLE) values(1019, 1018, 201, 'Scene #3 Title')

insert into dbo.t1(ID, PARENT_ID, CLASS_ID, TITLE) values(1020, 1019, 201, 'Scene #4 Title')

go

update dbo.t1

set mat_path = dbo.mat_path(ID)

go

create unique index t1_mat_path_u_nc_ix

on dbo.t1(mat_path)

go

select * from dbo.t1

go

create FUNCTION [dbo].[fn_GetSceneHeirarchyXML](

@mat_path varchar(max))

RETURNS XML

WITH RETURNS NULL ON NULL INPUT

BEGIN

RETURN

(

SELECT

s.ID As "@id",

s.PARENT_ID as "@parentID",

s.CLASS_ID as "@clsID",

s.TITLE as "@title",

dbo.fn_GetSceneHeirarchyXML(

(

select top 1 a.mat_path

from dbo.t1 as a

where a.mat_path like s.mat_path + '.%' and a.CLASS_ID = 201

order by len(a.mat_path)

)

)

FROM

dbo.t1 s

WHERE

s.mat_path like @mat_path

FOR XML PATH('Scene'), TYPE

)

END

go

declare @x xml

select @x = [dbo].[fn_GetSceneHeirarchyXML](1016)

select @x

go

drop function [dbo].[fn_GetSceneHeirarchyXML]

go

drop table dbo.t1

go

drop function dbo.mat_path

go

AMB




Re: Here is a real brain twister for a recursive function!

rknowles

WOW. Thank you for your response, and for all the work you put into it. It will take a while for me digest all this. But I will create it in my DB and test it today.
I have not done much work with XML myself, only a few functions.

Thanks again. I will post later today with the results I get.




Re: Here is a real brain twister for a recursive function!

Manivannan.D.Sekaran

Tried with out function....

/*

Desireed Output

<data Id="1" Parent="0">

<data Id="2" Parent="1">

<data Id="3" Parent="2"></data>

<data Id="4" Parent="2"></data>

</data>

<data Id="5" Parent="1"></data>

<data Id="6" Parent="1"></data>

<data Id="7" Parent="1">

<data Id="8" Parent="7">

<data Id="10" Parent="8">

<data Id="11" Parent="10"></data>

</data>

<data Id="9" Parent="8"></data>

</data>

</data>

</data>'

*/

Create table #Data(

Id int,

Parent Int

)

Insert Into #Data Values(1,0);

Insert Into #Data Values(2,1);

Insert Into #Data Values(5,1);

Insert Into #Data Values(6,1);

Insert Into #Data Values(7,1);

Insert Into #Data Values(8,7);

Insert Into #Data Values(9,8);

Insert Into #Data Values(10,8);

Insert Into #Data Values(11,10);

Insert Into #Data Values(3,2);

Insert Into #Data Values(4,2);

With CTE

as

(

Select

Id

,Parent

,Replace(Cast((Select Id,Parent From #Data data Where Id=Main.Id For Xml Auto, Type) as Varchar(max)),'/>', '>[Child-' + Cast(Id as Varchar) + ']</data>') Xml

From

#data Main

)

,PathFinder --Recursive

as

(

Select * , cast(Id as varchar) path from CTE Where id=1

Union all

Select d.* , Cast(q.path + '\' + cast(d.Id as varchar) as varchar) path from Cte d Join PathFinder q on d.parent=q.id

)

, Ordered

as

(

select *,Row_Number() Over (order By path) RowId from PathFinder

)

, Engager --Recursive

as

(

select id,parent,xml,rowid from Ordered where rowid=1

Union all

Select d.id,d.parent,replace(q.xml,'[Child-' + cast(d.parent as varchar) +']', d.xml + '[Child-' + cast(d.parent as varchar) +']'),d.rowid

From Ordered d Join Engager q on d.Rowid-1 = q.RowId

)

, XMLValue

as

(

Select Id,RowId,(Select Xml from Engager Where rowid = (select Max(rowId) from Engager)) as XML From Engager

)

, RollBacker --Recursive

as

(

Select Rowid, Replace(Xml,'[Child-' + cast(id as varchar) +']','') Xml From XMLValue Where Rowid=1

Union All

Select d.RowId, Replace(q.Xml,'[Child-' + cast(d.id as varchar) +']','') Xml From XMLValue D Join RollBacker q On d.RowId-1=q.Rowid

)

Select Cast(Xml as Xml) From RollBacker Where rowid = (select Max(rowId) from Engager)






Re: Here is a real brain twister for a recursive function!

rknowles

Manivannan,

Thank you for your response, as well.

I tested you query, and it does work well but, it does not accomplish what I am trying to do. I have a query that returns the complete result set, as yours does, in a nested XML representation. What I am trying to accomplish is filtering out certain records (based on class ID) without filtering any of the "children" of those records that might meet the filter criterita. So, if you have a record set like:
ID PARENT_ID CLASS_ID TITLE
1 0 201 First Record
2 0 201 Second Record
15 1 401 Fifteenth Record
27 15 201 Twenty Seventh Record
29 2 201 Twenty Ninth Record
35 29 401 Thirty Fifth Record
105 35 321 One Hundred and First Record
107 105 201 One Hundred and Seventh Record

and I filtered out all records that are not CLASS_ID = 201, I would get the following result in XML:
<Scene id="1" parentID="0" clsID="201" title="First Record">
<Scene id=27 parentID="15" clsID=201" title="Twenty Seventh Record">
</Scene>
</Scene>
<Scene id="2" parentID="0" clsID="201" title="Second Record">
<Scene id="107" parentID="105" clsID="201" title="One Hundred and Seventh Record>
</Scene>
</Scene>

so...the records that have a CLASS_ID != 201 are filtered out of the hierarchical result but, their "descendants" that DO have as CLASS_ID = 201 are included.

A bonus would be to "correct" the parentIDs in the XML result so that, for instance, Scene #27 would have a parentID=1, since it is now listed as a child of Scene #1.
But, I can live without that because it would be simple enough to write a function to do that in my ASP code.

Anyway, thanks again for your response.






Re: Here is a real brain twister for a recursive function!

Curtis Ruppe

I thought long and hard about this one, because I knew you had most of the code for the recursion already in place. Here is your answer.

Code Snippet

ALTER FUNCTION [dbo].[fn_GetSceneHeirarchyXML](@SceneID int)

RETURNS XML

WITH RETURNS NULL ON NULL INPUT

BEGIN

RETURN

(

CASE WHEN @SceneID IN (SELECT PARENT_ID FROM dbo.Scene WHERE CLASS_ID = 201) THEN

(

SELECT s.ID As [@id],

s.PARENT_ID as [@parentID],

s.CLASS_ID as [@clsID],

s.TITLE as [@title],

CASE WHEN s.PARENT_ID=@SceneID

THEN dbo.fn_GetSceneHeirarchyXML(s.ID)

END

FROM dbo.SCENE s

WHERE s.PARENT_ID = @SceneID

FOR XML PATH('Scene'), TYPE

)

ELSE

(

CASE WHEN @SceneID IN (SELECT PARENT_ID FROM dbo.Scene WHERE CLASS_ID <> 201) THEN

(

SELECT dbo.fn_GetSceneHeirarchyXML(ID) FROM dbo.Scene WHERE PARENT_ID = @SceneID

)

END

)

END

)

END

I hope this suits you well. Good luck!

PS: By adding a secondary variable to the function, you could possibly get this to produce the extra bonus you are looking for, but here's the code for that (I haven't fully tested it, so I may be wrong on this.

Code Snippet

ALTER FUNCTION [dbo].[fn_GetSceneHeirarchyXML](@SceneID int, @ParentID int)

RETURNS XML

WITH RETURNS NULL ON NULL INPUT

BEGIN

RETURN

(

CASE WHEN @SceneID IN (SELECT PARENT_ID FROM dbo.Scene WHERE CLASS_ID = 201) THEN

(

SELECT s.ID As [@id],

@ParentID as [@parentID],

s.CLASS_ID as [@clsID],

s.TITLE as [@title],

CASE WHEN s.PARENT_ID=@SceneID

THEN dbo.fn_GetSceneHeirarchyXML(s.ID, s.ID)

END

FROM dbo.SCENE s

WHERE s.PARENT_ID = @SceneID

FOR XML PATH('Scene'), TYPE

)

ELSE

(

CASE WHEN @SceneID IN (SELECT PARENT_ID FROM dbo.Scene WHERE CLASS_ID <> 201) THEN

(

SELECT dbo.fn_GetSceneHeirarchyXML(ID, @ParentID) FROM dbo.Scene WHERE PARENT_ID = @SceneID

)

END

)

END

)

END

Hopefully that resolves that. Thanks for the brain teaser!





Re: Here is a real brain twister for a recursive function!

rknowles

Curtis,

Thank you for your response!

Your first example looks exactly like the procedure I have been trying to conceptualize all day. I knew that I needed to have the Case - Else structure that you have written but, I was away from my computer all day today, and was unable to work it out. It was really neat to see your solution waiting on me when I returned home.

I just copied your first solution and ran it in my database. I received the following error:
Subquery returned more than 1 value. This is not permitted when the subquery follows =, !=, <, <= , >, >= or when the subquery is used as an expression.

I haven't had time to work through it yet but, I will take some time to do that.

I still haven't tested Hunchback's original solution either. I will do that one now too.

Thanks for your help, and your work. I will continue trying to resolve this. Your solution looks like the one I have been envisioning. I will continue working with it.

Thanks again.
roger




Re: Here is a real brain twister for a recursive function!

rknowles

Hunchback,

Thanks for your response.
I tested your code, and received the following result set:

1016 NULL 201 Scene #0 Title 1016
1017 1016 201 Scene #1 Title 1016.1017
1018 1017 401 Scene #2 Title 1016.1017.1018
1019 1018 201 Scene #3 Title 1016.1017.1018.1019
1020 1019 201 Scene #4 Title 1016.1017.1018.1019.1020

This is not the result set that I wanted (the record with classID = 401 should be omitted) but, I the mat_path column is very interesting. I am certain I can utilize that in the future.

Also, thank you for the book recommendation. I have some good books on SQL Server 2005 but, from the information I saw on Amazon.com about Inside SQL Server 2005: T-SQL Querying, it looks like it covers much more sophisticated concepts. I think I am almost ready for a book like that. I have added it to my Amazon wish list, and will get it soon.

Thanks again. I will keep studying your solution because there are concepts, and syntaxes, in it that are unfamiliar to me.




Re: Here is a real brain twister for a recursive function!

rknowles

Curtis, you are right!

That is the solution. I just added " FOR XML PATH('Scene'), TYPE" at the end of the SELECT statement in the Else condition, and that was it!

I will continue testing it out as soon as I finish celebration (I know, I have it backwards...test first, celebrate later).

WOOHOO!

Thanks a million!




Re: Here is a real brain twister for a recursive function!

Curtis Ruppe

As much as it pains me to say it, my logic is invalid. I will post again when I think of a better solution.



Re: Here is a real brain twister for a recursive function!

Curtis Ruppe

Here is more accurate code. Upon inspection, you would have had an issue whenever two IDs that shared a parent would have one as a 201 record and the other as some other classid. This will fix it, but note, it requires a cursor...

Code Snippet

ALTER FUNCTION [dbo].[fn_GetSceneHeirarchyXML](@SceneID int)

RETURNS XML

WITH RETURNS NULL ON NULL INPUT

BEGIN

DECLARE @doc xml, @docInner xml

DECLARE @id int, @parentid int, @classID int, @title varchar(MAX)

DECLARE scene_cursor cursor

FOR SELECT ID, PARENT_ID, CLASS_ID, TITLE, dbo.fn_GetSceneHeirarchyXML(ID) FROM dbo.Scene WHERE PARENT_ID=@SceneID

OPEN scene_cursor

FETCH NEXT FROM scene_cursor INTO @id, @parentid, @classID, @title, @docInner

WHILE @@FETCH_STATUS = 0

BEGIN

IF @classID = 201

BEGIN

SET @doc = CAST(CAST(IsNull(@doc, '') as varchar(MAX)) + CAST((SELECT @id [@id], @parentid [@parentID], @classID [@clsID], @title [@title], @docInner FOR XML PATH('Scene'), TYPE) as varchar(MAX)) as xml)

END

ELSE

BEGIN

SET @doc = CAST(CAST(IsNull(@doc, '') as varchar(MAX))+ CAST(IsNull(@docInner, '') as varchar(MAX)) as xml)

END

FETCH NEXT FROM scene_cursor INTO @id, @parentid, @classID, @title, @docInner

END

CLOSE scene_cursor

DEALLOCATE scene_cursor

RETURN @doc

END

Note the CAST with varchar(MAX) back to xml. This is because there is no UNION operator for XML without doing a deep dive into xml.modify(), which I'll leave up for you, if you wish to do so.

Sorry for the false answer before, but this should get you back on track.




Re: Here is a real brain twister for a recursive function!

rknowles

Curtis,

Thank you for your continued work on this. I put the latest version of your solution into my database for testing, and we are still not getting the results we are looking for. It is returning only elements that meet the clsID=201 criteria but the hierarchical structure of the results has been lost. The results are coming back with multiple root nodes, and confused relationships. I will keep working on this - but, in the mean time, I can write some code in my ASP files to parse the xml results, removing the elements that don't meet the CLASS_ID criteria and editing the "parentID" property of the children of the removed element to point to the parent of the removed element.

That shouldn't be hard to do.

But, I will continue working on this problem. I would think that it would be nice to have a function that will traverse a hierarchical structure and return the elements that meet a certain criteria while excluding those elements that don't.

Thanks again for your work on this. I will post whatever progress I make.




Re: Here is a real brain twister for a recursive function!

Manivannan.D.Sekaran

I didn't give up myself too Smile.. here the updated query without function

Code Snippet

/*

Desired Output

<Root>

<data Id="2" PARENT_ID="0" CLASS_ID="201" TITLE="Second Record">

<data Id="29" PARENT_ID="2" CLASS_ID="201" TITLE="Twenty Ninth Record">

<data Id="35" PARENT_ID="29" CLASS_ID="401" TITLE="Thirty Fifth Record">

<data Id="105" PARENT_ID="35" CLASS_ID="321" TITLE="One Hundred and First Record">

<data Id="107" PARENT_ID="105" CLASS_ID="201" TITLE="One Hundred and Seventh Record">

</data>

</data>

</data>

</data>

</data>

<data Id="1" PARENT_ID="0" CLASS_ID="201" TITLE="First Record">

<data Id="15" PARENT_ID="1" CLASS_ID="401" TITLE="Fifteenth Record">

<data Id="27" PARENT_ID="15" CLASS_ID="201" TITLE="Twenty Seventh Record">

</data>

</data>

</data>

</Root>

*/

Create Table #data (

[ID] int ,

[PARENT_ID] int ,

[CLASS_ID] int ,

[TITLE] Varchar(100)

);

Insert Into #data Values('1','0','201','First Record');

Insert Into #data Values('2','0','201','Second Record');

Insert Into #data Values('15','1','401','Fifteenth Record');

Insert Into #data Values('27','15','201','Twenty Seventh Record');

Insert Into #data Values('29','2','201','Twenty Ninth Record');

Insert Into #data Values('35','29','401','Thirty Fifth Record');

Insert Into #data Values('105','35','321','One Hundred and First Record');

Insert Into #data Values('107','105','201','One Hundred and Seventh Record');

Declare @XMLData as Varchar(Max);

Set @XMLData = '<Root>'

;With CTE

as

(

Select

Id

,PARENT_ID

,CLASS_ID

,TITLE

,Replace(Cast((Select Id,PARENT_ID,CLASS_ID,TITLE From #Data data Where Id=Main.Id For Xml Auto, Type) as Varchar(max)),'/>', '>[Child-' + Cast(Id as Varchar) + ']</data>') Xml

From

#data Main

)

,PathFinder --Recursive

as

(

Select * , cast(Id as varchar) path from CTE Where [PARENT_ID]=0

Union all

Select d.* , Cast(q.path + '\' + cast(d.Id as varchar) as varchar) path from Cte d Join PathFinder q on d.PARENT_ID=q.id

)

, Ordered

as

(

select *,Substring(path+'\',1,CharIndex('\',path+'\')-1) RootNode,Row_Number() Over (Partition By Substring(path+'\',1,CharIndex('\',path+'\')-1) order By path) RowId from PathFinder

)

, Engager --Recursive

as

(

select id,PARENT_ID,CLASS_ID,TITLE,xml,rowid,RootNode from Ordered where rowid=1

Union all

Select d.id,d.PARENT_ID,d.CLASS_ID,d.TITLE,replace(q.xml,'[Child-' + cast(d.PARENT_ID as varchar) +']', d.xml + '[Child-' + cast(d.PARENT_ID as varchar) +']'),d.rowid,d.RootNode

From Ordered d Join Engager q on d.Rowid-1 = q.RowId And d.RootNode = q.RootNode

)

, LeafXMLValue

as

(

Select mx.RootNode,Xml from Engager E Join (select RootNode,Max(rowId) rowid from Engager Group By RootNode) as Mx On E.rowid = Mx.rowid And E.RootNode=Mx.RootNode

)

, XMLValue

as

(

Select Id,RowId,RootNode,(Select XML from LeafXMLValue Where LeafXMLValue.RootNode=Ordered.RootNode) XML from Ordered

)

, RollBacker --Recursive

as

(

Select Rowid,RootNode, Replace(Xml,'[Child-' + cast(id as varchar) +']','') Xml From XMLValue Where Rowid=1

Union All

Select d.RowId,d.RootNode, Replace(q.Xml,'[Child-' + cast(d.id as varchar) +']','') Xml From XMLValue D Join RollBacker q On d.RowId-1=q.Rowid and d.RootNode=q.RootNode

)

Select

@XMLData = @XMLData + Xml

From

RollBacker R

Join (select RootNode,Max(rowId) rowid from Engager Group By RootNode)

as Mx On R.rowid = Mx.rowid And R.RootNode=Mx.RootNode

Select @XMLData + '</Root>'