| Author |
 Topic  |
|
dgottlieb
Starting Member
1 Posts |
 Posted - 05/31/2002 : 13:39:13
|
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 |
 |
|
|
julesr
Starting Member
United Kingdom
13 Posts |
Posted - 06/04/2002 : 19:30:33
|
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 |
|
|
|
jcelko
Esteemed SQL Purist
USA
547 Posts |
Posted - 06/17/2002 : 12:32:11
|
>> 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
|
|
|
|
Page47
Flowing Fount of Yak Knowledge
USA
2878 Posts |
Posted - 06/17/2002 : 12:53:28
|
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> |
|
|
|
prasannas
Starting Member
1 Posts |
Posted - 06/25/2002 : 12:49:57
|
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
|
|
|
|
Johnhamman
Starting Member
37 Posts |
Posted - 07/13/2002 : 14:06:35
|
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
|
|
|
|
ja928
Starting Member
USA
5 Posts |
Posted - 07/28/2002 : 16:43:58
|
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.
|
|
|
|
macka
Posting Yak Master
United Kingdom
162 Posts |
Posted - 07/31/2002 : 05:41:26
|
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 |
|
|
|
macka
Posting Yak Master
United Kingdom
162 Posts |
Posted - 08/05/2002 : 04:25:43
|
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.
|
|
|
|
SamC
White Water Yakist
USA
3459 Posts |
Posted - 08/06/2002 : 23:37:10
|
Rob,
Great article. I need to implement a tree based org table myself very soon.
Looking forward to the follow up article.
SamC
|
|
|
|
rive
Starting Member
3 Posts |
Posted - 08/22/2002 : 21:03:59
|
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,
|
|
|
|
rive
Starting Member
3 Posts |
Posted - 08/22/2002 : 21:13:53
|
A minute after posting, i realised a better way. Don't I feel like an idiot!
Rive,
|
|
|
|
AjarnMark
SQL Slashing Gunting Master
USA
3246 Posts |
Posted - 08/23/2002 : 12:58:34
|
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?
|
|
|
|
digory
Starting Member
Australia
13 Posts |
Posted - 08/26/2002 : 11:12:38
|
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
|
|
|
|
rive
Starting Member
3 Posts |
Posted - 08/29/2002 : 22:01:47
|
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,
|
|
|
|
Blastrix
Posting Yak Master
208 Posts |
Posted - 09/01/2002 : 04:54:57
|
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
|
|
|
|
Bill Wilkinson
Starting Member
USA
7 Posts |
Posted - 09/23/2002 : 14:47:52
|
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.
|
|
|
|
rtips
Starting Member
2 Posts |
Posted - 10/15/2002 : 12:57:40
|
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 ?
|
|
|
|
AjarnMark
SQL Slashing Gunting Master
USA
3246 Posts |
Posted - 10/15/2002 : 17:18:17
|
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?
|
|
|
|
AjarnMark
SQL Slashing Gunting Master
USA
3246 Posts |
Posted - 10/15/2002 : 17:29:29
|
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!
|
|
|
|
Topic |
|
Article: More Trees & Hierarchies in SQL
