Recursive Query for Formatted Output

Itech · June 11th, 2008, 03:28 PM

Hello All,

if this has already been addressed please forward me the forum post.
----------
Scenario:
Database Schema
ID ParentID Name
1 0 Root1
2 0 Root2
3 1 Root1_Child1
4 1 Root1_Child2
5 2 Root2_Child1
6 3 Root1_Child1_SubChild1
7 3 Root1_Child1_SubChild2

A select All would output as follows

ID ParentID FormattedPath
1 0 0/Root1
2 0 0/Root2
3 1 0/Root1/Root1_Child1
4 1 0/Root1/Root1_Child2
5 2 0/Root2/Root2_Child1
6 3 0/Root1/Root1_Child1/Root1_Child1_SubChild1
7 3 0/Root1/Root1_Child1/Root1_Child1_SubChild2

i used strings for the Formatted path just so you can see a better visual, i will end up using the ID. for example instead of the formatted output of '0/Root2/Root2_Child1' i will need '0/2/5'

thank you in advance for the help

Old Pedant · June 11th, 2008, 06:36 PM

Well, actually the right answer is to *STORE* your data in the form you are showing, or nearly so.

I do it like this:

Code:

ID  ParentID  Path             Name
1   0         0001             Root1
2   0         0002             Root2
3   1         0001-0003        Root1_Child1
4   1         0001-0004        Root1_Child2
5   2         0002-0005        Root2_Child1
6   3         0001-0003-0006   Root1_Child1_SubChild1
7   3         0001-0003-0007   Root1_Child1_SubChild2

That is, PATH is a VARCHAR that uses "padded" ids of fixed length. And so now, if you do an ORDER BY PATH you get

Code:

ID  ParentID  Path             Name
1   0         0001             Root1
3   1         0001-0003        Root1_Child1
4   1         0001-0004        Root1_Child2
6   3         0001-0003-0006   Root1_Child1_SubChild1
7   3         0001-0003-0007   Root1_Child1_SubChild2
2   0         0002             Root2
5   2         0002-0005        Root2_Child1

Ideal for building "tree" structures. And building the PATH field as you create the table is going to get you the best possible performance, later.

But starting from the other end is tougher...

SQL Server doesn't do well with recursion, though SQL Server 2005 has some new support for it that I haven't tried yet.

If you *KNOW* the maximum "depth" of your tree, you could clearly build this in a single query using a UNION and a SELECT for each "depth".

Otherwise, I think you'd need to use a Stored Procedure, cursors, a temporary table, etc.

Old Pedant · June 11th, 2008, 06:38 PM

OOPS! Minor goof...got the ORDER BY PATH wrong:

Should of course be

Code:

ID  ParentID  Path             Name
1   0         0001             Root1
3   1         0001-0003        Root1_Child1
6   3         0001-0003-0006   Root1_Child1_SubChild1
7   3         0001-0003-0007   Root1_Child1_SubChild2
4   1         0001-0004        Root1_Child2
2   0         0002             Root2
5   2         0002-0005        Root2_Child1

Itech · June 11th, 2008, 07:51 PM

i see, well, if i do know the depth, lets say only depth of 2, can you provide me an example? thanks for the reply btw

Old Pedant · June 11th, 2008, 08:38 PM

Well, to get literally what you asked for:

Code:

SELECT id, parentid, name AS path, name 
FROM demo 
WHERE parentid = 0
     UNION
SELECT D2.id, D2.parentid, D1.name + '/' + D2.name, D2.name
FROM demo AS D1, demo AS D2
WHERE D2.parentid = D1.id AND D1.parentid = 0
     UNION
SELECT D3.id, D3.parentid, D1.name + '/' + D2.name + '/' + D3.name, D3.name
FROM demo AS D1, demo AS D2, demo AS D3
WHERE D3.parentid = D2.id AND D2.parentid = D1.id AND D1.parentid = 0
ORDER BY id;

Here's what I mean by "path" and what I think you mean, as well:

Code:

SELECT id, parentid, RIGHT('0000' + CSTR(id),4) AS path, name 
FROM demo 
WHERE parentid = 0
    UNION
SELECT D2.id, D2.parentid,RIGHT('0000'+CSTR(D1.id),4)+':'+RIGHT('0000'+CSTR(D2.id),4), D2.name
FROM demo AS D1, demo AS D2
WHERE D2.parentid = D1.id AND D1.parentid = 0
    UNION 
SELECT D3.id, D3.parentid,RIGHT('0000'+CSTR(D1.id),4)+':'+RIGHT('0000'+CSTR(D2.id),4)+':'+RIGHT('0000'+CSTR(D3.id),4), D3.name
FROM demo AS D1, demo AS D2, demo AS D3
WHERE D3.parentid = D2.id AND D2.parentid = D1.id AND D1.parentid = 0
ORDER BY path;

That use of
    CSTR(...)
is Access, which is how I tested this. In SQL Server, you would change
    CSTR(...)
to
    CONVERT(VARCHAR(100),...)

Old Pedant · June 11th, 2008, 08:41 PM

That last query produces this output (your data, except names changed/simplified a tad...sorry):

Code:

id   parentid path              name
1    0        0001              root1
3    1        0001:0003         r1, child 1
6    3        0001:0003:0006    r1, c1, grandkid 1
7    3        0001:0003:0007    r1, c1, grandkid2
4    1        0001:0004         r1, child 2
2    0        0002              root2
5    2        0002:0005         r2, child 1

Old Pedant · June 11th, 2008, 08:53 PM

Last comment...

The query looks ugly, but it will actually perform pretty well. I would think you could use up two a depth of 5 or 6 (I call what I showed "depth 3") and get decent performance. Even if it just so happened that your actual data depth is (say) only 4.

planoie · June 12th, 2008, 07:54 AM

Old Pedant-

What happens when you need to move a node of the tree structure? There's a bit of work involved with recomputing child nodes if you are storing discreet paths in each.

SQL Server 2005's Common Table Expression capability is rather good at dealing with recursive structures.

-Peter
compiledthoughts.com

Itech · June 12th, 2008, 09:54 AM

thank you very much Pedant, i'll give her a try, also thanks Planoie for the Suggestion, i'm going to look into both options actually.

Old Pedant · June 12th, 2008, 01:36 PM

To Planoie:

Yes, I mentioned that SQL Server 2005 had recursion capabilities that I hadn't yet used.

Granted, using a "path" is much better used for read-only data. But there are tons of examples of such data in the real world. For example, forum posts. (Well, if the forum code is smarter than this mildly braindead one, such that you can reply to a particular message instead of just to the topic/thread.)

Anyway, he doesn't have a path, just the it/parentid relationship. So if you could show him how to produce his desired output using SQL Server 2005 recursion, it would be appreciated, I'm sure!