Re: recursive to tree conversion?

In article <4oksut$fgf@omni1.voicenet.com>, Scott Gray <gray@voicenet.com> wrote: >There are some *very* nice algorithms for representing hierarchical >structures in a relational database using only base SQL92 features >(without cursors or recursion), which I have had great success with >in the past. I would recommend reading "SQL for Smarties" for >some examples. > >If there is sufficient interest, I can provide some examples. Ok, I threw the following together, so I'm not promising that it is entirely correct, but I hope that y'all find it useful. It is written with a heavy slant towards Sybase, for obvious reasons, but could easily be ported to other platforms. I know that I said this didn't involve cursors, but this example minimally involves them, and it should be relatively easy to implement it without cursor. -scott ----------------------------[ snip ]-------------------------- Alright, so you wanna know more about representing hierarchies in a relational database? Before I get in to the nitty gritty I should at least give all of the credit for this algorithm to: "_Hierarical_Structures:_The_Relational_Taboo!_, _(Can_ Transitive_Closure_Queries_be_Efficient?)_", by Michael J. Kamfonas as published in 1992 "Relational Journal" (I don't know which volume or issue). The basic algorithm goes like this, given a tree (hierarchy) that looks roughly like this (forgive the ASCII art--I hope you are using a fixed font to view this): a / \\ / \\ / \\ b c / \\ /|\\ / \\ / | \\ / \\ / | \\ d e f g h (note, that the tree need not be balanced for this algorithm to work). The next step assigned two numbers to each node in the tree, called left and right numbers, such that the left and right numbers of each node contain the left and right numbers of the ancestors of that node (I'll get into the algorithm for assigning these left and right numbers later, but, hint: use a depth-first search): 1a16 / \\ / \\ / \\ 2b7 8c15 / \\ /|\\ / \\ / | \\ / \\ / | \\ 3d4 5e6 9f10 11g12 13h14 Side Note: The careful observer will notice that these left and right numbers look an awful lot like a B-Tree index. So, you will notice that all of the children of node 'a' have left and right numbers between 1 and 16, and likewise all of the children of 'c' have left and right numbers between 8 and 15. In a slightly more relational format this table would look like: Table: hier node parent left_nbr right_nbr ----- ------ -------- --------- a NULL 1 16 b a 2 7 c a 8 15 d b 3 4 e b 5 6 f c 9 10 g c 11 12 h c 13 14 So, given a node name, say @node (in Sybase variable format), and you want to know all of the children of the node you can do: SELECT h2.node FROM hier h1, hier h2 WHERE h1.node = @node AND h2.left_nbr > h1.left_nbr AND h2.left_nbr < h1.right_nbr If you had a table that contained, say, the salary for each node in your hierarchy (assuming a node is actually a individual in a company) you could then figure out the total salary for all of the people working underneath of @node by doing: SELECT sum(s.salary) FROM hier h1, hier h2, salary s WHERE h1.node = @node AND h2.left_nbr > h1.left_nbr AND h2.left_nbr < h1.right_nbr AND s.node = h2.node Pretty cool, eh? And, conversly, if you wanted to know how much it cost to manage @node (i.e. the combined salary of all of the boss's of @node), you can do: SELECT sum(s.salary) FROM hier h1, hier h2, salary s WHERE h1.node = @node AND h2.left_nbr < h1.left_nbr AND h2.left_nbr > h1.right_nbr AND s.node = h2.node Now that you can see the algorithm in action everything looks peachy, however the sticky point is the method in which left and right numbers get assigned. And, unfortunately, there is no easy method to do this relationally (it can be done, it just ain't that easy). For an real- world application that I have worked on, we had an external program used to build and maintain the hierarchies, and it was this program's responsibility to assign the left and right numbers. But, in brief, here is the algorithm to assign left and right numbers to every node in a hierarchy. Note while reading this that this algorithm uses an array as a stack, however since arrays are not available in Sybase, they are (questionably) emulated using a temp table. DECLARE @skip int, @counter int, @idx int, @left_nbr int, @node varchar(10) /*-- Initialize variables --*/ SELECT @skip = 1000, /* Leave gaps in left & right numbers */ @counter = 0, /* Counter of next available left number */ @idx = 0 /* Index into array */ /* * The following table is used to emulate an array for Sybase, * for Oracle this wouldn't be a problem. :( */ CREATE TABLE #a ( idx int NOT NULL, node varchar(10) NOT NULL, left_nbr int NOT NULL ) /* * I know that I always preach about not using cursors, and there * are ways to get around it, but in this case I am more worried * about readability over performance. */ DECLARE root_cur CURSOR FOR SELECT h.node FROM hier h WHERE h.parent IS NULL FOR READ ONLY /* * Here we are populating our "stack" with all of the root * nodes of the hierarchy. We are using the cursor in order * to assign an increasing index into the "stack"...this could * be done using an identity column and a little trickery. */ OPEN root_cur FETCH root_cur INTO @node WHILE (@@sqlstatus = 0) BEGIN SELECT @idx = @idx + 1 INSERT INTO #a VALUES (@idx, @node, 0) FETCH root_cur INTO @node END CLOSE root_cur DEALLOCATE CURSOR root_cur /