if you have the pleasure to work with Oracle, it is all taken care of for you.. "connect by" takes care of everything for you. no coding necessary. In 9i you can
o order the hierarchy in a connect by o join a connect by o get the "connect by path" It is not available before. Here is an example from 9i [EMAIL PROTECTED]> create or replace view v 2 as 3 select emp.ename, emp.empno, emp.mgr, dept.dname from emp, dept where emp.deptno = dept.deptno 4 / View created. [EMAIL PROTECTED]> column EmpName format a30 [EMAIL PROTECTED]> select rpad('*',2*level,'*')||ename EmpName, dname 2 from v connect by a join... 3 start with mgr is null 4 connect by prior empno = mgr 5 / EMPNAME DNAME ------------------------------ -------------- **KING ACCOUNTING ****CLARK ACCOUNTING ******MILLER ACCOUNTING ****JONES RESEARCH ******FORD RESEARCH ********SMITH RESEARCH ******SCOTT RESEARCH ********ADAMS RESEARCH ****BLAKE SALES ******ALLEN SALES ******JAMES SALES ******WARD SALES ******TURNER SALES ******MARTIN SALES 14 rows selected. [EMAIL PROTECTED]> [EMAIL PROTECTED]> [EMAIL PROTECTED]> [EMAIL PROTECTED]> select rpad('*',2*level,'*')||ename EmpName, dname 2 from v 3 start with mgr is null 4 connect by prior empno = mgr 5 order SIBLINGS by ename Order the hierarchy 6 / EMPNAME DNAME ------------------------------ -------------- **KING ACCOUNTING ****BLAKE SALES ******ALLEN SALES ******JAMES SALES ******MARTIN SALES ******TURNER SALES ******WARD SALES ****CLARK ACCOUNTING ******MILLER ACCOUNTING ****JONES RESEARCH ******FORD RESEARCH ********SMITH RESEARCH ******SCOTT RESEARCH ********ADAMS RESEARCH 14 rows selected. [EMAIL PROTECTED]> [EMAIL PROTECTED]> column cbp format a30 [EMAIL PROTECTED]> [EMAIL PROTECTED]> select rpad('*',2*level,'*')||ename EmpName, dname, 2 sys_connect_by_path( ename, '/' ) cbp 3 from v 4 start with mgr is null 5 connect by prior empno = mgr 6 order SIBLINGS by ename 7 / EMPNAME DNAME CBP ------------------------------ -------------- ------------------------------ **KING ACCOUNTING /KING ****BLAKE SALES /KING/BLAKE ******ALLEN SALES /KING/BLAKE/ALLEN ******JAMES SALES /KING/BLAKE/JAMES ******MARTIN SALES /KING/BLAKE/MARTIN ******TURNER SALES /KING/BLAKE/TURNER ******WARD SALES /KING/BLAKE/WARD ****CLARK ACCOUNTING /KING/CLARK ******MILLER ACCOUNTING /KING/CLARK/MILLER ****JONES RESEARCH /KING/JONES ******FORD RESEARCH /KING/JONES/FORD ********SMITH RESEARCH /KING/JONES/FORD/SMITH ******SCOTT RESEARCH /KING/JONES/SCOTT ********ADAMS RESEARCH /KING/JONES/SCOTT/ADAMS 14 rows selected. Chuck Fox <[EMAIL PROTECTED]> wrote: I have done this in a production environment. THIS IS NOT TO BE UNDERTAKING BY THE FAINT OF HEART. Caveats: I have used multi parented relationships. In a static environment this is not a big issue. In an environment where constant reparenting occurs, along with the attendant woes of widow and orphaned hierarchies, use dynamic sql and a cursoring technique and in terms of the table just store the parent key and the child key. In the years since I first did this, CPU and disk speeds have more than made up for the cost of constructing the hierarchy on the fly. There are a number of solutions to this problem. Attached are theory behind how I implemented an idea that is quite similar to yours. While it was a very interesting problem and the solution is rather elegant, maintenance can become a nightmare. Take it from someone who implemented this for a table of about a million parent->child relationships. If you are interested in a full blown example, please contact me directly. Your Friendly Neighborhood DBA, Chuck [EMAIL PROTECTED] wrote: >Hi all, > >I have question about storing hierarchical values in db. I found some >methods, pick up the first easiest, but I ahve question about that - >have someone coded some methods, or knows some module, which helps me >with this issue ? > >Ok, here is infos: > >MYSQL tables: >CREATE TABLE `cat_name` ( > `id` int(11) unsigned NOT NULL auto_increment, > `cat_name` varchar(150) NOT NULL default '', > PRIMARY KEY (`id`), > UNIQUE KEY `cat_name` (`cat_name`) >) ENGINE=MyISAM DEFAULT CHARSET=utf8 > >CREATE TABLE `cat_tree` ( > `id` int(9) unsigned NOT NULL auto_increment, > `parent_id` int(11) unsigned NOT NULL default '0', > `child_id` int(11) unsigned NOT NULL default '0', > PRIMARY KEY (`id`), > KEY `parent_id` (`parent_id`), > KEY `child_id` (`child_id`) >) ENGINE=MyISAM DEFAULT CHARSET=utf8 > >input data: > >name = 'some name...' >category = 'foo/bar/foo/bar' >name = 'something other...' >category = 'foo/bar/foo/bar' > >Perl snippet: > >foreach my $cat ( split '/', $hr->{category} ) { > next if $hash{$cat}++; #skip duplicates > $hr->{cat_id} = cat_get($cat) || cat_insert($cat); > print $hr->{cat_id}, "\n"; > #need other functions to store/get (recursive) values into cat_tree >} > >sub cat_get { > my ($id) = $dbh->selectrow_array("select id from cat_name where cat_name = > ?", {}, shift); > return ($id); >} > >sub cat_insert { > my $cat_insert = $dbh->prepare("INSERT INTO cat_name (cat_name) values (?)"); > $cat_insert->execute( shift ); > return $dbh->{'mysql_insertid'}; >} > >I don't know if this problem is solved like my "code", but it it my >first try. Could anyone helps on this, please ? > >thanks. > > > From: [EMAIL PROTECTED] (Scott Gray) Date: 3 Jun 1996 08:02:07 -0400 Subject: Re: recursive to tree conversion? Message-ID: <[EMAIL PROTECTED]> Organization: VoiceNet Internet Access In article <[EMAIL PROTECTED]>, Scott Gray 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 /* * The following cursor will be employed to retrieve all of * the children of a given parent. */ DECLARE child_cur CURSOR FOR SELECT h.node FROM hier h WHERE h.parent = @node FOR READ ONLY /* * While our stack is not empty. */ WHILE (@idx > 0) BEGIN /* * Look at the element on the top of the stack. */ SELECT @node = node, @left_nbr = left_nbr FROM #a WHERE idx = @idx /* * If the element at the top of the stack has not been assigned * a left number yet, then we assign it one and copy its children * on the stack as "nodes to be looked at". */ IF (@left_nbr = 0) BEGIN /* * Set the left number of the current node to be @counter + @skip. * Note, we are doing a depth-first traversal, assigning left * numbers as we go. */ SELECT @counter = @counter + @skip UPDATE #a SET left_nbr = @counter WHERE idx = @idx /* * Append the children of the current node to the "stack". */ OPEN child_cur FETCH child_cur INTO @node WHILE (@@sqlstatus = 0) BEGIN SELECT @idx = @idx + 1 INSERT INTO #a VALUES (@idx, @node, 0) FETCH child_cur INTO @node END CLOSE child_cur END ELSE BEGIN /* * It turns out that the current node already has a left * number assigned to it, so we just need to assign the * right number and update the node in the actual * hierarchy. */ SELECT @counter = @counter + @skip UPDATE h SET left_nbr = @left_nbr, right_nbr = @counter WHERE h.node = @node /* * "Pop" the current node off our "stack". */ DELETE #a WHERE idx = @idx SELECT @idx = @idx - 1 END END /* WHILE (@idx > 0) */ DEALLOCATE CURSOR child_cur While reading through this, you should notice that assigning the left and right numbers to the entire hierarchy is very costly, especially as the size of the hierarchy grows. If you put the above code in an insert trigger on the hier table, the overhead for inserting each node would be phenominal. However, it is possible to reduce the overall cost of an insertion into the hierarchy. 1. By leaving huge gaps in the left & right numbers (using the @skip variable), you can reduce the circumstances in which the numbers need to be reassigned for a given insert. Thus, as long as you can squeeze a new node between an existing pair of left and right numbers you don't need to do the re-assignment (which could affect all of the node in the hierarchy). 2. By keeping an extra flag around in the hier table to indicate which nodes are leaf nodes (this could be maintained with a trigger as well), you avoid placing leaf nodes in the array and thus reduce the number of updates. Deletes on this table should never cause the left and right numbers to be re-assigned (you could even have a trigger automagically re-parent orphaned hierarchy nodes). All-in-all, this algorithm is very effective as long as the structure of the hierarchy does not change very often, and even then, as you can see, there are ways of getting around a lot of its inefficiencies. -- Scott C. Gray [EMAIL PROTECTED] Sybase Professional Services [EMAIL PROTECTED] http://www.voicenet.com/~gray/sqsh.html --------------------------------- Discover Yahoo! Find restaurants, movies, travel & more fun for the weekend. Check it out!