SQL Server Forums
Profile | Register | Active Topics | Members | Search | Forum FAQ
 
Register Now and get your question answered!
Username:
Password:
Save Password
Forgot your Password?

 All Forums
 Site Related Forums
 Article Discussion
 Article: More Trees & Hierarchies in SQL
 New Topic  Reply to Topic
 Printer Friendly
Previous Page | Next Page
Author Previous Topic Topic Next Topic
Page: of 7

dgottlieb
Starting Member

1 Posts

Posted - 05/31/2002 :  13:39:13  Show Profile  Reply with Quote
Hi,

I am working on a tree problem similar to that discussed in the article – a hierarchy of folders and hyperlinks. However, there is one key difference. When I display the tree, I need to show the nodes sorted alphabetically under each parent. I can do this using recursion, but I can't figure out how to do this in pure SQL. Any thoughts?

On a related note, I also need to be able to hide spacific nodes (and their children) from certain user groups when I display the tree. Does anyone know of an elegant way to integrate this into the tree?

Thanks,
Dan
Go to Top of Page

julesr
Starting Member

United Kingdom
13 Posts

Posted - 06/04/2002 :  19:30:33  Show Profile  Visit julesr's Homepage  Send julesr an ICQ Message  Reply with Quote
Interesting article. I tend to show my tree structures using XML, but this gives food for thought. I look forward to reading about your logic for inserting/updating/deleting nodes.

Jules
http://www.charon.co.uk
Go to Top of Page

jcelko
Esteemed SQL Purist

USA
547 Posts

Posted - 06/17/2002 :  12:32:11  Show Profile  Visit jcelko's Homepage  Reply with Quote
>> I am having difficultiy with one aspect. What happens when your tree data looks like this...

CREATE TABLE Tree
(emp CHAR(10) NOT NULL,
boss CHAR(10));

insert INTO Tree values ('Jerry',NULL);
insert INTO Tree values ('Bert','Jerry');
insert INTO Tree values ('Chuck','Jerry');
insert INTO Tree values ('Donna','Chuck');
insert INTO Tree values ('Eddie','Chuck');
insert INTO Tree values ('Fred','Chuck');
insert INTO Tree values ('Page47',NULL);
insert INTO Tree values ('Sloan','Page47');

 
...Such that there are multiple trees in the forest, ie. multiple roots? <<

1) that thing is not a table because it has no key. Let's ignore that, since this is a quickie posting

2) A tree has one and only one root by definition. In the nested set model, the lft of the root =1.

3) A forest is a set of disjoint trees. What I think you mean was:

emp tree lft rgt
-------------------
Jerry 1 1 12
Bert 1 2 3
Chuck 1 4 11
Donna 1 5 6
Eddie 1 7 8
Fred 1 9 10
Page47 2 1 4
Sloan 2 2 3

Which ever root you put on the stack to start will get processed into (lft,rgt) pairs.



--CELKO--
Joe Celko, SQL Guru
Go to Top of Page

Page47
Flowing Fount of Yak Knowledge

USA
2878 Posts

Posted - 06/17/2002 :  12:53:28  Show Profile  Reply with Quote
Joe, thanks for the reply.

I suppose I was thinking that the nested-set model dml could work without the 'tree' column as long as the left/right pairs were mutually exclusive for each tree. I guess not.



<O>
Go to Top of Page

prasannas
Starting Member

1 Posts

Posted - 06/25/2002 :  12:49:57  Show Profile  Reply with Quote
Hunting around google groups I found this link in a post http://www.utdt.edu/~mig/sql-trees

The paper is titled "Genealogical Representation of Trees in Databases" (what a mouthful).

Basically the same concept as the article but in order to save on space they convert the id to another base (i.e something greater than base 10). You can do a number of variations on the same concept. I have modest needs (1024 children at most) so I can represent each node as 2 chars.

I don't know how it will perform compared to Celko's method. I guess the more people who experiment with both methods the more we can understand the pros and cons of each.

/prasanna

Go to Top of Page

Johnhamman
Starting Member

37 Posts

Posted - 07/13/2002 :  14:06:35  Show Profile  Visit Johnhamman's Homepage  Reply with Quote
robvolk,
When can we see the followup to this article???

Question.
How would I select 'Ian Faith' and its child employees?
Without selecting another Boss that has the same parentnode and lineage?

Denis Eaton-Hogg
Bobbi Flekman
-> Ian Faith
David St. Hubbins
Nigel Tufnel
Derek Smalls

-john

Go to Top of Page

ja928
Starting Member

USA
5 Posts

