Page 1 of 2

Logic Help

Posted: Tue Jun 20, 2006 5:36 pm
by s.dot
I'm setting up the basic database structure for a site *my first* client wants me to do. I've never done anything like this, so I thought I would ask here for help.

He wants a referral system. Alright, I've done that before. But he wants it to go different levels deep depending on the account type of the referrer.

Type 1 goes 3 levels deep
Type 2 goes 5 levels deep
Type 3 goes 7 levels deep
Type 4 goes 10 levels deep

By levels, I mean something like this.

- User A refers user B
- User B refers user C
- User C refers user D
- User A refers user E

So now, user A's downline (different level referrers) looks like this

1st level (direct referrals)
- B
- E

2nd level
- C

3rd level
- D

I've already figured out that I'm going to need a separate database table, perhaps called `downline` with 3 separate fields.

`personreferring`, `personwhogotreferred`,`level`

So a sample entry would look like

BOB, SUSY, 3

My question is this, how do I figure out what level each person is on? Do I have to do up to 10 separate queries to determine if each person was referred by someone else, then insert up to 10 new records in the downline table?

Obvsiously I have to do this on signup, or upon activation, so I didn't want anything to be too complex.. although it would be transparent to the end user... so I guess it doesn't really matter.

Some logic on how to do this?

[edit] After thinking about it, it seems i could only log the direct (1st level) referrals, then use a script to calculate the downlines, based on first level referrals only.

Posted: Tue Jun 20, 2006 5:52 pm
by Robert Plank
If all you need to know is the level, just lookup level of the referring user, add one, store that in the database for the new user.

If you want to show the upline and downline of a user, you will have to add 2 columns to the table.

Read this article: http://www.sitepoint.com/article/hierar ... a-database

By storing left and right tree values for each row in the table you can get a user's whole downline in one query, and the whole upline in one query.

To get the downline of user X: grab all rows form the table whose LEFT (or RIGHT values, doesn't matter) is between X's LEFT and RIGHT values.
To get the upline of user X: grab all rows from the table whose LEFT value is less than X's LEFT, and whose RIGHT value is greater than X's RIGHT.

If your referral system only allows each user to be referred by one person, then a person's level is just the COUNT(*) of that upline query.

True, it'll take you 30 mins to read that article but if the system goes 500 levels deep you'll only need one query, not 500. :D

Posted: Wed Jun 21, 2006 3:40 pm
by s.dot
Hmm, I'm not sure I understand the concept of your post. But that's exactly what I need to do.. I just thought I'd explain it because I wasn't sure if people understood the concept of downlines.

Ideally, all i need to show is any given users downline. Upline doesn't matter. I'm having trouble grasping a concept other than a recursive lookup, doing x queries.

If you could elaborate, i'd be grateful. :)

Posted: Wed Jun 21, 2006 4:13 pm
by Weirdan
Well, this approach is usually called 'nested sets'... It's very efficient for retrieve, yet you have to reindex ~1/2 of your records on every insert. To grasp it adequately you have to think different :)

Don't think of it as a tree with branches that connect your users. Using your example we will substitute the term 'referred' with a term 'ate':
- User A ate user B
- User B ate user C
- User C ate user D
- User A ate user E

So we could picture the system as follows:

Code: Select all

|-------------User A----------------------------------------------------|
|      |----------------User B--------------|     |------User E----|    |
|      |     |---------User C--------|      |     |                |    |
|      |     |     |---User D---|    |      |     |                |    |
|      |     |     |            |    |      |     |                |    |
|------|-----|-----|------------|----|------|-----|----------------|----|-------------------------->
|      |     |     |            |    |      |     |                |    |              Numeric axis
A(l)  B(l)  C(l)  D(l)        D(r)  C(r)   B(r)  E(l)             E(r) A(r)
... where X(l|r) is integer.
As you can see, we can uniquely identify each user with a pair of numbers, representing its left and right boundary.
So to get everyone who is in User B's stomach we would query for users whose boundaries are within User B's boundaries.

Posted: Wed Jun 21, 2006 4:14 pm
by Weirdan
heh, "that's how cannibalism works" :lol:

Posted: Wed Jun 21, 2006 7:48 pm
by s.dot
That.... may be the coolest thing I've seen in a while. :-P So, beginning to implement this into a database structure, how would one go about assigning boundries?

Posted: Wed Jun 21, 2006 8:19 pm
by Weirdan
inserting a standalone node:
select the maximum existing right boundary + 1, use it as left boundary of newly created node
right boundary in this cause would be `left`+1

inserting a descendant node:

Code: Select all

mysql_query("START TRANSACTION");
$res = mysql_query("SELECT `right` FROM `table` WHERE `id`=" . $parent_id);
list($p_right) = mysql_fetch_row($res);
mysql_query("UPDATE `table` SET `left`=`left`+2 WHERE `left`>" . $p_right); // move left boundaries
mysql_query("UPDATE `table` SET `right`=`right`+2 WHERE `right`>=" . $p_right);
mysql_query("INSERT  INTO `table` SET `left`=" . $p_right . ", `right`=" . ($p_right+1));
mysql_query("COMMIT");

Posted: Wed Jun 21, 2006 9:48 pm
by s.dot
cool. i'm learning to think of it as linear instead of a tree (very hard concept to grasp!). I'm going to have a go at it in the morning. I'm sure i'll be back for questions :P

Thanks, Weirdan. :)

