MySQL: Tree-Hierarchical query

Question

SUB-TREE WITHIN A TREE in MySQL

In my MYSQL Database COMPANY, I have a Table: Employee with recursive association, an employee can be boss of other employee. A self relationship of kind (SuperVisor (1)- SuperVisee (∞) ).

Query to Create Table:

CREATE TABLE IF NOT EXISTS `Employee` (
 `SSN` varchar(64) NOT NULL,
 `Name` varchar(64) DEFAULT NULL,
 `Designation` varchar(128) NOT NULL,
 `MSSN` varchar(64) NOT NULL, 
 PRIMARY KEY (`SSN`),
 CONSTRAINT `FK_Manager_Employee` 
 FOREIGN KEY (`MSSN`) REFERENCES Employee(SSN)
) ENGINE=InnoDB DEFAULT CHARSET=latin1;

I have inserted a set of tuples (Query):

INSERT INTO Employee VALUES 
 ("1", "A", "OWNER", "1"), 
 ("2", "B", "BOSS", "1"), # Employees under OWNER 
 ("3", "F", "BOSS", "1"),
 ("4", "C", "BOSS", "2"), # Employees under B
 ("5", "H", "BOSS", "2"), 
 ("6", "L", "WORKER", "2"), 
 ("7", "I", "BOSS", "2"), 
 # Remaining Leaf nodes 
 ("8", "K", "WORKER", "3"), # Employee under F 
 ("9", "J", "WORKER", "7"), # Employee under I 
 ("10","G", "WORKER", "5"), # Employee under H
 ("11","D", "WORKER", "4"), # Employee under C
 ("12","E", "WORKER", "4") 

The inserted rows has following Tree-Hierarchical-Relationship:

 A <---ROOT-OWNER
 /|\ 
 / A \ 
 B F 
 //| \ \ 
 // | \ K 
 / | | \ 
 I L H C 
/ | / \ 
J G D E

I written a query to find relationship:

SELECT SUPERVISOR.name AS SuperVisor, 
 GROUP_CONCAT(SUPERVISEE.name ORDER BY SUPERVISEE.name ) AS SuperVisee, 
 COUNT(*) 
FROM Employee AS SUPERVISOR 
 INNER JOIN Employee SUPERVISEE ON SUPERVISOR.SSN = SUPERVISEE.MSSN 
GROUP BY SuperVisor;

And output is:

+------------+------------+----------+
| SuperVisor | SuperVisee | COUNT(*) |
+------------+------------+----------+
| A | A,B,F | 3 |
| B | C,H,I,L | 4 |
| C | D,E | 2 |
| F | K | 1 |
| H | G | 1 |
| I | J | 1 |
+------------+------------+----------+
6 rows in set (0.00 sec)

[QUESTION]
Instead of complete Hierarchical Tree, I need a SUB-TREE from a point (selective) e.g.:
If input argument is B then output should be as below...

+------------+------------+----------+
| SuperVisor | SuperVisee | COUNT(*) |
+------------+------------+----------+
| B | C,H,I,L | 4 |
| C | D,E | 2 |
| H | G | 1 |
| I | J | 1 |
+------------+------------+----------+ 

Please help me on this. If not query, a stored-procedure can be helpful.
I tried, but all efforts were useless!

• mellamokb: Sample test fiddle
• mellamokb: I simply provided a test framework for the community to use in exploring this question more easily.
• Grijesh Chauhan: @bluefeet Yes, once I will get answer I will remove one of this two.
• jcolebrand: @GrijeshChauhan let me ask you this: Which is better to make your own visible waves? To throw pebbles into the ocean, or to throw rocks into a small pond? Going straight to the experts is almost certainly going to give you the best answer, and this sort of question is so important (advanced database topics) that we have given it its own site on the network. But I won't stop you from asking it where you like, that's your prerogative. My prerogative is to vote to move it to another site if I think that's where it belongs. :D We both use the network as we see fit in this case :D
• Grijesh Chauhan: @jcolebrand: Actually it was my fault only. I use to post question on multiple sides to get a better, quick and many response. It my experience I always got better answer from expert sides. And I think it was better decision to move question to Database Administrators. In all the cases, I am very thankful to stackoverflow and peoples who are active here. I really got solution for many problem that was very tough to find myself or any other web.

