get all items of category and its child

Question

I'm about to give 100 bounty points for answer to this question

So I have very difficult question about recursions - how to get all items count of category and all childs that contains that parent and more deeper until the end?

I have table:

+----+---------------+-----------------+
| id | category name | category_parent |
+----+---------------+-----------------+
| 1  | cars          |        0        |
+----+---------------+-----------------+
| 2  | real estate   |        0        |
+----+---------------+-----------------+
| 3  | clothes       |        0        |
+----+---------------+-----------------+
| 4  | bmw           |        1        |
+----+---------------+-----------------+
| 5  | audi          |        1        |
+----+---------------+-----------------+
| 6  | 100           |        5        |
+----+---------------+-----------------+
| 7  | 80            |        5        |
+----+---------------+-----------------+
| 8  | A4            |        5        |
+----+---------------+-----------------+
| 9  | QUATRO        |        8        |
+----+---------------+-----------------+
| 10 | TDI           |        8        |
+----+---------------+-----------------+
| 11 | Black         |        9        |
+----+---------------+-----------------+
| 12 | White         |        9        |
+----+---------------+-----------------+
| 13 | 2 doors       |        11       |
+----+---------------+-----------------+
| 14 | 5 doors       |        11       |
+----+---------------+-----------------+

and my products table look like this:

+----+---------------+-----------------+
| id | category_id   | name            |
+----+---------------+-----------------+

and for example I want to count all items that are in cars category. So basically I should pass this category id (1) and somehow make a recursion to count all items. But I have no idea how to deal with it, becouse childs of that category could be unlimited.

So when I want to know all items of that parent count, I should make something like this:

1++:
  4++
  5++:
    6++
    7++
    8++:
      9++:
        11++:
           13++
           14++
        12++
      10++

I hope you will understand what I need and give me any suggestion that could help me.

also, this is the begining I have made so far - I could implement it but in the future I will stuck in recursion... so its worth nothing.

public function get_category_tree_id_list($cat_id, $list_array = FALSE)
{
    if ( !$list_array ){
        $items = $this->system->_getCustomTableData('categories', array(array('category_parent' => $cat_id)), 'id DESC');
        $this->__tmp['id_list'] = [];
        foreach ( $items as $key => $value ) {
            $this->__tmp['id_list'][] = $value['id'];
        }
    }        
}

Answer 1

You would most likely want to do nested sets. They are a little tricky to get set up, but make the queries MUCH simpler. So, instead of category parent, you are going to have two columns - lft and rgt. Left and right are basically the boundaries of a category, if an item's category id is between those values, you know that it is a child of that category.

+----+---------------+-----+------+
| id | category name | lft | rgt  |
+----+---------------+-----+------+
| 1  | cars          |  1  |  24  |
+----+---------------+-----+------+
| 2  | bmw           |  2  |  3   |
+----+---------------+-----+------+
| 5  | audi          |  4  | 23   |
+----+---------------+-----+------+
| 6  | 100           |  5  |  6   |
+----+---------------+-----+------+
| 7  | 80            |  7  |  8   |
+----+---------------+-----+------+
| 8  | A4            |  9  | 22   |
+----+---------------+-----+------+
| 9  | TDI           |  10 | 11   |
+----+---------------+-----+------+
| 10 | Quatro        |  12 | 21   |
+----+---------------+-----+------+
| 11 | Black         |  13 | 18   |
+----+---------------+-----+------+
| 12 | White         |  19 |  20  |
+----+---------------+-----+------+
| 13 | 2 doors       |  14 |  15  |
+----+---------------+-----+------+
| 14 | 5 doors       |  16 | 17   |
+----+---------------+-----+------+

Then, to get the number of items in the cars category, you can do it super simply like this:

SELECT categories.name, items.id, items.category_id, items.name 
FROM categories 
LEFT JOIN items 
    ON (items.category_id BETWEEN categories.lft AND categories.rgt)
WHERE categories.category_name = 'cars'

Obviously you can just change the value of category_name and get the items in ANY category.