Posted: Tue Mar 13, 2007 5:47 pm
by s.dot
So, my need for this came up again. I never implemented it the first time.. so here goes my shot at understanding it again.

Each user has their own left boundary, and their right boundary. For every direct referral, we push the referrering users right boundary to the right 2, and give the new user a left and right boundary inside of the referring user. For a non-referred user, he starts his left boundary at the "max right boundary + 1" and his right boundary to start off with would be the "max right boundary + 2". Am I grasping this so far?

Good table setup?

Code: Select all

CREATE TABLE `downline` (
`id` INT( 10 ) NOT NULL AUTO_INCREMENT PRIMARY KEY ,
`username` VARCHAR( 25 ) NOT NULL ,
`left_boundary` INT( 10 ) NOT NULL ,
`right_boundary` INT( 10 ) NOT NULL 
) ENGINE = innodb;

Posted: Tue Mar 13, 2007 5:54 pm
by Weirdan
scottayy wrote: Each user has their own left boundary, and their right boundary. For every direct referral, we push the referrering users right boundary to the right 2, and give the new user a left and right boundary inside of the referring user. For a non-referred user, he starts his left boundary at the "max right boundary + 1" and his right boundary to start off with would be the "max right boundary + 2". Am I grasping this so far?

Good table setup?

Code: Select all

CREATE TABLE `downline` (
`id` INT( 10 ) NOT NULL AUTO_INCREMENT PRIMARY KEY ,
`username` VARCHAR( 25 ) NOT NULL ,
`left_boundary` INT( 10 ) NOT NULL ,
`right_boundary` INT( 10 ) NOT NULL 
) ENGINE = innodb;
seems ok to me

Posted: Tue Mar 13, 2007 6:15 pm
by s.dot
So, I did a sample script to insert a new node into the downline table.

Code: Select all

<?php

//user was referred by user 'jimbob'

//get user jimbobs right boundary
$rtbndry = mysql_query("SELECT `right_boundary` FROM `downline` WHERE `username` = 'jimbob' LIMIT 1") or die(mysql_error());
$rtbndry = mysql_result($rtbndry, 0);

//push everyone to the right if their right boundary is > $rtbndry
mysql_query("UPDATE `downline` SET `right_boundary`=`right_boundary`+2 WHERE `right_boundary` >= '$rtbndry'") or die(mysql_error());

//now there is space inside of user jimbob to add this user

//left boundary is the old right boundry
$newuser_lftbndry = $rtbndry;

//right boundry is the old right boundary + 1
$newuser_rtbndry = $rtbndry+1;

mysql_query("INSERT INTO `downline` (`username`,`left_boundary`,`right_boundary`) VALUES('$newuser', '$newuser_lftbndry', '$newuser_rtbndry')") or die(mysql_error());

?>
I came up with this, and this would work perfectly *inside my head*, but then I look at weirdans example and there's moving of the *left* boundaries. Why!?

Posted: Tue Mar 13, 2007 7:02 pm
by s.dot
Well crap, I'll just give it a try and see what happens. I dunno how i'm going to automate a thousand or so referrals just to see how the thing works :))

