Recipe13.2.Expressing a Child-Parent-Grandparent Relationship

Recipe 13.2. Expressing a Child-Parent-Grandparent Relationship

Problem

Employee CLARK works for KING and to express that relationship you can use the first recipe in this chapter. What if employee CLARK was in turn a manager for another employee? Consider the following query:

  select ename,empno,mgr   from emp  where ename in ('KING','CLARK','MILLER') ENAME        EMPNO     MGR --------- -------- ------- CLARK         7782    7839 KING          7839 MILLER        7934    7782 

As you can see, employee MILLER works for CLARK who in turn works for KING. You want to express the full hierarchy from MILLER to KING. You want to return the following result set:

 LEAF___BRANCH___ROOT --------------------- MILLER-->CLARK-->KING 

However, the single self-join approach from the previous recipe will not suffice to show the entire relationship from top to bottom. You could write a query that does two self joins, but what you really need is a general approach for traversing such hierarchies.

Solution

This recipe differs from the first recipe because there is now a three-tier relationship, as the title suggests. If your RDBMS does not supply functionality for traversing tree-structured data, then you can solve this problem using the technique from , but you must add an additional self join. DB2, SQL Server, and Oracle offer functions for expressing hierarchies. Thus self joins on those RDBMSs aren't necessary, though they certainly work.

DB2 and SQL Server

Use the recursive WITH clause to find MILLER's manager, CLARK, then CLARK's manager, KING. The SQL Server string concatenation operator + is used in this solution:

 1    with  x (tree,mgr,depth) 2      as  ( 3  select  cast(ename as varchar(100)), 4          mgr, 0 5    from  emp 6   where  ename = 'MILLER' 7   union  all 8  select  cast(x.tree+'-->'+e.ename as varchar(100)), 9          e.mgr, x.depth+1 10   from  emp e, x 11  where x.mgr = e.empno 12 ) 13 select tree leaf___branch___root 14   from x 15  where depth = 2 

The only modification necessary for this solution to work on DB2 is to use DB2's concatenation operator, ||. Otherwise, the solution will work as is, on DB2 as well as SQL Server.

Oracle

Use the function SYS_CONNECT_BY_PATH to return MILLER, MILLER's manager, CLARK, then CLARK's manager, KING. Use the CONNECT BY clause to walk the tree:

 1  select ltrim( 2           sys_connect_by_path(ename,'-->'), 3         '-->') leaf___branch___root 4    from emp 5   where level = 3 6   start with ename = 'MILLER' 7 connect by prior mgr = empno 

PostgreSQL and MySQL

Self join on table EMP twice to return MILLER, MILLER's manager, CLARK, then CLARK's manager, KING. The following solution uses PostgreSQL's concatenation operator, the double vertical-bar (||):

 1  select a.ename||'-->'||b.ename 2                ||'-->'||c.ename as leaf___branch___root 3    from emp a, emp b, emp c 4   where a.ename = 'MILLER' 5     and a.mgr = b.empno 6     and b.mgr = c.empno 

For MySQL users, simply use the CONCAT function; this solution will work for PostgreSQL as well.

Discussion

DB2 and SQL Server

The approach here is to start at the leaf node and walk your way up to the root (as useful practice, try walking in the other direction). The upper part of the UNION ALL simply finds the row for employee MILLER (the leaf node). The lower part of the UNION ALL finds the employee who is MILLER's manager, then finds that person's manager, and this process of finding the "manager's manager" repeats until processing stops at the highest-level manager (the root node). The value for DEPTH starts at 0 and increments automatically by 1 each time a manager is found. DEPTH is a value that DB2 maintains for you when you execute a recursive query.

For an interesting and in-depth introduction to the WITH clause with focus on its use recursively, see Jonathan Gennick's article "Understanding the WITH Clause" at http://gennick.com/with.htm.

Next, the second query of the UNION ALL joins the recursive view X to table EMP, to define the parentchild relationship. The query at this point, using SQL Server's concatenation operator, is as follows:

    with x (tree,mgr,depth)     as ( select cast(ename as varchar(100)),        mgr, 0   from emp  where ename = 'MILLER'  union all select cast(x.tree+'-->'+e.ename as varchar(100)),        e.mgr, x.depth+1   from emp e, x  where x.mgr = e.empno ) select tree leaf___branch___root   from x TREE            DEPTH ---------- ---------- MILLER              0 CLARK               1 KING                2 