Sorry, for some reason the image rotated when I uploaded it here, but if you draw out your categories as circles, and then number the lines, you can see what the value should be for left and right.

I only did cars since I figured you could extrapolate to get the other categories.

So if you write out your categories like this:

Cars(BMW(), Audi(100(),80(),A4(TDI(),Quatro(Black(2dr(),5dr()), White())))

Then you can label your parenthesis with numbers:

Cars[1]->(BMW[2]->()<-[3], Audi[4]->(100[5]->()<-[6],80[7]->()<-[8],A4[9]->(TDI[10]->()<-[11],Quatro[12]->(Black[13]->(2dr[14]->()<-[15], 5dr[16]->()<-[17])<-[18], White[19]->()<-[20])<-[21])<-[22])<-[23])<-[24]

Or if you chart it out as a tree, you can label it like this, where you label the left most node with a number, and only label the right node when you have labeled all of it's children:

Answer 2

I have a new idea I think it will be nice. The idea is this: in category_parent column we will insert a reference to all parents of this node.

+----+---------------+-----------------+
| id | category name |    hierarchy    |
+----+---------------+-----------------+
| 1  | cars          |        1        |
+----+---------------+-----------------+
| 2  | real estate   |        2        |
+----+---------------+-----------------+
| 3  | clothes       |        3        |
+----+---------------+-----------------+
| 4  | bmw           |       1-4       |
+----+---------------+-----------------+
| 5  | audi          |       1-5       |
+----+---------------+-----------------+
| 6  | 100           |      1-4-6      |
+----+---------------+-----------------+
| 7  | 80            |      1-4-7      |
+----+---------------+-----------------+
| 8  | A4            |      1-4-8      |
+----+---------------+-----------------+
| 9  | QUATRO        |     1-4-8-9     |
+----+---------------+-----------------+
| 10 | TDI           |     1-4-8-10    |
+----+---------------+-----------------+
| 11 | Black         |    1-4-8-9-11   |
+----+---------------+-----------------+
| 12 | White         |   1-4-8-9-12    |
+----+---------------+-----------------+
| 13 | 2 doors       |  1-4-8-9-11-13  |
+----+---------------+-----------------+
| 14 | 5 doors       |  1-4-8-9-11-14  |
+----+---------------+-----------------+

if you look at my updated table you will notice that every record has an link to its parents, not only the direct one, But also all of parents. And for that job I made some modification to insert to be:

Insert into table_name (category_name, hierarchy) values ('new_name', (concat(parent_hierarch, '-', (SELECT Auto_increment FROM information_schema.tables WHERE table_name='table_name'))))

Now lets make your desired queries:

1- all sub categories of cars:

select * from table_name where hierarchy like '1-%'

2- if you need all parent of BLACK you simply type:

select * from table_name where hierarchy = '1-4-8-9' or hierarchy = '1-4-8' or hierarchy = '1-4' or hierarchy = '1'

(you can build that query from php, splitting hierarchy field at '-' char)

3- To see all categories, with level and direct parent:

select *, SUBSTR(hierarchy, 1, (LENGTH(hierarchy) - LENGTH(id) - 1)) as parent, LENGTH(hierarchy) - LENGTH(REPLACE(hierarchy, '-', '')) as level From table_name

+----+---------------+-----------------+-----------+--------+
| id | category name |    hierarchy    |   parent  |  level |
+----+---------------+-----------------+-----------+--------+
| 1  | cars          |        1        |           |    0   |
+----+---------------+-----------------+-----------+--------+
| 2  | real estate   |        2        |           |    0   |
+----+---------------+-----------------+-----------+--------+
| 3  | clothes       |        3        |           |    0   |
+----+---------------+-----------------+-----------+--------+
| 4  | bmw           |       1-4       |     1     |    1   |
+----+---------------+-----------------+-----------+--------+
| 5  | audi          |       1-5       |     1     |    1   |
+----+---------------+-----------------+-----------+--------+
| 6  | 100           |      1-4-6      |    1-4    |    2   |
+----+---------------+-----------------+-----------+--------+
| 7  | 80            |      1-4-7      |    1-4    |    2   |
+----+---------------+-----------------+-----------+--------+
| 8  | A4            |      1-4-8      |    1-4    |    2   |
+----+---------------+-----------------+-----------+--------+
| 9  | QUATRO        |     1-4-8-9     |   1-4-8   |    3   |
+----+---------------+-----------------+-----------+--------+
| 10 | TDI           |     1-4-8-10    |   1-4-8   |    3   |
+----+---------------+-----------------+-----------+--------+
| 11 | Black         |    1-4-8-9-11   |  1-4-8-9  |    4   |
+----+---------------+-----------------+-----------+--------+
| 12 | White         |   1-4-8-9-12    |  1-4-8-9  |    4   |
+----+---------------+-----------------+-----------+--------+
| 13 | 2 doors       |  1-4-8-9-11-13  |1-4-8-9-11 |    5   |
+----+---------------+-----------------+-----------+--------+
| 14 | 5 doors       |  1-4-8-9-11-14  |1-4-8-9-11 |    5   |
+----+---------------+-----------------+-----------+--------+

This is a new idea and need some improvement. I hope you benefit from it.

Answer 3

You may want to look at this article on suggestions for handling tree-structured data in MySQL.

http://mikehillyer.com/articles/managing-hierarchical-data-in-mysql

What approach you choose to take would likely depend on what your application read and write use cases consist of.

Currently, you are using an adjacency list model, which is particularly problematic when working with arbitrary tree depth type of queries. If this is a major use case for you, you may want to consider nested set approach, which though probably not as intuitive, is much better suited for arbitrary depth tree queries.

The challenge with the nested set approach is that updates to the table are typically more difficult to manage.

Answer 4

To call this, simply construct the object targetId as argument:

Like :

$counter = new RecursiveCounter(8);
$count = $counter->getCount();

The Class:

class RecursiveCounter {
private $row;
private $targetId;

public function __construct($targetId) {
    //Just setting up the info I need. You need to consider how to get the data from database and replace the constructor
    $this->row = array(
        1 => array("category" => "cars", "parent" => 0),
        2 => array("category" => "realestate", "parent" => 0),
        3 => array("category" => "clothes", "parent" => 0),
        4 => array("category" => "bmw", "parent" => 1),
        5 => array("category" => "audi", "parent" => 1),
        6 => array("category" => "100", "parent" => 5),
        7 => array("category" => "80", "parent" => 5),
        8 => array("category" => "A4", "parent" => 5),
        9 => array("category" => "QUATRO", "parent" => 8),
        10 => array("category" => "TDI", "parent" => 8),
        11 => array("category" => "Black", "parent" => 9),
        12 => array("category" => "White", "parent" => 9),
        13 => array("category" => "doors", "parent" => 11),
        14 => array("category" => "doors", "parent" => 11)
    );
    $this->targetId = $targetId;
}

public function getCount() {
    // Entry point
    $count = 0;
    foreach ($this->row as $id => $row) {
        if ($this->isMatchTarget($id)) {
            $count++;
        }
    }
    return $count;
}
private function getParent($id) {
    $parentId = $this->row[$id]["parent"];
    if (array_key_exists($parentId, $this->row)) {
        return $parentId;
    } else {
        return false;
    }
}

private function isMatchTarget($id) {
    // 1. If the supplied id is the target id, job is done and return true;
    // 2. If not:
    //      Get the parent ud;
    //      If parent id is not 0 (Meaning it has a parent), keep on checking
    //          What to check? Check if the parent id is matching
    //          If the the parent id is still not equal to target or 0, it will check the parent of parent until it they are equal or it is 0
    //      if there is no parent, and the id dont match (Ending condidtion)
    //          return false;
    if ($id == $this->targetId) {
        return true;
    } else {
        $parentId = $this->getParent($id);
        if (0 != $parentId) {
            return $this->isMatchTarget($parentId);
        } else {
            return false;
        }
    }
}

}