CODEWITHSUNDEEP
phpmysqlalgorithmtree
madpoet
madpoet

Reputation: 1063

Tree Traversal recursive calculation

We have users, questions and unlimited levels of categories. The users can get some points from questions. Questions can have multiple categories.

What I want to do is to calculate the top users per category: It's simply total points taken from the questions under that category AND it's sub-categories too.

So, I have these tables:

questions
--------------
id
title
question

categories
--------------
id
parent_id
category
lft
rgt

question_categories
--------------
question_id
category_id

users
--------------
id
username

user_points
--------------
id
user_id
question_id
point_type
points

user_category
--------------
user_id
category_id
points

What I want to do is to calculate user_category.points value. Summing up the points for each category is easy but including the sub-categories is getting complicated.

What might be the best way to do this?

Example calculation:

Let's say the categories are:

Programming
   PHP
      Zend Framework
      Symfony
   Java
   Ruby on Rails

Assume that the user got 3 points from Zend Framework, 2 points from PHP, 5 points from java and 1 point from Rails. The points for this user per categories will be:

Programming            11 (5+5+1)
   PHP                  5 (2+3)
      Zend Framework    3
      Symfony
   Java                 5
   Ruby on Rails        1

Upvotes: 0

Views: 539

Answers (4)

Puggan Se
Puggan Se

Reputation: 5846

This php and SQL should get you the top 3 users for each category including sub categories:

$query = "SELECT id, parent_id FROM categories";
$parent = array();
...fetch mysql data loop depending on what connection you use, mysqli or pdo...
{
   $parent[$result['id']] = $result['parent_id'];
}

$childs = array();

foreach($parent as $id => $parrent_id)
{
   $childs[$parrent_id][$id] = $id;
   $next_parrent_id = $parrent_id;
   while($next_parrent_id = $parent[$next_parrent_id])
   {
      $childs[$next_parrent_id][$id] = $id;
   }
}

foreach($parent as $id => $parrent_id)
{
   $current_categories = array($id => $id) + $childs[$id];
   $query = "SELECT user_id, username, SUM(points) AS total_points
             FROM user_points 
             LEFT JOIN users ON (user_id = users.id)
             LEFT JOIN question_categories USING (question_id)
             WHERE category_id IN (" . implode(', ', $current_categories). ")
             ORDER BY total_points DESC
             LIMIT 3";
   ...fetch mysql data loop...
}

Upvotes: 0

thebjorn
thebjorn

Reputation: 27311

If you're only going to sum per top-level category, then you should add a field to your categories table called root_id (holding the id of the transitive parent of the category).

Then your sum would be calculated as:

select up.user_id, ctg.root_id, sum(up.points)
from user_points up
join question_categories qc on up.question_id = qc.question_id
join categories ctg on qc.category_id = ctg.id
group by up.user_id, ctg.root_id

Upvotes: 0

dadinck
dadinck

Reputation: 1158

Perhaps it would be best to use tags instead of a hierarchy. For instance, anything with a "Zend Framework" will also have "PHP" and "Programming" tags. This also helps when some categories can appear in multiple places. For instance, I can use ajax in jQuery and also Javascript. Then, add 1 to each tag listed in the category for the user.

Upvotes: 1

Nir Alfasi
Nir Alfasi

Reputation: 53525

I would create a user_categories table in which I would store 3 values: user_id, category_id and user_score. It's easy to maintain (need only to INSERT or UPDATE) and it's also easy to query for top-users of every category.

Upvotes: 0

Related Questions