DB2, Oracle, and PostgreSQL

Self join on EMP. Then use the double vertical-bar (||) concatenation operator:

	1 select a.ename || ' works for ' || b.ename as emps_and_mgrs
	2   from emp a, emp b
	3  where a.mgr = b.empno

MySQL

Self join on EMP. Then use the concatenation function CONCAT:

	1 select concat(a.ename, ' works for ',b.ename) as emps_and_mgrs
	2   from emp a, emp b
	3  where a.mgr = b.empno

SQL Server

Self join on EMP. Then use the plus sign (+) as the concatenation operator:

	1 select a.ename + ' works for ' + b.ename as emps_and_mgrs
	2   from emp a, emp b
	3  where a.mgr = b.empno

DB2, PostgreSQL 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

This solution can work on other databases if the concatenation operator is changed. Hence, change to || for DB2 or CONCAT for PostgreSQL.

MySQL:

Similar to above, but also needs recursive keyword:

	1    with recursive 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(concat(x.tree,'-->',emp.ename) as char(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

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

DB2, SQL Server, PostgreSQL and MySQL

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.

Next, the second query of the UNION ALL joins the recursive view X to table EMP, to define the parent–child 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.

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.

DB2, PostgreSQL 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 + and MySQL uses the concat function. 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

MySQL

MySQL also needs the recursive keyword:

	 1   with recursive 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(concat(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.

DB2, MySQL, PostgreSQL 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

DB2, PostgreSQL and SQL Server

Use the recursive WITH clause to find all employees under JONES. Begin with JONES by specifying WHERE ENAME = JONES in the first of the two union queries:

	 1   with x (ename,empno)
	 2     as (
	 3 select ename,empno
	 4   from emp
	 5  where ename = 'JONES'
	 6  union all
	 7 select e.ename, e.empno
	 8   from emp e, x
	 9  where x.empno = e.mgr
	10 )
	11 select ename
	12   from x

Oracle

Use the CONNECT BY clause and specify START WITH ENAME = JONES to find all the employees under JONES:

	1 select ename
	2   from emp
	3  start with ename = 'JONES'
	4 connect by prior empno = mgr

DB2, MySQL, PostgreSQL and SQL Server

The recursive WITH clause makes this a relatively easy problem to solve. The first part of the WITH clause, the upper part of the UNION ALL, returns the row for employee JONES. You need to return ENAME to see the name and EMPNO so you can use it to join on. The lower part of the UNION ALL recursively joins EMP.MGR to X.EMPNO. The join condition will be applied until the result set is exhausted.

Oracle

The START WTH clause tells the query to make JONES the root node. The condition in the CONNECT BY clause drives the tree walk and will run until the condition is no longer true.

DB2, PostgreSQL, MySQL, and SQL Server

Use three scalar subqueries to determine the correct “Boolean” value (either a 1 or a 0) to return for each node type:

	 1 select e.ename,
	 2        (select sign(count(*)) from emp d
	 3          where 0 =
	 4            (select count(*) from emp f
	 5              where f.mgr = e.empno)) as is_leaf,
	 6        (select sign(count(*)) from emp d
	 7          where d.mgr = e.empno
	 8           and e.mgr is not null) as is_branch,
	 9        (select sign(count(*)) from emp d
	10          where d.empno = e.empno
	11            and d.mgr is null) as is_root
	12   from emp e
	13 order by 4 desc,3 desc

Oracle

The scalar subquery solution will work for Oracle as well, and should be used if you are on a version of Oracle prior to Oracle Database 10g. The following solution highlights built-in functions provided by Oracle (that were introduced in Oracle Database 10g) to identify root and leaf rows. The functions are CONNECT_BY_ROOT and CONNECT_BY_ISLEAF, respectively:

	 1  select ename,
	 2         connect_by_isleaf is_leaf,
	 3         (select count(*) from emp e
	 4           where e.mgr = emp.empno
	 5             and emp.mgr is not null
	 6             and rownum = 1) is_branch,
	 7         decode(ename,connect_by_root(ename),1,0) is_root
	 8    from emp
	 9   start with mgr is null
	10 connect by prior empno = mgr
	11 order by 4 desc, 3 desc

DB2, PostgreSQL, MySQL, and SQL Server

This solution simply applies the rules defined in the “Problem” section to determine leaves, branches, and roots. The first step is to find determine whether an employee is a leaf node. If the employee is not a manager (no one works under her), then she is a leaf node. The first scalar subquery, IS_LEAF, is shown below:

	select e.ename,
	       (select sign(count(*)) from emp d
	         where 0 =
	           (select count(*) from emp f
	             where f.mgr = e.empno)) as is_leaf
	  from emp e
	order by 2 desc

	ENAME        IS_LEAF
	----------- --------
	SMITH              1
	ALLEN              1
	WARD               1
	ADAMS              1
	TURNER             1
	MARTIN             1
	JAMES              1
	MILLER             1
	JONES              0
	BLAKE              0
	CLARK              0
	FORD               0
	SCOTT              0
	KING               0

Because the output for IS_LEAF should be a 0 or 1, it is necessary to take the SIGN of the COUNT(*) operation. Otherwise you would get 14 instead of 1 for leaf rows. As an alternative, you can use a table with only one row to count against, because you only want to return 0 or 1. For example:

	select e.ename,
	       (select count(*) from t1 d
	         where not exists
	           (select null from emp f
	             where f.mgr = e.empno)) as is_leaf
	  from emp e
	order by 2 desc

	ENAME         IS_LEAF
	---------- ----------
	SMITH               1
	ALLEN               1
	WARD                1
	ADAMS               1
	TURNER              1
	MARTIN              1
	JAMES               1
	MILLER              1
	JONES               0
	BLAKE               0
	CLARK               0
	FORD                0
	SCOTT               0
	KING                0

The next step is to find branch nodes. If an employee is a manager (someone works for them), and they also happen to work for someone else, then the employee is a branch node. The results of the scalar subquery IS_BRANCH are shown below:

	select e.ename,
	       (select sign(count(*)) from emp d
	         where d.mgr = e.empno
	          and e.mgr is not null) as is_branch
	  from emp e
	order by 2 desc

	ENAME       IS_BRANCH
	----------- ---------
	JONES               1
	BLAKE               1
	SCOTT               1
	CLARK               1
	FORD                1
	SMITH               0
	TURNER              0
	MILLER              0
	JAMES               0
	ADAMS               0
	KING                0
	ALLEN               0
	MARTIN              0
	WARD                0

Again, it is necessary to take the SIGN of the COUNT(*) operation. Otherwise you will get (potentially) values greater than 1 when a node is a branch. Like scalar subquery IS_LEAF, you can use a table with one row to avoid using SIGN. The following solution uses a one-row table named dual:

	select e.ename,
	      (select count(*) from t1 t
	        where exists (
	         select null from emp f
	          where f.mgr = e.empno
	            and e.mgr is not null)) as is_branch
	  from emp e
	order by 2 desc

	ENAME            IS_BRANCH
	--------------- ----------
	JONES                    1
	BLAKE                    1
	SCOTT                    1
	CLARK                    1
	FORD                     1
	SMITH                    0
	TURNER                   0
	MILLER                   0
	JAMES                    0
	ADAMS                    0
	KING                     0
	ALLEN                    0
	MARTIN                   0
	WARD                     0

The last step is to find the root nodes. A root node is defined as an employee who is a manager but who does not work for anyone else. In table EMP, only KING is a root node. Scalar subquery IS_ROOT is shown below:

	select e.ename,
	       (select sign(count(*)) from emp d
	         where d.empno = e.empno
	           and d.mgr is null) as is_root
	  from emp e
	order by 2 desc

	ENAME         IS_ROOT
	----------  ---------
	KING                1
	SMITH               0
	ALLEN               0
	WARD                0
	JONES               0
	TURNER              0
	JAMES               0
	MILLER              0
	FORD                0
	ADAMS               0
	MARTIN              0
	BLAKE               0
	CLARK               0
	SCOTT               0

Because EMP is a small 14-row table, it is easy to see that employee KING is the only root node, so in this case taking the SIGN of the COUNT(*) operation is not strictly necessary. If there can be multiple root nodes, then you can use SIGN, or you can use a one-row table in the scalar subquery as is shown earlier for IS_BRANCH and IS_LEAF.

Oracle

For those of you on versions of Oracle prior to Oracle Database 10g, you can follow the discussion for the other RDBMSs, as that solution will work (without modifications) in Oracle. If you are on Oracle Database 10g or later, you may want to take advantage of two functions to make identifying root and leaf nodes a simple task: they are CONNECT_BY_ROOT and CONNECT_BY_ISLEAF, respectively. As of the time of this writing, it is necessary to use CONNECT BY in your SQL statement in order for you to be able to use CONNECT_BY_ROOT and CONNECT_BY_ISLEAF. The first step is to find the leaf nodes by using CONNECT_BY_ISLEAF as follows:

	select ename,
	        connect_by_isleaf is_leaf
	  from emp
	 start with mgr is null
	connect by prior empno = mgr
	order by 2 desc

	ENAME          IS_LEAF
	----------  ----------
	ADAMS                1
	SMITH                1
	ALLEN                1
	TURNER               1
	MARTIN               1
	WARD                 1
	JAMES                1
	MILLER               1
	KING                 0
	JONES                0
	BLAKE                0
	CLARK                0
	FORD                 0
	SCOTT                0

The next step is to use a scalar subquery to find the branch nodes. Branch nodes are employees who are managers but who also work for someone else:

	select ename,
	        (select count(*) from emp e
	          where e.mgr = emp.empno
	            and emp.mgr is not null
	            and rownum = 1) is_branch
	  from emp
	 start with mgr is null
	connect by prior empno = mgr
	order by 2 desc

	ENAME       IS_BRANCH
	---------- ----------
	JONES               1
	SCOTT               1
	BLAKE               1
	FORD                1
	CLARK               1
	KING                0
	MARTIN              0
	MILLER              0
	JAMES               0
	TURNER              0
	WARD                0
	ADAMS               0
	ALLEN               0
	SMITH               0

The filter on ROWNUM is necessary to ensure that you return a count of 1 or 0, and nothing else.

The last step is to identify the root nodes by using the function CONNECT_BY_ROOT. The solution finds the ENAME for the root node and compares it with all the rows returned by the query. If there is a match, that row is the root node:

	select ename,
	        decode(ename,connect_by_root(ename),1,0) is_root
	  from emp
	 start with mgr is null
	connect by prior empno = mgr
	order by 2 desc

	ENAME          IS_ROOT
	----------  ----------
	KING                 1
	JONES                0
	SCOTT                0
	ADAMS                0
	FORD                 0
	SMITH                0
	BLAKE                0
	ALLEN                0
	WARD                 0
	MARTIN               0
	TURNER               0
	JAMES                0
	CLARK                0
	MILLER               0

The SYS_CONNECT_BY_PATH function rolls up a hierarchy starting from the root value as is shown below:

	select ename,
	       ltrim(sys_connect_by_path(ename,','),',') path
	  from emp
	start with mgr is null
	connect by prior empno=mgr

	ENAME      PATH
	---------- ----------------------------
	KING       KING
	JONES      KING,JONES
	SCOTT      KING,JONES,SCOTT
	ADAMS      KING,JONES,SCOTT,ADAMS
	FORD       KING,JONES,FORD
	SMITH      KING,JONES,FORD,SMITH
	BLAKE      KING,BLAKE
	ALLEN      KING,BLAKE,ALLEN
	WARD       KING,BLAKE,WARD
	MARTIN     KING,BLAKE,MARTIN
	TURNER     KING,BLAKE,TURNER
	JAMES      KING,BLAKE,JAMES
	CLARK      KING,CLARK
	MILLER     KING,CLARK,MILLER

To get the root row, simply substring out the first ENAME in PATH:

	select ename,
	       substr(root,1,instr(root,',')-1) root
	  from (
	select ename,
	       ltrim(sys_connect_by_path(ename,','),',') root
	  from emp
	start with mgr is null
	connect by prior empno=mgr
	       )

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

The last step is to flag the result from the ROOT column if it is NULL; that is your root row.