Recipe13.3.Creating a Hierarchical View of a Table

Recipe 13.3. Creating a Hierarchical View of a Table

Problem

You want to return a result set that describes the hierarchy of an entire table. In the case of the EMP table, employee KING has no manager, so KING is the root node. You want to display, starting from KING, all employees under KING and all employees (if any) under KING's subordinates. Ultimately, you want to return the following result set:

 EMP_TREE ------------------------------ KING KING - BLAKE KING - BLAKE - ALLEN KING - BLAKE - JAMES KING - BLAKE - MARTIN KING - BLAKE - TURNER KING - BLAKE - WARD KING - CLARK KING - CLARK - MILLER KING - JONES KING - JONES - FORD KING - JONES - FORD - SMITH KING - JONES - SCOTT KING - JONES - SCOTT - ADAMS 

Solution

DB2 and SQL Server

Use the recursive WITH clause to start building the hierarchy at KING and then ultimately display all the employees. The solution following uses the DB2 concatenation operator "||". SQL Server users use the concatenation operator +. Other than the concatenation operators, the solution will work as-is on both RDBMSs:

  1   with x (ename,empno)  2      as (  3  select cast(ename as varchar(100)),empno  4    from emp  5   where mgr is null    6   union all  7  select cast(x.ename||' - '||e.ename as varchar(100)),  8         e.empno  9    from emp e, x 10   where e.mgr = x.empno 11  ) 12  select ename as emp_tree 13    from x 14   order by 1 

Oracle

Use the CONNECT BY function to define the hierarchy. Use SYS_CONNECT_BY_PATH function to format the output accordingly:

 1  select ltrim( 2           sys_connect_by_path(ename,' - '), 3         ' - ') emp_tree 4    from emp 5    start with mgr is null 6  connect by prior empno=mgr 7    order by 1 

This solution differs from that in the previous recipe in that it includes no filter on the LEVEL pseudo-column. Without the filter, all possible trees (where PRIOR EMPNO=MGR) are displayed.

PostgreSQL

Use three UNIONs and multiple self joins:

  1  select emp_tree  2    from  (  3  select ename as emp_tree  4    from  emp  5   where mgr is null  6  union  7  select a.ename||' - '||b.ename  8    from emp a  9         join 10         emp b on (a.empno=b.mgr) 11   where a.mgr is null 12  union 13  select rtrim(a.ename||' - '||b.ename 14                      ||' - '||c.ename,' - ') 15    from emp a 16         join 17         emp b on (a.empno=b.mgr) 18         left join 19         emp c on (b.empno=c.mgr) 20   where a.ename = 'KING' 21  union 22  select rtrim(a.ename||' - '||b.ename||' - '|| 23               c.ename||' - '||d.ename,' - ') 24    from emp a 25         join 26         emp b on (a.empno=b.mgr) 27         join 28         emp c on (b.empno=c.mgr) 29         left join 30         emp d on (c.empno=d.mgr) 31   where a.ename = 'KING' 32         ) x 33   where tree is not null 34   order by 1 

MySQL

Use three UNIONs and multiple self joins:

  1  select emp_tree  2    from (  3  select ename as emp_tree  4    from emp  5   where mgr is null  6  union  7  select concat(a.ename,' - ',b.ename)  8    from emp a  9         join 10         emp b on (a.empno=b.mgr) 11   where a.mgr is null 12  union 13  select concat(a.ename,' - ', 14                b.ename,' - ',c.ename) 15    from emp a 16         join 17         emp b on (a.empno=b.mgr) 18         left join 19         emp c on (b.empno=c.mgr) 20   where a.ename = 'KING' 21  union 22  select concat(a.ename,' - ',b.ename,' - ', 23                c.ename,' - ',d.ename) 24    from emp a 25         join 26         emp b on (a.empno=b.mgr) 27         join 28         emp c on (b.empno=c.mgr) 29         left join 30         emp d on (c.empno=d.mgr) 31   where a.ename = 'KING' 32         ) x 33   where tree is not null 34   order by 1 

Discussion

DB2 and SQL Server

