.NET Questions (CLOSED)

Questions and Answers on any aspect of .NET. Now closed.

This discussion group is now closed.

Have a question about .NET development? Try stackoverflow.com, a worldwide community of great developers asking and answering questions 24 hours a day.

The archives of .NET Questions contain years of Q&A. Even older .NET Questions are still online, too.

Database hierarchy

interesting SQL question here.

I have a table with 3 columns, a pk, a string value and a parent id.

Each row in the table can have a parent id that links to the pk of another row in that table. So you can pick an item and trace it via the parent all the way to the top of the tree (hope that makes sense).

However the problem I have is I want to trace down the tree. So I would pick an item, and I would want to bring back every item in the same table that has the picked item as the parent and follow all the roots down the tree so the query would come back with the whole list

If this makes sense does anyone have any ideas?
Tony
Tuesday, January 09, 2007
 
 
If you are allowed to modify the DB structure then look into "nested sets", http://www.codeproject.com/database/nestedsets.asp is a good start.

If you can't modify the database then it is not really possible in straight SQL (I don't think, I've never really tried because I just use nested sets when I need to do this). Most likely you would have to resort to some sort of procedural solution.
Chris Send private email
Tuesday, January 09, 2007
 
 
Have you taken a moment to read Celko's book on trees & SQL?
http://www.elsevier.com/wps/find/bookbibliographicinfo.cws_home/702605/description?navopenmenu=4
http://willets.org/sqlgraphs.html

Also, you might like to look how other folks handle "bill of materials" which is a manufacturing term.
Peter
Tuesday, January 09, 2007
 
 
Christopher Wells Send private email
Tuesday, January 09, 2007
 
 
Celko's nested sets are neat if you can modify the table and then figure out how to keep everything updated.

In general, I've found the most resources by searching for SQL + Bills of Material and SQL + geneology, although I'm sure that even a search for Nested Sets will turn up competing strategies.

If you can't modify the table, then try this psuedo code (maybe in a stored procedure or user-defined function). The loop makes it procedural in nature, but at least each iteration is a set-based operation.

----------------------------
Create procedure getDescendents(parentID)
as
Create temp table #tmp(pk, parentPK, level)
insertLevel = 0
-- insert the first row (level 0) to get the top of the tree (the starting point for your traversal)
insert into #tmp select pk, parentPK, insertLevel from heirarchy where heirarchy.pk = parentID
recordsInserted = affectedRecords --should be == 1

while recordsInsert > 0
begin
insertLevel = insertLevel + 1 --increment the level

-- create a join between heirarchy and #tmp that gets all records that have a parentPK == the pk for records at the next lower level
insert into #tmp select pk, parentPK, insertLevel from heirarchy left join #tmp on #tmp.PK = heirarchy.parentPK where #tmp.level = insertLevel - 1

recordsInserted = affectedRecords --did we actually do anything?
end
return #tmp
----------------------------------

I don't know if my off-the-cuff pseudo-code has everything quite right, but I hope the general principle is clear.

An interesting modification would be to include a field for a dotted-notation (pk.pk.pk) so that level could be calculated by counting dots, 'like' could be used to extract sub-trees, simple parsing could be used to retrieve the ancestry of any node, and sorting puts everything in 'treeview order'. As a result, this modification makes the result set trivial to stuff into a tree-view control or otherwise represent as a visual tree. To do the dotted notation stuff, add a 'tree string' field to #tmp and modify the SQL to continually concatenate #temp.treeString and heirarchy.pk. Obviously, the level field is technically unnecessary, but it does simplify processing because you don't need to 'count dots' on the fly. An obvious problem with this is that you could need a pretty huge field to contain the fully concatenated notation, especially if you're using GUIDs. Additional tinkering should get you to the point where you are starting with 1, then 1.1, 1.2, 1.3, 1.1.1, 1.1.2, etc. as you increase the depth and the number of siblings at any level.

If you can put a limit on the maximum number of levels in the tree, you can also add as many copies of the hierarchy table as you have levels, with joins from one copy's pk to the next copy's parentPK. A small BoM program I used once placed an upper limit of 7 levels, so the same table was added to the visual query designer 7 times, joins were made as appropriate and it actually worked pretty good. While this imposes a limit on the number of levels that can be handled, it has the advantage of being a pure set-based operation so it can be a straight query or view instead of a stored procedure or function. Of course, that puts each 'level' in a different column...

A variation on that theme (i.e. multiple copies of the table all joined appropriately) would be to represent it as a union query so that the number of fields in the result set remains constant regardless of the number of levels you define. If you can figure that one out, then you might even be able to remove the restriction on the number of levels by running another job that builds the appropriate statement. (I never thought of this apprach until after I stopped working with BoMs, so I've never tried it. I'm starting back into BoMs, so I might give it a go.)

There you go. Such as it is, that's literally everything I know about processing hierarchies. I hope there is something useful in there. Good luck!
Ron Porter Send private email
Wednesday, January 10, 2007
 
 
Ron, Thats very similar to how I've done it :) although I'm liking your way

I create two temp tables instead and as I looped, after I populate the temp table that I return I also populate another temp table that told me what i had already searched for, so I didn't search for them again

cheers
Tony
Wednesday, January 10, 2007
 
 
If you are using SQL Server 2005, you can use a Common Table Expression (CTE). If you do a google search, you can see some examples of how to do it.
Rick
Wednesday, January 10, 2007
 
 
Yes, I've informed my boss of that :). But unfortunatly we are using MySQL for this project :(. At least I get to learn something new :)
Tony
Thursday, January 11, 2007
 
 
+1
to using pk.pk.pk I usually call it path and use "/" instead of "."

Same as MS heirrchical controls from Access 1.1.
Interestingly this is similar to XPath.

Thursday, January 18, 2007
 
 

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
 
Powered by FogBugz