Hierarchical Data

CreativeLogic · 12-08-2007, 04:27 PM

I've come across a problem I can't exactly figure out. The problem at hand is with categories and unlimited subcategories. I've done quite a bit of research on the subject and it seems that Adjacency List Model is the best approach for what I'm needing. The Nested Set Model would be ideal optimizing queries but it supports at most two children and only allows one one parent for each node. That is the problem I'm running into.

The only problem with the Adjacency List Model is the fact that getting all categories and subcategories and grouping them together properly with the children under the proper parents doesn't allow for optimized queries and only works properly using recursion. Below is an example of why it's not optimized:

Code:

function pull_categories ($parent_id = 0)
{
    $categories = array ();
    $categories_query = $this->initialize->db->query ("SELECT * FROM    categories WHERE parent_id = '" . $this->initialize->db->e ($parent_id) . "'");
    while ($category = $this->initialize->db->fetch ($categories_query))
    {
        $categories[$category['category_id']] = $category;
        $categories[$category['category_id']]['children'] = $this->pull_categories ($category['category_id']);
    }
    return $categories;
}

To get around the recursion is gathering all of the information with one loop and storing it in an array then fixing the data that way.

So the question I have for you, does anyone know any other better ways to accomplish what I'm after? Anyone know any data structures or any types of trees that would allow for better optimizing the code?

Karl · 12-08-2007, 04:34 PM

I've only skimmed over your post so if this of no use, I do appologise. Have you tried a "Modified Preorder Tree Traversal" (lol who the hell came up with that name)?

It's a very flexible system, you can read a good article on it here. Thanks to gcbdm for originally posting it in this thread.

CreativeLogic · 12-08-2007, 04:40 PM

The link you posted doesn't help as it only supports two children for each parent. I've read that article and many others and none seem to give a helping hand on any ideas.

The only thing I can think that would be out there that could possibly help is some type of data tree structure that I'm not familiar with currently.

bdm · 12-08-2007, 05:51 PM

The modified preorder tree traversal methods supports as many children as you need per parent. I've already implemented it with 10+ children on certain parents.

PHP Code:


			
$connection = mysql_connect("localhost", "root", "x");
    $database = mysql_select_db("test", $connection);

    $result = mysql_query("SELECT COUNT(parent.category_id) AS depth, cat.name as cname, products.name as pname
  FROM categories AS parent
INNER
  JOIN categories AS cat
    ON cat.lft BETWEEN parent.lft AND parent.rgt
LEFT OUTER
  JOIN products 
    ON products.category_id = cat.category_id") or die(mysql_error());

$current_cat = NULL;
while($row = mysql_fetch_assoc($result))
{
    if($current_cat != $row['cname'])
    {
        /*display the new category however you wish here*/
        echo str_repeat("&nbsp;&nbsp;&nbsp;&nbsp;", $row['depth']) . "<strong>" . ucwords(strtolower($row['cname'])) . "</strong><br />\n";
        $current_cat = $row['cname'];
    }
    /*display the product however you wish here;
        you could use $row['depth'] to line up with the current (sub-)category*/
    echo str_repeat("&nbsp;&nbsp;&nbsp;&nbsp;", $row['depth']) . $row['pname'] . "<br />\n";
}

Here is some not so good code which I used as a base to link items to categories.

My table structures were:

sql Code:

CREATE TABLE categories (
 category_id INT AUTO_INCREMENT PRIMARY KEY,
 name VARCHAR(20) NOT NULL,
 lft INT NOT NULL,
 rgt INT NOT NULL
);

CREATE TABLE products (
product_id INT AUTO_INCREMENT PRIMARY KEY,
name VARCHAR(40),
category_id INT NOT NULL
);

And some sample data:

Code:

"category_id","name","lft","rgt"
1,"ELECTRONICS",1,20
2,"TELEVISIONS",2,9
3,"TUBE",3,4
4,"LCD",5,6
5,"PLASMA",7,8
6,"PORTABLE ELECTRONICS",10,19
7,"MP3 PLAYERS",11,14
8,"FLASH",12,13
9,"CD PLAYERS",15,16
10,"2 WAY RADIOS",17,18

"product_id","name","category_id"
1,"product under television",2
2,"product under television",2
3,"product under tube",3
4,"product under lcd",4
5,"product under lcd",4
6,"product under plasma",5
7,"product under flash",8
8,"product under portable electronics",6
9,"product under portable electronics",6
10,"product under portable electronics",6
11,"product under television",2
12,"product under electronic",1
13,"product under cd players",9

Once you get a firm grasp on how the left/right values work. The amount of flexibility is indeterminable. And as you can see, there is no recursion. We query our database once and use very simple logic.