The first step is to identify the root row (employee KING) in the upper part of the UNION ALL in the recursive view X. The next step is to find KING's subordinates, and their subordinates if there are any, by joining recursive view X to table EMP. Recursion will continue until you've returned all employees. Without the formatting you see in the final result set, the result set returned by the recursive view X is shown below:

  with x (ename,empno)     as ( select cast(ename as varchar(100)),empno   from emp  where mgr is null  union all select cast(e.ename as varchar(100)),e.empno   from emp e, x  where e.mgr = x.empno  )  select ename emp_tree    from x  EMP_TREE  ----------------  KING  JONES  SCOTT  ADAMS  FORD  SMITH  BLAKE  ALLEN  WARD  MARTIN  TURNER  JAMES  CLARK  MILLER 

All the rows in the hierarchy are returned (which can be useful), but without the formatting you cannot tell who the managers are. By concatenating each employee to her manager, you return more meaningful output. Produce the desired output simply by using

 cast(x.ename+','+e.ename as varchar(100)) 

in the SELECT clause of the lower portion of the UNION ALL in recursive view X.

The WITH clause is extremely useful in solving this type of problem, because the hierarchy can change (for example, leaf nodes become branch nodes) without any need to modify the query.

Oracle

The CONNECT BY clause returns the rows in the hierarchy. The START WITH clause defines the root row. If you run the solution without SYS_CONNECT_BY_PATH, you can see that the correct rows are returned (which can be useful), but not formatted to express the relationship of the rows:

  select ename emp_tree   from emp  start with mgr is null connect by prior empno = mgr EMP_TREE ----------------- KING JONES SCOTT ADAMS FORD SMITH BLAKE ALLEN WARD MARTIN TURNER JAMES CLARK MILLER 

By using the pseudo-column LEVEL and the function LPAD, you can see the hierarchy more clearly, and you can ultimately see why SYS_CONNECT_BY_PATH returns the results that you see in the desired output shown earlier:

 select lpad('.',2*level,'.')||ename emp_tree    from emp   start with mgr is null connect by prior empno = mgr EMP_TREE ----------------- ..KING ....JONES ......SCOTT ........ADAMS ......FORD ........SMITH ....BLAKE ......ALLEN ......WARD ......MARTIN ......TURNER ......JAMES ....CLARK ......MILLER 

The indentation in this output indicates who the managers are by nesting subordinates under their superiors. For example, KING works for no one. JONES works for KING. SCOTT works for JONES. ADAMS works for SCOTT.

If you look at the corresponding rows from the solution when using SYS_CONNECT_BY_PATH, you will see that SYS_CONNECT_BY_PATH rolls up the hierarchy for you. When you get to a new node, you see all the prior nodes as well:

 KING KING - JONES KING - JONES - SCOTT KING - JONES - SCOTT - ADAMS 

If you are on Oracle8i Database or earlier, you can use the PostgreSQL solution to this problem. Alternatively, because CONNECT BY is available on older versions of Oracle, you can simply use LEVEL and RPAD/ LPAD for formatting (although to reproduce the output created by SYS_CONNECT_BY_PATH would require a bit more work).

PostgreSQL and MySQL