Posted - 07/28/2002 :  16:43:58  Show Profile  Reply with Quote
The lineage idea is great. My only caveat is that I added this to a hierarchy table in SQL 2000 and it caused me errors setting up merge replication. I changed the name to "heritage" since my replication snapshot said that the name lineage caused conflicts. I'm not sure that this was the only solution, but we were under intense time pressure.

Go to Top of Page

macka
Posting Yak Master

United Kingdom
162 Posts

Posted - 07/31/2002 :  05:41:26  Show Profile  Reply with Quote
Not really an SQL problem as such, but does anyone happen to know if there any any funky XSL Transforms which will take the nested set structure as input and output a nested XML document ?

ie. Transform this:


<?xml version="1.0"?>
<root>
<rec id="1" lft="1" rgt="8" />
<rec id="2" lft="2" rgt="7" />
<rec id="3" lft="3" rgt="4" />
<rec id="4" lft="5" rgt="6" />
</root>


into this:


<?xml version="1.0"?>
<root>
<rec id="1" lft="1" rgt="8">
<rec id="2" lft="2" rgt="7">
<rec id="3" lft="3" rgt="4" />
<rec id="4" lft="5" rgt="6" />
</rec>
</rec>
</root>


Cheers,

macka.


Edited by - macka on 07/31/2002 05:43:00
Go to Top of Page

macka
Posting Yak Master

United Kingdom
162 Posts

Posted - 08/05/2002 :  04:25:43  Show Profile  Reply with Quote
In answer to my own question.

With a great deal of help from my new best friend over at MarrowSoft (www.marrowsoft.com), the following XSL seems to work as long as the input is sorted by lft ascending. I guess this could be done in the XSL, but for simplicity, I'm sorting it when I create the XML document.


<?xml version="1.0"?>
<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
<xsl:output method="xml" indent="yes"/>
<xsl:template match="root">
<root>
<!-- do the fist (highest) in hierarchy -->
<xsl:apply-templates select="rec[1]"/>
</root>
</xsl:template>
<xsl:template match="rec">
<!-- copy this node -->
<xsl:copy>
<!-- copy all existing atts and child nodes -->
<xsl:copy-of select="@*|node()"/>
<!-- do first hierarchic child (if any) -->
<xsl:apply-templates select="following-sibling::rec[@lft > current()/@lft and @rgt < current()/@rgt][1]"/>
</xsl:copy>
<!-- do next hierarchic sibling (if any) -->
<xsl:apply-templates select="following-sibling::rec[@lft = (current()/@rgt + 1)][1]"/>
</xsl:template>
</xsl:stylesheet>


Cheers,

macka.

Go to Top of Page

SamC
White Water Yakist

USA
3461 Posts

Posted - 08/06/2002 :  23:37:10  Show Profile  Reply with Quote
Rob,

Great article. I need to implement a tree based org table myself very soon.

Looking forward to the follow up article.

SamC


Go to Top of Page

rive
Starting Member

3 Posts

Posted - 08/22/2002 :  21:03:59  Show Profile  Reply with Quote
Hi People,

Using the article data, how would I get the id number of the boss to an employee?

Say i wanted my results like so,
EmployeeId,Name,BossId

The best I can come up with is

SELECT
EmployeeId,
Name,
(SELECT EmployeeId FROM Tree WHERE Node = (SELECT ParentNode FROM Tree WHERE EmployeeId = Employees.EmployeeId) ) As BossId
FROM
Employees

-- This example has not been tested, but it is working on my version (tables renamed, etc so went with article table names)

The question, is there a better/faster way of doing this?

Thanks,
Rive,

Go to Top of Page

rive
Starting Member

3 Posts

Posted - 08/22/2002 :  21:13:53  Show Profile  Reply with Quote
A minute after posting, i realised a better way. Don't I feel like an idiot!

Rive,

Go to Top of Page

AjarnMark
SQL Slashing Gunting Master

USA
3246 Posts

Posted - 08/23/2002 :  12:58:34  Show Profile  Visit AjarnMark's Homepage  Reply with Quote
quote:

A minute after posting, i realised a better way. Don't I feel like an idiot!



Rive, why don't you post it for everyone to see and learn from?

Go to Top of Page

digory
Starting Member

Australia
13 Posts

Posted - 08/26/2002 :  11:12:38  Show Profile  Visit digory's Homepage  Reply with Quote
Great article. I've seen this method described before, but your article was extremely concise. I had the whole thing implemented in a project that I'm working on in less than 2 hours.


Darren Neimke - MCP
http://www.MarkItUp.com/
darren AT showusyourcode DOT com

