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

rtips
Starting Member

2 Posts

Posted - 10/15/2002 :  17:53:23  Show Profile  Reply with Quote

quote:

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



lets not assume that all applications that require trees/hierarchies have huge datasets such as message board threads. very simple hierarchical instant messaging buddy lists could be rows in the range of 20-30 with a few groups and a few levels of hierachies.


quote:

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.



Again in my example above tables can be built for buddy list groups that can be keyed off of the userID for example and one can simply do a select of these 20-30 rows on userID

quote:

What do you consider a "simple application programming algorithm"?



Building a tree from this 20-30 rows can be as straight forward as:
Create a tree node
For each data set row
Create a tree node
Insert the tree node at the appropriate place in the tree

Using XmlNode or related classes in .NET for example, one can fairly easily build a XML tree out of the adjacency set rows that were retrieved



Go to Top of Page

robvolk
Most Valuable Yak

USA
15663 Posts

Posted - 10/15/2002 :  18:38:13  Show Profile  Visit robvolk's Homepage  Reply with Quote
quote:
lets not assume that all applications that require trees/hierarchies have huge datasets such as message board threads. very simple hierarchical instant messaging buddy lists could be rows in the range of 20-30 with a few groups and a few levels of hierachies.
True, not everything is a big honking banyan tree with branches all over the place. But at the scale you're talking about, the performance will be about the same no matter which technique you use. Another way of saying it: if all solutions are equally good, why not go with one that scales better? Having to iterate through every node to build a tree will slow down at some point.
quote:
Again in my example above tables can be built for buddy list groups that can be keyed off of the userID for example and one can simply do a select of these 20-30 rows on userID.
That's just a simple 1st generation, NOT a tree. What if there are more than 2 levels? You'd have to use some kid of recursion or iteration.
quote:
Building a tree from this 20-30 rows can be as straight forward as:
Create a tree node
For each data set row
Create a tree node
Insert the tree node at the appropriate place in the tree

Using XmlNode or related classes in .NET for example, one can fairly easily build a XML tree out of the adjacency set rows that were retrieved
That's EXACTLY the point, and the problem as well. Tree/hierarchical data is NOT, repeat NOT, relational data. A tree is bound by its structure; relational data is bound by its values. There has to be a translation of some kind to make a tree structure fit a relational structure.

By keeping the hierarchy/lineage up-to-date and stored with each node, it's just like any other relational data value, and can be queried as such. It eliminates the need to traverse or generate the tree structure simply to retrieve information. Otherwise it would be better to keep the tree structure in XML all the time and not bother with SQL tables at all (this is especially true for the small amount of data you have in your example)

Go to Top of Page

CactusJuice
Starting Member

USA
46 Posts

Posted - 10/16/2002 :  13:34:22  Show Profile  Visit CactusJuice's Homepage  Reply with Quote
I am not new to SQL but this advanced heirarchy stuff is new to me...I am having the hardest time wrapping my mind around it...but I'm giving it a shot...whew! I want to build a registry for German Shepherd owners...basically a familiy tree for dogs. Since this complexity is difficult for me, I am using Rob's example tables/data just to try to get myself into it.

So extrapolating...the youngest dog would be "Derek Smalls" and its great great grand father would be "Denis Eaton Hogg"? Then for the mother's side of the family I add a "Ms Derek Eaton Hogg" to tbl Employees. But then I'm lost with how to handle her in the Tree table. How to handle the dubplicate set of ParentNodes?

Also there are thousands of dogs. Should I be concerned about the "Node" column growing...a la Bill Wilkerson's warning? Mabye seed it with 1000000 just to be safe.

Also, many owners do not know their dog's pedigree (or don't care to enter it) so only some of the dogs from a query will have lineage records.

--Cameron

Edited by - CactusJuice on 10/16/2002 15:40:58
Go to Top of Page

helenrivera74
Starting Member

1 Posts

Posted - 11/12/2002 :  17:51:44  Show Profile  Reply with Quote
I am trying to create a stored procedure to delete a single node from a hierarchy created in SQL using Joe Celko's SQL for Smarties. I am implementing the method where if parent node is deleted, children will be connected to the parent of the original node. (page 458)

I've had a look at the stored procedure "DropNode" and it seems to close the gaps fine. Is there any example that anyone could offer why I would need the views and script to close the gaps (page 460) if I am using the delete method mentioned above.

Go to Top of Page

tkeenan
Starting Member

1 Posts

Posted - 01/03/2003 :  19:09:57  Show Profile  Reply with Quote
SELECT Space(T.Depth*2) + E.Name AS Name
FROM Employees E
INNER JOIN Tree T ON E.EmployeeID=T.EmployeeID
ORDER BY T.Lineage + Ltrim(Str(T.Node,6,0))

Works great if you want to see the entire tree at once, but when dealing with large recordsets, what's the most effective way to retrieve a partial listing of the hierarchies? i.e. the boss and employees of 1003?

