Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

For the problem I have a single table which store a Member's ID and His Referee's ID. This is something like a Multi-Level-Marketing plan where you join a company for some tasks and then someone join from your reference and appear under your downline and so on and so forth. The scheme I am using is not necessarily a binary tree, there can be many users under a single user.

I want to retrieve the entire tree under a specific user, I am using below query to retrieve the records but this is not the solution I want.

SELECT t1.user AS lvl1, t2.user AS lvl2, t3.user AS lvl3,
       t4.user AS lvl4, t5.user AS lvl5
FROM reference t1  
LEFT JOIN reference t2 ON t2.referee = t1.user  
LEFT JOIN reference t3 ON t3.referee = t2.user  
LEFT JOIN reference t4 ON t4.referee = t3.user  
LEFT JOIN reference t5 ON t5.referee = t4.user  
WHERE t1.referee = 1

This query will get me the tree structure under user 1 but only 5 level deep.

Now I want to retrieve the entire tree upto last level but cant figure out a way for same. Tree depth can be anything depending on the users referrals so I cannot even guess the depth (That wont make sense anyway).

All I want right now is to perform the JOIN and keep watching the selected column (in our case user) from last JOIN to check if all the values in it are NULL. If the column from last JOIN is NULL then it means the tree is completed and query should return the result.

Can anyone suggest a workaround?
I can make changes in the table structure if necessary but that should not effect the behavior of other operations.

share|improve this question
add comment

2 Answers 2

Although MySQL has no CTE functionality, there are two major ways to create CTE expressions:

TECHNIQUE #1 : Write Stored Procedures to Traverse Recursively

Rather than Reinventing the Wheel, please see my past posts on how to make stored procedures

TECHNIQUE #2 : Iterate Based on the Tree's Maximum Depth

First, here is some sample data

DROP DATABASE IF EXISTS dufran;
CREATE DATABASE dufran;
USE dufran;
CREATE TABLE reference 
(
    user INT NOT NULL AUTO_INCREMENT,
    referee INT NOT NULL DEFAULT 0,
    name VARCHAR(20) NOT NULL,
    PRIMARY KEY (user)
);
INSERT INTO reference (name,referee) VALUES ('Rolando',0);
INSERT INTO reference (name,referee) VALUES ('Pamela',1);
INSERT INTO reference (name,referee) VALUES ('Carlik',2);
INSERT INTO reference (name,referee) VALUES ('Javonne',2);
INSERT INTO reference (name,referee) VALUES ('Dominique',2);
INSERT INTO reference (name,referee) VALUES ('Diamond',2);
INSERT INTO reference (name,referee) VALUES ('Azalia',3);

When loaded, this is the data

mysql> SELECT * FROM reference;
+------+---------+-----------+
| user | referee | name      |
+------+---------+-----------+
|    1 |       0 | Rolando   |
|    2 |       1 | Pamela    |
|    3 |       2 | Carlik    |
|    4 |       2 | Javonne   |
|    5 |       2 | Dominique |
|    6 |       2 | Diamond   |
|    7 |       3 | Azalia    |
+------+---------+-----------+
7 rows in set (0.00 sec)

mysql>

Here is how you compute the maximum depth

SET @depth = 0;
SELECT MAX(@depth:=@depth+1) max_depth FROM
(SELECT DISTINCT referee FROM reference) A;

Here is the maximum depth for the sample data

mysql> SET @depth = 0;
Query OK, 0 rows affected (0.00 sec)

mysql> SELECT MAX(@depth:=@depth+1) max_depth FROM
    -> (SELECT DISTINCT referee FROM reference) A;
+-----------+
| max_depth |
+-----------+
|         4 |
+-----------+
1 row in set (0.00 sec)

mysql>

Using this principle, iterate for the SELECT columns and the LEFT JOIN clauses

