Logic Help

Not for 'how-to' coding questions but PHP theory instead, this forum is here for those of us who wish to learn about design aspects of programming with PHP.

Moderator: General Moderators

User avatar
s.dot
Tranquility In Moderation
Posts: 5001
Joined: Sun Feb 06, 2005 7:18 pm
Location: Indiana

Logic Help

Post 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.
Set Search Time - A google chrome extension. When you search only results from the past year (or set time period) are displayed. Helps tremendously when using new technologies to avoid outdated results.
Robert Plank
Forum Contributor
Posts: 110
Joined: Sun Dec 26, 2004 9:04 pm
Contact:

Post 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
User avatar
s.dot
Tranquility In Moderation
Posts: 5001
Joined: Sun Feb 06, 2005 7:18 pm
Location: Indiana

Post 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. :)
Set Search Time - A google chrome extension. When you search only results from the past year (or set time period) are displayed. Helps tremendously when using new technologies to avoid outdated results.
User avatar
Weirdan
Moderator
Posts: 5978
Joined: Mon Nov 03, 2003 6:13 pm
Location: Odessa, Ukraine

Post 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.
User avatar
Weirdan
Moderator
Posts: 5978
Joined: Mon Nov 03, 2003 6:13 pm
Location: Odessa, Ukraine

Post by Weirdan »

heh, "that's how cannibalism works" :lol:
User avatar
s.dot
Tranquility In Moderation
Posts: 5001
Joined: Sun Feb 06, 2005 7:18 pm
Location: Indiana

Post 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?
Set Search Time - A google chrome extension. When you search only results from the past year (or set time period) are displayed. Helps tremendously when using new technologies to avoid outdated results.
User avatar
Weirdan
Moderator
Posts: 5978
Joined: Mon Nov 03, 2003 6:13 pm
Location: Odessa, Ukraine

Post 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");
User avatar
s.dot
Tranquility In Moderation
Posts: 5001
Joined: Sun Feb 06, 2005 7:18 pm
Location: Indiana

Post 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. :)
Set Search Time - A google chrome extension. When you search only results from the past year (or set time period) are displayed. Helps tremendously when using new technologies to avoid outdated results.
User avatar
s.dot
Tranquility In Moderation
Posts: 5001
Joined: Sun Feb 06, 2005 7:18 pm
Location: Indiana

Post 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;
Set Search Time - A google chrome extension. When you search only results from the past year (or set time period) are displayed. Helps tremendously when using new technologies to avoid outdated results.
User avatar
Weirdan
Moderator
Posts: 5978
Joined: Mon Nov 03, 2003 6:13 pm
Location: Odessa, Ukraine

Post 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
User avatar
s.dot
Tranquility In Moderation
Posts: 5001
Joined: Sun Feb 06, 2005 7:18 pm
Location: Indiana

Post 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!?
Set Search Time - A google chrome extension. When you search only results from the past year (or set time period) are displayed. Helps tremendously when using new technologies to avoid outdated results.
User avatar
s.dot
Tranquility In Moderation
Posts: 5001
Joined: Sun Feb 06, 2005 7:18 pm
Location: Indiana

Post 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 :))
Set Search Time - A google chrome extension. When you search only results from the past year (or set time period) are displayed. Helps tremendously when using new technologies to avoid outdated results.
User avatar
s.dot
Tranquility In Moderation
Posts: 5001
Joined: Sun Feb 06, 2005 7:18 pm
Location: Indiana

Post 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?
Set Search Time - A google chrome extension. When you search only results from the past year (or set time period) are displayed. Helps tremendously when using new technologies to avoid outdated results.
User avatar
s.dot
Tranquility In Moderation
Posts: 5001
Joined: Sun Feb 06, 2005 7:18 pm
Location: Indiana

Post 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)?
Set Search Time - A google chrome extension. When you search only results from the past year (or set time period) are displayed. Helps tremendously when using new technologies to avoid outdated results.
User avatar
John Cartwright
Site Admin
Posts: 11470
Joined: Tue Dec 23, 2003 2:10 am
Location: Toronto
Contact:

Post 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.
Last edited by John Cartwright on Wed Mar 14, 2007 4:08 pm, edited 1 time in total.
Post Reply