Page 1 of 1

referral system using modified preordered tree traversal

Posted: Tue Apr 08, 2008 9:36 pm
by s.dot
Currently, this is how I'm displaying the number of people in a given persons downline (their referrals, their referrals referrals, etc..)

Code: Select all

function display($root, $level_limit)
{
    //count
    $downcount = 0;
// retrieve the left and right value of the $root node
    $result = mysql_query('SELECT `left_boundary`, `right_boundary` FROM `downline` WHERE `username` = "'.$root.'";') or die(mysql_error());
    $row = mysql_fetch_array($result);
 
    // start with an empty $right stack
    $right = array();
 
    // now, retrieve all descendants of the $root node
    $result = mysql_query('SELECT `username`, `left_boundary`, `right_boundary` FROM `downline` WHERE `left_boundary` BETWEEN '.$row['left_boundary'].' AND '.$row['right_boundary'].' AND `exists` = 1 GROUP BY `username` ORDER BY `left_boundary` ASC;') or die(mysql_error());
    
    // display each row
    while($row = mysql_fetch_assoc($result))
    {
        // only check stack if there is one
        if(count($right)>0)
        {
            // check if we should remove a node from the stack
            while($right[count($right)-1] < $row['right_boundary'])
            {
                array_pop($right);
            }
        }
 
        // display indented node title
        if($row['username'] != $_SESSION['user_name'])
        {
            $level = 1*count($right);
            
            if($level <= $level_limit)
            {
                $downcount++;
            }
        }
 
        // add this node to the stack
        $right[] = $row['right_boundary'];
    }
}
I'm wondering if there's a way I can query for all the members within a specific level limit (say 5 levels deep) without using the $downcount variable inside of a condition. If I can, this will allow me to paginate the results.

Err.. hope I can make myself clear enough. I want to be able to get all members of bob's downline 5 levels deep within a query. Hopefully someone has good experience with referral systems and downlines. :)

Re: referral system using modified preordered tree traversal

Posted: Wed Apr 09, 2008 5:56 am
by EverLearning
Code below should work. Let me know how it goes.

Code: Select all

 
$sql = '
    SELECT d.username, d.left_boundary, d.right_boundary, COUNT(*) as level
        FROM downline d
            INNER JOIN downline d2 ON d.left_boundary BETWEEN d2.left_boundary AND d2.right_boundary
        WHERE d.left_boundary BETWEEN '.$row['left_boundary'].' AND '.$row['right_boundary'].' 
            AND d2.left_boundary > '.$row['left_boundary'].'
            AND exists = 1 
        GROUP BY username 
        HAVING level <= 5
        ORDER BY level asc';
 

Re: referral system using modified preordered tree traversal

Posted: Wed Apr 09, 2008 6:02 am
by EverLearning
If you want to learn more about "modified preordered tree traversal" read

Joe Celko's Trees and Hierarchies in SQL for Smarties

EDIT | And there are some nice examples in Pro MySQL in Chapter 8 - "SQL Scenarios"

Re: referral system using modified preordered tree traversal

Posted: Wed Apr 09, 2008 3:20 pm
by s.dot
Thank you for your generous code sample. I will give it a try and update this topic tonight. Just knowing that it may be possible using a query is very relieving. :)

Thanks for the links -- I may need those. Hierarchical data is not my friend :P:

Re: referral system using modified preordered tree traversal

Posted: Wed Apr 09, 2008 4:31 pm
by EverLearning
With nested sets you can do pretty much anything that comes to mind, but statements can become quite big, involve multiple self joins, subqueries ... :D