At this point, the heart of the problem has been solved; starting from MILLER, return the full hierarchical relationship from bottom to top. What's left then is merely formatting. Since the tree traversal is recursive, simply concatenate the current ENAME from EMP to the one before it, which gives you the following result set:

    with x (tree,mgr,depth)     as ( select  cast(ename as varchar(100)),         mgr, 0   from emp  where ename = 'MILLER'  union all select cast(x.tree+'-->'+e.ename as varchar(100)),        e.mgr, x.depth+1   from emp e, x  where x.mgr = e.empno ) select depth, tree   from x DEPTH TREE ----- ---------------------------     0 MILLER     1 MILLER-->CLARK     2 MILLER-->CLARK-->KING 

The final step is to keep only the last row in the hierarchy. There are several ways to do this, but the solution uses DEPTH to determine when the root is reached (obviously, if CLARK has a manager other than KING, the filter on DEPTH would have to change; for a more generic solution that requires no such filter, see the next recipe).

Oracle

The CONNECT BY clause does all the work in the Oracle solution. Starting with MILLER, you walk all the way to KING without the need for any joins. The expression in the CONNECT BY clause defines the relationship of the data and how the tree will be walked:

   select ename    from emp   start with ename = 'MILLER' connect by prior mgr = empno ENAME -------- MILLER CLARK KING 

The keyword PRIOR lets you access values from the previous record in the hierarchy. Thus, for any given EMPNO you can use PRIOR MGR to access that employee's manager number. When you see a clause such as CONNECT BY PRIOR MGR = EMPNO, think of that clause as expressing a join between, in this case, parent and child.

For more on CONNECT BY and related features, see the following Oracle Technology Network articles: "Querying Hierarchies: Top-of-the-Line Support" at http://www.oracle.com/technology/oramag/webcolumns/2003/techarticles/gennick_connectby.html, and "New CONNECT BY Features in Oracle Database 10g"at http://www.oracle.com/technology/oramag/webcolumns/2003/techarticles/gennick_connectby_10g.html.

At this point you have successfully displayed the full hierarchy starting from MILLER and ending at KING. The problem is for the most part solved. All that remains is the formatting. Use the function SYS_CONNECT_BY_PATH to append each ENAME to the one before it:

   select sys_connect_by_path(ename,'-->') tree    from emp   start with ename = 'MILLER' connect by prior mgr = empno TREE --------------------------- -->MILLER -->MILLER-->CLARK -->MILLER-->CLARK-->KING 

Because you are interested in only the complete hierarchy, you can filter on the pseudo-column LEVEL (a more generic approach is shown in the next recipe):

   select sys_connect_by_path(ename,'-->') tree    from emp   where level = 3   start with ename = 'MILLER' connect by prior mgr = empno TREE --------------------------- -->MILLER-->CLARK-->KING 

The final step is to use the LTRIM function to remove the leading "-->" from the result set.

PostgreSQL and MySQL

Without built-in support for hierarchical queries, you must self join n times to return the whole tree (where n is the number of nodes between the leaf and the root, including the root itself; in this example, relative to MILLER, CLARK is a branch node and KING is the root node, so the distance is two nodes, and n = 2). This solution simply uses the technique from the previous recipe and adds one more self join:

  select a.ename as leaf,        b.ename as branch,        c.ename as root   from emp a, emp b, emp c  where a.ename = 'MILLER'    and a.mgr = b.empno    and b.mgr = c.empno LEAF      BRANCH      ROOT --------- ----------  ----- MILLER    CLARK       KING 

The next and last step is to format the output using the || concatenation operator for PostgreSQL or the CONCAT function for MySQL. The drawback to this kind of query is that if the hierarchy changesfor example, if there is another node between CLARK and KINGthe query would need to have yet another join to return the whole tree. This is why it is such an advantage to have and use built-in functions for hierarchies.