SET @depth = 0;
SELECT GROUP_CONCAT(CONCAT('t',dep,'.user AS lvl',dep))
INTO @sqllist FROM
(SELECT @depth:=@depth+1 dep FROM
(SELECT DISTINCT referee FROM reference) AA) A;
SET @depth1 = 0;
SET @depth2 = 1;
SELECT GROUP_CONCAT(sqljoin SEPARATOR ' ') INTO @sqljoins
FROM (SELECT CONCAT('LEFT JOIN reference t',@depth2:=@depth2+1,
' ON t',@depth2,'.referee = t',@depth1:=@depth1+1,'.user') sqljoin
FROM (SELECT DISTINCT referee FROM reference) AA) A;
SELECT @sqljoins;
SET @sqlstmt = CONCAT('SELECT ',@sqllist,
' FROM reference t1 ',@sqljoins);
SELECT @sqllist\G
SELECT @sqljoins\G
SELECT @sqlstmt\G

Here is the SQL generated

mysql> SET @depth = 0;
Query OK, 0 rows affected (0.00 sec)

mysql> SELECT GROUP_CONCAT(CONCAT('t',dep,'.user AS lvl',dep))
    -> INTO @sqllist FROM
    -> (SELECT @depth:=@depth+1 dep FROM
    -> (SELECT DISTINCT referee FROM reference) AA) A;
Query OK, 1 row affected (0.00 sec)

mysql> SET @depth1 = 0;
Query OK, 0 rows affected (0.00 sec)

mysql> SET @depth2 = 1;
Query OK, 0 rows affected (0.00 sec)

mysql> SELECT GROUP_CONCAT(sqljoin SEPARATOR ' ') INTO @sqljoins
    -> FROM (SELECT CONCAT('LEFT JOIN reference t',@depth2:=@depth2+1,
    -> ' ON t',@depth2,'.referee = t',@depth1:=@depth1+1,'.user') sqljoin
    -> FROM (SELECT DISTINCT referee FROM reference) AA) A;
Query OK, 1 row affected (0.00 sec)

mysql>     SELECT @sqllist\G
*************************** 1. row ***************************
@sqllist: t1.user AS lvl1,t2.user AS lvl2,t3.user AS lvl3,t4.user AS lvl4
1 row in set (0.00 sec)

mysql>     SELECT @sqljoins\G
*************************** 1. row ***************************
@sqljoins: LEFT JOIN reference t2 ON t2.referee = t1.user LEFT JOIN reference t3 ON t3.referee = t2.user LEFT JOIN reference t4 ON t4.referee = t3.user LEFT JOIN reference t5 ON t5.referee = t4.user
1 row in set (0.00 sec)

mysql>     SELECT @sqlstmt\G
*************************** 1. row ***************************
@sqlstmt: SELECT t1.user AS lvl1,t2.user AS lvl2,t3.user AS lvl3,t4.user AS lvl4 FROM reference t1 LEFT JOIN reference t2 ON t2.referee = t1.user LEFT JOIN reference t3 ON t3.referee = t2.user LEFT JOIN reference t4 ON t4.referee = t3.user LEFT JOIN reference t5 ON t5.referee = t4.user
1 row in set (0.00 sec)

mysql>

Here is the big question, does the SQL work ??? Take the SQL and run it dynamically:

PREPARE s FROM @sqlstmt;
EXECUTE s;
DEALLOCATE PREPARE s;

Here is the result:

mysql> PREPARE s FROM @sqlstmt;
Query OK, 0 rows affected (0.00 sec)
Statement prepared

mysql> EXECUTE s;
+------+------+------+------+
| lvl1 | lvl2 | lvl3 | lvl4 |
+------+------+------+------+
|    1 |    2 |    3 |    7 |
|    1 |    2 |    4 | NULL |
|    1 |    2 |    5 | NULL |
|    1 |    2 |    6 | NULL |
|    2 |    3 |    7 | NULL |
|    2 |    4 | NULL | NULL |
|    2 |    5 | NULL | NULL |
|    2 |    6 | NULL | NULL |
|    3 |    7 | NULL | NULL |
|    4 | NULL | NULL | NULL |
|    5 | NULL | NULL | NULL |
|    6 | NULL | NULL | NULL |
|    7 | NULL | NULL | NULL |
+------+------+------+------+
13 rows in set (0.03 sec)

mysql> DEALLOCATE PREPARE s;
Query OK, 0 rows affected (0.00 sec)

mysql>

I scripted this to give you a starting point and some homework. Here is what I mean: You probably don't want to see NULL columns. You could do one of two things:

  1. Convert each NULL to IFNULL(lvl1,''), GROUP_CONCAT all columns.
  2. Compute the depth of a particular id and gather columns for it only.