Answer 1

I already addressed something of this nature using Stored Procedures : Find highest level of a hierarchical field: with vs without CTEs (Oct 24, 2011)

If you look in my post, you could use the GetAncestry and GetFamilyTree functions as a model for traversing the tree from any given point.

UPDATE 2012年12月11日 12:11 EDT

I looked back at my code from my post. I wrote up the Stored Function for you:

DELIMITER $$
DROP FUNCTION IF EXISTS `cte_test`.`GetFamilyTree` $$
CREATE FUNCTION `cte_test`.`GetFamilyTree`(GivenName varchar(64))
RETURNS varchar(1024) CHARSET latin1
DETERMINISTIC
BEGIN
 DECLARE rv,q,queue,queue_children,queue_names VARCHAR(1024);
 DECLARE queue_length,pos INT;
 DECLARE GivenSSN,front_ssn VARCHAR(64);
 SET rv = '';
 SELECT SSN INTO GivenSSN
 FROM Employee
 WHERE name = GivenName
 AND Designation <> 'OWNER';
 IF ISNULL(GivenSSN) THEN
 RETURN ev;
 END IF;
 SET queue = GivenSSN;
 SET queue_length = 1;
 WHILE queue_length > 0 DO
 IF queue_length = 1 THEN
 SET front_ssn = queue;
 SET queue = '';
 ELSE
 SET pos = LOCATE(',',queue);
 SET front_ssn = LEFT(queue,pos - 1);
 SET q = SUBSTR(queue,pos + 1);
 SET queue = q;
 END IF;
 SET queue_length = queue_length - 1;
 SELECT IFNULL(qc,'') INTO queue_children
 FROM
 (
 SELECT GROUP_CONCAT(SSN) qc FROM Employee
 WHERE MSSN = front_ssn AND Designation <> 'OWNER'
 ) A;
 SELECT IFNULL(qc,'') INTO queue_names
 FROM
 (
 SELECT GROUP_CONCAT(name) qc FROM Employee
 WHERE MSSN = front_ssn AND Designation <> 'OWNER'
 ) A;
 IF LENGTH(queue_children) = 0 THEN
 IF LENGTH(queue) = 0 THEN
 SET queue_length = 0;
 END IF;
 ELSE
 IF LENGTH(rv) = 0 THEN
 SET rv = queue_names;
 ELSE
 SET rv = CONCAT(rv,',',queue_names);
 END IF;
 IF LENGTH(queue) = 0 THEN
 SET queue = queue_children;
 ELSE
 SET queue = CONCAT(queue,',',queue_children);
 END IF;
 SET queue_length = LENGTH(queue) - LENGTH(REPLACE(queue,',','')) + 1;
 END IF;
 END WHILE;
 RETURN rv;
END $$

It actually works. Here is a sample:

mysql> SELECT name,GetFamilyTree(name) FamilyTree
 -> FROM Employee WHERE Designation <> 'OWNER';
+------+-----------------------+
| name | FamilyTree |
+------+-----------------------+
| A | B,F,C,H,L,I,K,D,E,G,J |
| G | |
| D | |
| E | |
| B | C,H,L,I,D,E,G,J |
| F | K |
| C | D,E |
| H | G |
| L | |
| I | J |
| K | |
| J | |
+------+-----------------------+
12 rows in set (0.36 sec)
mysql>

There is only one catch. I added one extra row for the owner

• The owner has SSN 0
• The owner is his own boss with MSSN 0

Here is the data