Posted: Tue Mar 13, 2007 8:01 pm
by s.dot
Sorry for all the consecutive posts.

Here's my code

Code: Select all

if(!empty($_COOKIE['ref']))
{
	//referrer
	$ref = mysql_real_escape_string(htmlentities(stripslashes($_COOKIE['ref']), ENT_QUOTES));
			
	//see if user exists
	$existsr = mysql_query("SELECT count(*) FROM `users` WHERE `username` = '$ref' LIMIT 1") or die(mysql_error());
	if(mysql_result($existsr, 0) == 1)
	{
		//user exists
		//insert dependent node
		$rtbndry = mysql_query("SELECT `right_boundary` FROM `downline` WHERE `username` = '$ref' LIMIT 1") or die(mysql_error());
		$rtbndry = mysql_result($rtbndry, 0);

		//push left boundaries
		mysql_query("UPDATE `downline` SET `left_boundary`=`left_boundary`+2 WHERE `left_boundary` > '$rtbndry'") or die(mysql_error());

		//push everyone to the right if their right boundary is > $rtbndry
		mysql_query("UPDATE `downline` SET `right_boundary`=`right_boundary`+2 WHERE `right_boundary` >= '$rtbndry'") or die(mysql_error());

		//now there is space inside  to add this user

		//left boundary is the old right boundry
		$newuser_lftbndry = $rtbndry;

		//right boundry is the old right boundary + 1
		$newuser_rtbndry = $rtbndry+1;

		mysql_query("INSERT INTO `downline` (`username`,`left_boundary`,`right_boundary`) VALUES('$user_username', '$newuser_lftbndry', '$newuser_rtbndry')") or die(mysql_error());

	} else
	{
		//insert new node
		$max_right = mysql_query("SELECT MAX(`right_boundary`) FROM `downline`") or die(mysql_error());
		$max_right = mysql_result($max_right, 0);
			
		$new_left = $max_right + 1;
		$new_right = $max_right + 2;
			
		mysql_query("INSERT INTO `downline` (`username`,`left_boundary`,`right_boundary`) VALUES('$user_username', '$new_left', '$new_right')") or die(mysql_error());
	}
} else
{
	//insert new node
	$max_right = mysql_query("SELECT MAX(`right_boundary`) FROM `downline`") or die(mysql_error());
	$max_right = mysql_result($max_right, 0);
			
	$new_left = $max_right + 1;
	$new_right = $max_right + 2;
			
	mysql_query("INSERT INTO `downline` (`username`,`left_boundary`,`right_boundary`) VALUES('$user_username', '$new_left', '$new_right')") or die(mysql_error());
}
I made some sample users and drew in a tree view what I expected to happen, as far as users and levels are concerned

Code: Select all

-Scrotaye
     - Suzy
     - Jim
          - Jack
          - Scott
-Bob
I made all of those users, with the appropriate referrals to try to get my downline table to represent the downline tree above.

Here's what the table now looks like.

Code: Select all

id     |     username     |      left_boundary     |      right_boundary  
----------------------------------------------------------------------------------
   1    |      scrotaye      |       1                        |          10 
-----------------------------------------------------------------------------------
   2    |      bob              |       11                     |           12 
-----------------------------------------------------------------------------------
   3    |      suzy         |        2                       |          3 
-----------------------------------------------------------------------------------
   4    |      jim            |        4                       |           9 
-----------------------------------------------------------------------------------
   5    |      jack           |        5                       |          8 
-----------------------------------------------------------------------------------
   6    |      scott          |        6                       |          7 
-----------------------------------------------------------------------------------
In my head, without doing queries, this appears to be correct. Does it to you? Would this work even if there were thousands of members?

Posted: Wed Mar 14, 2007 4:01 pm
by s.dot
I believe I have it all sorted out, with one question remaining.

Say a users chooses to delete their account. I can just delete their record from the `downline` table shown above, without having to change left and right boundaries, right? I mean, it would create a void in the numbers, but the uplines and downlines would remain the same (hopefully)?

Posted: Wed Mar 14, 2007 4:07 pm
by John Cartwright
I often find it much easier to set a flag, rather than deleting rows in the database. So in your case, simply have a field 'activated' (0-1).. this way your referals won't be messed, plus you'll have a full dataset.