Give it a Try !!!

share|improve this answer
    
Thank you for help, This is really too much now but look at this, I am stuck at calculating the depth for a particular user. There is only one restrictions on the hierarchy, User under your down-line will have ID greater than yours. So, That makes it really hard to pick an ID,say 8,and then go from ID 8 to the leaf node that is at maximum distance and then calculate the depth. Since there will be many leaf nodes it is even harder to calculate the depth by comparing the node path from root node to all of them.So all in all,I am still at the same point where I was right before testing this out. –  Gufran Oct 30 '12 at 15:04
    
Alright, another couple hours I spent on this concluded that I have to find a way to calculate the depth of the tree in order to retrieve the full tree under a given node. I came up with an approach to loop through the JOINs and select the last level result from the latest JOIN result, if the result is NULL then we have the depth of tree. I dont want to loop the query because increasing the depth level will result in so many loop iterations. Can you please suggest a way to eliminate the loop situation ? I can post the algorithm for that if you want me to.I have word limit on comments here. –  Gufran Oct 30 '12 at 20:30
    
@Gufran Do you have an example of the LOOP you used in the end? –  Webdevilopers Feb 13 '13 at 8:03
    
Technique #3: upgrade to a modern DBMS that supports recursive queries. –  a_horse_with_no_name Feb 13 '13 at 12:19
    
@Webdevilopers, do you want the solution or the example ? If solution then I settled with adjacency list model, read more about that over wikipedia en.wikipedia.org/wiki/Adjacency_list_model. –  Gufran Feb 13 '13 at 14:26
add comment

A CTE (Common Table Expression) will provide a solution to your problem.

CREATE TABLE Reference 
(
    UserID INT NOT NULL CONSTRAINT PK_Posts PRIMARY KEY IDENTITY(1,1)
    , ReferrerID INT NULL
    , PersonName NVARCHAR(255)
);

INSERT INTO Reference VALUES (NULL, 'Joe');
INSERT INTO Reference VALUES (NULL, 'Sally');
INSERT INTO Reference VALUES (1, 'Mike');
INSERT INTO Reference VALUES (1, 'Tracy');
INSERT INTO Reference VALUES (3, 'Ken');
INSERT INTO Reference VALUES (2, 'Bob');
INSERT INTO Reference VALUES (2, 'Brigitte');

GO

;WITH Referrers(ReferrerID, UserID, [Level], PersonName, Hierarchy, UserIDs)
AS 
(
    SELECT 
        ReferrerID
        , UserID
        , 1
        , PersonName
        , CAST(PersonName as nvarchar(255))
        , CAST('|' + CAST(UserID AS nvarchar(255)) + '|' AS nvarchar(255))
    FROM Reference 
    WHERE ReferrerID IS NULL 
    UNION ALL
    SELECT 
        R2.ReferrerID
        , R2.UserID
        , [Level] + 1
        , R2.PersonName
        , CAST('under ' + R.PersonName as nvarchar(255))
        , CAST('|' + CAST(R2.UserID as nvarchar(255)) + UserIDs AS nvarchar(255))
    FROM Reference R2
        JOIN Referrers R ON R2.ReferrerID = R.UserID 
)
SELECT UserID, Level, PersonName, Hierarchy, UserIDs 
FROM Referrers 
WHERE UserIDs LIKE '%|3|%'
ORDER BY ReferrerID, UserID;

The results for 'Ken' are:

UserID  Level   PersonName  Hierarchy   UserIDs
3       2       Mike        under Joe   |3|1|
5       3       Ken         under Mike  |5|3|1|

Ken is selected in this query by the WHERE UserIDs LIKE '%|3|%' - the pipe symbols allow selecting any specific UserID as either the Person, or their referrer.

share|improve this answer
    
Thanks for your efforts, This looks promising except I cannot convert it into MySQL Query without compromising on performance, Or am I missing something ? I need a query for MySQL. –  Gufran Oct 29 '12 at 13:51
    
oooops - When I first looked at your question, I was using my phone and didn't see the tag. Sorry, but I'm not sure how to convert the CTE into something MySQL compatible... Perhaps @RolandMySQLDBA will have an answer later today. –  Max Vernon Oct 29 '12 at 14:34
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.