Good as it is to inherit a library, it is better to collect one
- Augustine Birrell

Go to Top of Page

rive
Starting Member

3 Posts

Posted - 08/29/2002 :  22:01:47  Show Profile  Reply with Quote
quote:

Rive, why don't you post it for everyone to see and learn from?



Ok, the way that i found was to join the table to itself (EmployeeId to BossId), as in this article.
http://www.sqlteam.com/item.asp?ItemID=1333

Rive,

Go to Top of Page

Blastrix
Posting Yak Master

208 Posts

Posted - 09/01/2002 :  04:54:57  Show Profile  Reply with Quote
Hey Rob,
When is part two of this article coming? I'm really interested in seeing how you perform some other operations with this list.

I also have some problems with the sorting. In the example you gave, everything will sort correctly with order, but will not alphabetize. What is your suggestion to alphabetize the list?

Thanks
Steve

Go to Top of Page

Bill Wilkinson
Starting Member

USA
7 Posts

Posted - 09/23/2002 :  14:47:52  Show Profile  Reply with Quote
Perhaps the second part of this article covers this problem, but just in case:

THERE IS A FATAL FLAW in this scheme!

It works FINE if the node numbers are all of the same length when converted to strings, but it fails when the lengths vary.

Consider if you had both 3 and 4 digit node numbers.

Now the Lineage field might contain entries such as:

/932/1001/1055
/1004/1122

And immediately we go KABLOOEY!

Because now an ORDER BY will *reverse* the natural (numerical) order of those records!

You *MUST* pad the node numbers (with spaces or zeroes...matters not) up to the expected maximum length of any node number.

This has been discussed before!

http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=6202

"graz" suggested it first, and then I made a couple of comments on it as well.

Go to Top of Page

rtips
Starting Member

2 Posts

Posted - 10/15/2002 :  12:57:40  Show Profile  Reply with Quote


What are the disadvantages (besides possible performance issues) of doing the following -

- keep the relationships/hierarchies in a simple adjaency set way in a table.
- retrieve part of the table that includes all the hierarchy members using 1 database hit
- walk this recordset recursively in the application program (using traditional programming language) and creating whatever display view is required.

why does one need to use stored procedures to get the tree hierarchies out of the store. why not just use a simple application programming algorithm with the apporpriate data structures ?



Go to Top of Page

AjarnMark
SQL Slashing Gunting Master

USA
3246 Posts

Posted - 10/15/2002 :  17:18:17  Show Profile  Visit AjarnMark's Homepage  Reply with Quote
quote:
What are the disadvantages (besides possible performance issues)

I'd say that'a a pretty big hit if you have a sizeable dataset.

quote:
- retrieve part of the table that includes all the hierarchy members using 1 database hit

Ahhh, but the trick is, HOW do you know which records should be included and get this in "1 database hit"? Unless you are retrieving ALL the records (back to the big performance hit) you will have to recursively walk through the data in SQL Server.

quote:
- walk this recordset recursively in the application program (using traditional programming language) and creating whatever display view is required.

why does one need to use stored procedures to get the tree hierarchies out of the store. why not just use a simple application programming algorithm with the apporpriate data structures ?

What do you consider a "simple application programming algorithm"? What is the largest set of data you have recursively walked through with only a couple of seconds of elapsed time? If you're dealing with the web, every second counts big! Ever had a page time-out?

Go to Top of Page

AjarnMark
SQL Slashing Gunting Master

USA
3246 Posts

Posted - 10/15/2002 :  17:29:29  Show Profile  Visit AjarnMark's Homepage  Reply with Quote
quote:
THERE IS A FATAL FLAW in this scheme!

It works FINE if the node numbers are all of the same length when converted to strings, but it fails when the lengths vary.



Bill, I read the other link and still don't see the issue here. Yes, I understand that if you want to sort by hierarchy-list, then one like 1001/YYY/YYYY would come before 999/XXX/XXXX. But my question is, why is this relevant or important in this scenario? Believe me, in many other situations, this has been a big pain for me, but for this situation, you're still going to get all the people that report to manager 1001 grouped together. And you can still select everyone who is under person 1001/YYY and sort order doesn't make a whit of difference.

So I guess my question is, why do you care about it? What's the issue that you have run into?

Thanks for sharing!

Go to Top of Page
Page: of 7 Previous Topic Topic Next Topic  
Previous Page | Next Page
 New Topic  Reply to Topic
 Printer Friendly
Jump To:
SQL Server Forums © 2000-2009 SQLTeam Publishing, LLC Go To Top Of Page
This page was generated in 0.2 seconds. Powered By: Snitz Forums 2000