With the exception of string concatenation in the SELECT clauses, the solutions are the same for both PostgreSQL and MySQL. The first step is to determine the maximum number of nodes for any one branch. You have to do this manually, before you write the query. If you examine the data in the EMP table, you will see that employees ADAM and SMITH are the leaf nodes at the greatest depth (you may wish to look at the Oracle discussion where you'll find a nicely formatted tree of the EMP hierarchy). If you look at employee ADAMS, you see that ADAMS works for SCOTT who in turn works for JONES who in turn works for KING, so the depth is 4. To be able to express a hierarchy with a depth of four, you must self join four instances of table EMP, and you must write a four-part UNION query. The results of the four-way self join (which is the lower part of the last UNION, from top to bottom) is shown below (using PostgreSQL syntax; MySQL users, simply substitute "||" for the CONCAT function call):

  select rtrim(a.ename||' - '||b.ename||' - '||              c.ename||' - '||d.ename,' - ') as max_depth_4   from emp a        join        emp b on (a.empno=b.mgr)        join        emp c on (b.empno=c.mgr)        left join        emp d on (c.empno=d.mgr)  where a.ename = 'KING' MAX_DEPTH_4 ----------------------------- KING - JONES - FORD - SMITH KING - JONES - SCOTT - ADAMS KING - BLAKE - TURNER KING - BLAKE - ALLEN KING - BLAKE - WARD KING - CLARK - MILLER KING - BLAKE - MARTIN KING - BLAKE - JAMES 

The filter on A.ENAME is necessary to ensure that the root row is KING and no other employee. If you look at the result set above and compare it with the final result set, you'll see that there are some three-deep hierarchies not returned: KING - JONES - FORD and KING - JONES - SCOTT. To include those rows in the final result set, you need to write another query similar to the one above, but with one less join (self joining only three instances of table EMP rather than four). The result set of this query is shown below:

  select rtrim(a.ename||' - '||b.ename                     ||' - '||c.ename,' - ') as max_depth_3   from emp a        join        emp b on (a.empno=b.mgr)        left join        emp c on (b.empno=c.mgr)  where a.ename = 'KING' MAX_DEPTH_3 --------------------------- KING - BLAKE - ALLEN KING - BLAKE - WARD KING - BLAKE - MARTIN KING - JONES - SCOTT KING - BLAKE - TURNER KING - BLAKE - JAMES KING - JONES - FORD KING - CLARK - MILLER 

Like the query before it, the filter on A.ENAME is necessary to ensure the root row node is KING. You'll notice some overlapping rows between the query above and the four-way EMP join. To get rid of the redundant rows, simply UNION the two queries:

  select rtrim(a.ename||' - '||b.ename                     ||' - '||c.ename,' - ') as partial_tree   from emp a        join        emp b on (a.empno=b.mgr)        left join        emp c on (b.empno=c.mgr)  where a.ename = 'KING' union select rtrim(a.ename||' - '||b.ename||' - '||              c.ename||' - '||d.ename,' - ')   from emp a        join        emp b on (a.empno=b.mgr)        join        emp c on (b.empno=c.mgr)        left join        emp d on (c.empno=d.mgr)  where a.ename = 'KING' PARTIAL_TREE ------------------------------- KING - BLAKE - ALLEN KING - BLAKE - JAMES KING - BLAKE - MARTIN KING - BLAKE - TURNER KING - BLAKE - WARD KING - CLARK - MILLER KING - JONES - FORD KING - JONES - FORD - SMITH KING - JONES - SCOTT KING - JONES - SCOTT - ADAMS 

At this point the tree is almost complete. The next step is to return rows that represent a two-deep hierarchy with KING as the root node (i.e., employees who work directly for KING). The query to return those rows is shown below:

  select a.ename||' - '||b.ename as max_depth_2   from emp a        join        emp b on (a.empno=b.mgr)  where a.mgr is null MAX_DEPTH_2 --------------- KING - JONES KING - BLAKE KING - CLARK 

The next step is to UNION the above query, to the PARTIAL_TREE union:

  select a.ename||' - '||b.ename as partial_tree   from emp a        join        emp b on (a.empno=b.mgr)  where a.mgr is null union select rtrim(a.ename||' - '||b.ename                     ||' - '||c.ename,' - ')   from emp a        join        emp b on (a.empno=b.mgr)        left join        emp c on (b.empno=c.mgr)  where a.ename = 'KING' union select rtrim(a.ename||' - '||b.ename||' - '||              c.ename||' - '||d.ename,' - ')   from emp a        join        emp b on (a.empno=b.mgr)        join        emp c on (b.empno=c.mgr)        left join        emp d on (c.empno=d.mgr)  where a.ename = 'KING' PARTIAL_TREE ---------------------------------- KING - BLAKE KING - BLAKE - ALLEN KING - BLAKE - JAMES KING - BLAKE - MARTIN KING - BLAKE - TURNER KING - BLAKE - WARD KING - CLARK KING - CLARK - MILLER KING - JONES KING - JONES - FORD KING - JONES - FORD - SMITH KING - JONES - SCOTT KING - JONES - SCOTT - ADAMS 

The final step is to UNION KING to the top of PARTIAL_TREE to return the desired result set.