mysql> select * from Employee;
+-----+------+-------------+------+
| SSN | Name | Designation | MSSN |
+-----+------+-------------+------+
| 0 | A | OWNER | 0 |
| 1 | A | BOSS | 0 |
| 10 | G | WORKER | 5 |
| 11 | D | WORKER | 4 |
| 12 | E | WORKER | 4 |
| 2 | B | BOSS | 1 |
| 3 | F | BOSS | 1 |
| 4 | C | BOSS | 2 |
| 5 | H | BOSS | 2 |
| 6 | L | WORKER | 2 |
| 7 | I | BOSS | 2 |
| 8 | K | WORKER | 3 |
| 9 | J | WORKER | 7 |
+-----+------+-------------+------+
13 rows in set (0.00 sec)
mysql>

• Grijesh Chauhan: understood the Idea!
• Smith: How can i adapt to get all Descendants of A like this A A/B A/B/C A/B/C/D A/B/C/E A/B/H A/B/H/G A/B/I A/B/I/J A/B/L A/F A/F/K
• عثمان غني: does it handle multinodes also? as it is hanging in my database where multiple nodes of a parent found

Answer 2

What you are using is called Adjacency List Model. It has a lot of limitations. You'll be problem when you want to delete/insert a node at a specific place. Its better you use Nested Set Model.

There is a detailed explanation. Unfortunately the article on mysql.com is does not exist any more.

• user1822: "it has a lot of limitations" - but only when using MySQL. Nearly all DBMS support recursive queries (MySQL is one of the very few that doesn't) and that makes the model really easy to deal with.
• Shiplu Mokaddim: @a_horse_with_no_name Never used anything other than MySQL. So I never knew it. Thanks for the information.

Answer 3

After 12.5 years, doing something similar.

Now, MySQL 8.6+ supports CTE, I wrote a query to answer this question:

WITH RECURSIVE
 Hierarchy AS (
 SELECT SSN, Name, Designation, MSSN
 FROM Employee
 WHERE Name = 'B' -- change B
 UNION ALL
 SELECT E.SSN, E.Name, E.Designation, E.MSSN
 FROM Employee AS E
 INNER JOIN Hierarchy AS H
 ON E.MSSN = H.SSN
 WHERE E.MSSN <> E.SSN 
 )
SELECT Supervisor.name AS SuperVisor,
 GROUP_CONCAT(Supervisee.name ORDER BY Supervisee.name) AS SuperVisee,
 COUNT(*)
FROM Hierarchy AS Supervisor
INNER JOIN Hierarchy AS Supervisee
 ON Supervisor.SSN = Supervisee.MSSN
GROUP BY SuperVisor

Which is actually working in MySQL:

mysql> WITH RECURSIVE
 -> Hierarchy AS (
 -> SELECT SSN, Name, Designation, MSSN
 -> FROM Employee
 -> WHERE Name = 'B'
 -> 
 -> UNION ALL
 -> 
 -> SELECT E.SSN, E.Name, E.Designation, E.MSSN
 -> FROM Employee AS E
 -> INNER JOIN Hierarchy AS H
 -> ON E.MSSN = H.SSN
 -> WHERE E.MSSN <> E.SSN 
 -> )
 -> SELECT Supervisor.name AS SuperVisor,
 -> GROUP_CONCAT(Supervisee.name ORDER BY Supervisee.name) AS SuperVisee,
 -> COUNT(*)
 -> FROM Hierarchy AS Supervisor
 -> INNER JOIN Hierarchy AS Supervisee
 -> ON Supervisor.SSN = Supervisee.MSSN
 -> GROUP BY SuperVisor;
+------------+------------+----------+
| SuperVisor | SuperVisee | COUNT(*) |
+------------+------------+----------+
| B | C,H,I,L | 4 |
| C | D,E | 2 |
| H | G | 1 |
| I | J | 1 |
+------------+------------+----------+
4 rows in set (0.003 sec)

• Grijesh Chauhan: I realized it buggy answer, throw an exception for Name = 'A' , will update
• Grijesh Chauhan: added WHERE E.MSSN <> E.SSN to previous answer