Go to Top of Page

robvolk
Most Valuable Yak

USA
15663 Posts

Posted - 01/03/2003 :  20:12:24  Show Profile  Visit robvolk's Homepage  Reply with Quote
LIKE or CharIndex() would work:

SELECT Space(T.Depth*2) + E.Name AS Name
FROM Employees E
INNER JOIN Tree T ON E.EmployeeID=T.EmployeeID
WHERE T.Lineage LIKE '%/1003/%'
--or the following:
--CharIndex(T.Lineage, '/1003/') > 0
ORDER BY T.Lineage + Ltrim(Str(T.Node,6,0))


Go to Top of Page

squishyfish
Starting Member

Australia
1 Posts

Posted - 03/23/2003 :  19:15:18  Show Profile  Reply with Quote
Wondering if Part 2 of your article is out yet or when it is planned?

Thanks.

Go to Top of Page

hotblue
Starting Member

1 Posts

Posted - 05/13/2003 :  17:52:00  Show Profile  Reply with Quote
Fatal Flaw in this technique - it will work only while your lineage column can accomodate the hierarchy. How about a binary tree with, say a depth of 5,000? Tried this technique way, way back, and the db fails whenever the lineage field is overloaded. This code is good enough for a few hundred levels deep. But if it goes beyond that, how would you handle it?


Go to Top of Page

robvolk
Most Valuable Yak

USA
15663 Posts

Posted - 05/13/2003 :  21:50:11  Show Profile  Visit robvolk's Homepage  Reply with Quote
I wouldn't. I can't even conceive of a hierarchy with 5,000 levels. I never suggested that this method was suitable for modeling EVERY kind of tree/hierarchy, and it certainly wouldn't work for a model as extreme as what you're describing.

Not being able to handle that does not constitute a "fatal" flaw, just as not being able to survive a hit by a 20mm cannon shell is a fatal flaw; it's just fatal. It happens to work nicely for org chart and similar structures and I would never need to model even 100 levels of depth with it. Any corporation with over 100 levels of management could never function or organize themselves enough to MAKE an org chart anyway.

Go to Top of Page

smotsie
Starting Member

1 Posts

Posted - 06/02/2003 :  10:39:09  Show Profile  Reply with Quote
OK, so I have a database heirarchy, but I CANNOT get it to sort correctly. What I want is to store in the database a representation of a folder structure, so each level is sorted alphanumerically, and each sub level also, but with correct nesting.

I tried
SELECT Table1.id, Table1.lineage, Table1.name
FROM Table1
ORDER BY Table1.lineage + Table1.name;


but this returns all the 001 records, then all the 001/002...

Does anyone have a way to do this - I want a maximum of 999 nodes per level and 16 levels, so this solution would fit well if I could get it to work!

TIA

Smotsie
Go to Top of Page

freeranger
Starting Member

1 Posts

Posted - 06/05/2003 :  06:37:47  Show Profile  Reply with Quote
I have exactly the same problem as smotsie.
I need to be able to sort by hierarchy level and then alphabetic at each level.
I have tried loads of different ways, but simply cannot get it to work for me.
In my case, it is a personnel tree, which I want to sort by surname, forename within the correct hierarchy level.

any guru's out there have any ideas on this?

thanks,

freeranger
Go to Top of Page

sr1
Starting Member

1 Posts

Posted - 07/15/2003 :  09:03:54  Show Profile  Reply with Quote
First post on this site. I wonder if there's a way to list articles from most recent to oldest starting on the first page?

I, too, saw Celko's posting, this time in an Access ng. The problem with his method is that, if you don't skip-count, by 5s or 10s, or whatever, that you have to modify at least one field in every record whenever you shake up the hierarchy; add, delete, move to another level. It's okay for small lists. But if it gets too big . .

There was an alternative mentioned by Vadim Tropashko, which mapped the same 'materialized path' which is I believe what Volk has presented, here. He wanted the nested set advantage of 'unrolling' the hierarchy for non-nested SQL queries. But the denominator mapping, if I recall, used a binary shift. That's power of 2, and a geometric progression. At some point, it will explode. And I think it was used for each subsequent list item, not only nesting. So it could explode, quickly.

So sticking with the unadultered 'materialized path', might be fine. But I'd be interested to see your part II, where you lay out the actual routines for basic database operations of ADD, MOVE, DELETE, etc. And what queries still pose problems. The advantage, for me, of sticking with adjacency lists is not just that they are intuitive, as Tropashko noted, and common and well documented, but as clumsy as they may be, they do isolate other portions of the table, sort of instead of Celko's knotted rope or thread a more standard broken thread tied periodically and started again. You can't see it all at once. But you can't mess it up all at once.

It is cumbersome, without recursive SQL extensions. If there were a way to avoid 'key explosions', or exhaustive maintanence for routine operations, I could see moving to something else, perhaps - depending.

Go to Top of Page

