Today's question comes from Kurt M.:
While your article at http://4guysfromrolla.com/webtech/sqlguru/q120899-1.shtml answered the basic question of Michael S., I was hoping that you'd go farther into this issue.
I'm interested (and I'll bet Michael S. is, too) in learning if there is a way to apply such recursive joins in such a manner that a single
SELECTquery will return all the nodes in a tree in their proper order.
If, as in Mike's example, we have:PostID ParentID
Any record (tree node) can be the parent of multiple records and the child of only one or none. What I (and probably Mike) would like to know is, is it possible to construct a single SQL statement that will return all of these nodes in their proper depth order with their breadth levels. This statement would mimic a recursive loop, whereas your method (and those derived directly from it with more recursive levels) are restricted to a maximum number of recursions.
In my understanding, such a setup is currently not possible within the current SQL language and even using non standard Oracle or SQL Server tools. The only solution I've seen that allows such records to be SELECTED and and returned in their proper depth order with their breadth level depends on the use of one of two types of dot hash columns.
Any thoughts on this issue?
Business Systems & Reporting
Kurt, you asked:
What I (and probably Mike) would like to know is, is it possible to construct a single SQL statement that will return all of these nodes in their proper depth order with their breadth levels.
Probably, but you'd have to be a little tricky about it. Here's what I'm thinking you would need:
1) Multiple recursive joins up to the maximum tree depth you'd like. Of course, there is usually an imposed limit on the number of joins in a query (e.g. SQL6.5 limits you to 16 joins). In reality, there is always a practical limit on the number of joins you can perform. However, if you were really a masochist, you could probably write something that dynamically generates the proper SQL syntax with the correct joins, as long as your tree wasn't too deep.
2) Some way to combine results from the different incarnations of the table
into a set of columns that made sense. Possibly with outer joins and
3) Some way to calculate depth on the fly in the query.... hmm, can't think of a solution to this one off the top of my head.
Or you could use the tactics traditional programming languages use: recursion or iteration. A recursive SP (SQL, at least in MS SQLServer does support recursion) could traverse the tree and spit out the results you want. Of course, this would give you multiple resultsets. Or, you could use an iterative approach with a cursor and a stack(temptable).
But all that sounds like a lot of trouble. If you don't mind storing a little extra information (hey, disk space is cheap), why not just store a post's depth and root post ID when it's added to the table? That would effectively flatten the information, while still retaining the proper relationships between posts. You could calculate the post's depth with a cute little recursive proc that you call when you insert the post.
Then, you can do a straight run through the table, ordering by root post ID, and depth. Sure, it's less elegant, but sometimes less elegant == working solution :)
(WARNING, shamless produt plug follows) By the way, I'm on my second Dell Latitude laptop, and it rocks!
Note From Scott Mitchell, webmaster of 4Guys:
In the Summer of '99 I was an intern at Microsoft. I worked on a project which contained a table which had recursive definitions upon itself. When a person visited a particular web page, the Microsoft ActiveX TreeView Control would be loaded with the top level items appearing. As the user clicked on each node, the tree would be expanded, and that particular node's children would be loaded.
I also wrote a stored procedure that would return the entire tree structure, using a recursive stored procedure, since we were certain that our depth would, for all practical purposes, be less than 5. So, just wanted to let you know that recursive stored procedures can indeed be used to fully iterate through a complex tree structure.