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!

share|improve this question

edited Dec 11 '12 at 9:28

asked Dec 6 '12 at 15:36          Grijesh Chauhan        2862413

migrated from stackoverflow.com Dec 8 '12 at 9:42

This question came from our site for professional and enthusiast programmers.

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 latin1DETERMINISTICBEGIN  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>

share|improve this answer

edited Dec 11 '12 at 17:11

answered Dec 10 '12 at 20:09          RolandoMySQLDBA        102k13131263

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.

share|improve this answer

answered Dec 6 '12 at 15:46          Shiplu        1213