X002548
Not Just a Number

15586 Posts

Posted - 07/25/2003 :  11:08:21  Show Profile  Reply with Quote
quote:

Wondering if Part 2 of your article is out yet or when it is planned?



quote:

But I'd be interested to see your part II, where you lay out the actual routines for basic database operations of ADD, MOVE, DELETE, etc



That's the first thing I asked...and tried to build...then got busy

Have to back to it..but you have to ask your self questions like.

1. If I delete a node in the middle, do all of his children become children of the grandparent, or do they disappear?

If I move a node, do the children move with it, or do they become the children of the grandparent.

Same thing if you promote a node

What happens if you insert a node between a parent hand his children, does it become the defacto parent? Or a sibling in a different branch?

My troubles were less tecnical, rather than deriving the "rules" on how "events" are to behave.

So I gave up

Lazy SQL Scrub that I am.



Brett

8-)
Go to Top of Page

emdc2
Starting Member

USA
1 Posts

Posted - 08/30/2003 :  12:26:52  Show Profile  Reply with Quote
Great article... are you going to post Part 2 sometime soon?
Go to Top of Page

JGALFO21
Starting Member

4 Posts

Posted - 10/10/2003 :  21:25:53  Show Profile  Visit JGALFO21's Homepage  Reply with Quote
Hey Rob Great article!!!
How about the second part you promise "all the necessary tree operations that are needed (add, delete, move, promote)..."

Did you get around that?

Thanks.
Go to Top of Page

gully
Starting Member

France
2 Posts

Posted - 10/28/2003 :  11:05:52  Show Profile  Reply with Quote
I have used MS Treeview control with ASP.NET and the FOR XML clause it works brilliant to represent a tree with this kind of table structure

I might put the code out if anyone is into it ...


Sir code a lot
Go to Top of Page

austegard
Starting Member

2 Posts

Posted - 10/28/2003 :  11:51:26  Show Profile  Reply with Quote
Rob - I'm just joining the chorus waiting for part 2 of the article...

Meanwhile the technique is similar enough to the one here http://www.yafla.com/papers/sqlhierarchies/sqlhierarchies.htm
that I think I can figure out how to do it. Your solution has the advantage of not having to redo the lineage/SetString everytime for all later siblings and their descendents if a node is removed, though the lineage field could grow large if there were a lot of nodes/levels.

Oskar
Go to Top of Page

settinUpShop
Starting Member

28 Posts

Posted - 11/03/2003 :  12:19:03  Show Profile  Reply with Quote
quote:
Originally posted by AjarnMark

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!





Disclaimer - Newbie to SQL database development

I've created a content management tool for my company, so they can create and edit pages which will be displayed on their website. I'd like to use this model to create a means of creating a tree structure for the various different page's. Right now the pages can be placed into various page sections which I intend on defining as different roots in the tree structure.

for example: the numbers in parens are "Sort_Order" values
Corporate Info
--Who we are (070)
--What we do (040)
--Contact Us (010)

Solutions
--ProductX (095)
----ModuleA (090)
----ModuleB (080)
----ModuleC (070)
--ProductY (040)
----History (090)
----Technology Used (030)
etc.

The sidenav I've create will display one section at a time, depending on which section the user is currently in. Links to the pages under each sub heading, must have a specific order which I can control. Currently I accomplish this by using a "Sort_Order" field in my "PageInfo" table.

If I still want to be able to influence the order in which menu items are going to be displayed then I need to continue to use this field correct? The actual "Node", being an identity column can't be used to sort a group of siblings who share the same parent, bcs the "Node" does not represent the importance of the Node in relation to other simplings.

So to accomplish what I'm attempting would this work? I've converted Employees table to my PageInfo table.

SELECT Space(T.Depth*2) + P.Name AS Name
FROM PageInfo P
INNER JOIN Tree T ON P.PageInfoID=T.PageInfoID
ORDER BY T.Lineage + Ltrim(Str(P.Sort_Order,6,0))

The "Sort_Order" column is kept in the PageInfo table, and accepts values between 0 and 100.

Ah, I can see that's going to be a problem. I'll need to convert single and double digit numbers into three digit numbers with leading zeros, right, based on what BillW pointed out.

Also, and this may be a silly question, but why does Rob suggest using the Ltrim function in the above statement? An int data type isn't going to have any leading space characters is it?

Thanks :)


Edited by - settinUpShop on 11/03/2003 12:19:53
Go to Top of Page

sangle
Starting Member

18 Posts

Posted - 11/04/2003 :  09:46:46  Show Profile  Reply with Quote
can you send me the link to the part 2 of this topic!!
Go to Top of Page

sangle
Starting Member

18 Posts

Posted - 11/04/2003 :  10:20:04  Show Profile  Reply with Quote
Hey rob,
Ur article was really helful...good job!
can u send me a link to the part 2 of this article
:(
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.31 seconds. Powered By: Snitz Forums 2000