displaying categories and sub-categories

[sde]

re: mysql

these are the fields in my "categories" table.

category_id
parent_id
category_name

i need to make a tree and display these in order. here are some examples of what is inside this table:

1  NULL  tv's
2  NULL  cameras
3  1        Big Screens
4  1        Plasmas
5  2        digital
6  2        35mm
7  5        Smart Media

i need each of the sub-categories to go under the parent categories. the idea here is to be able to have infinate sub-categories nested inside categories.

so the results of my query will order it like this:

tv's
     Big Screens
     Plasmas

cameras
     digital
          smart media
     35mm

anyone have experience with this?

[sde]

eh, i will have to settle on limiting my levels of sub-categories to a fixed number. but i suppose that is ok.

[sdeming]

Well, you are brushing on heirarchical data storage, something that often baffles people because it is so bloody difficult to envision. We have troubles with the concept of infinity.

Basically, your best bet is to have a different table for tracking the heirarchies, keeping your data separate like this:

categories:
cat_id
description
primary key on cat_id

heirarchy:
cat_id
parent_id
primary key on cat_id, parent_id
foreign key on cat_id to categories.cat_id
foreign key on parent_id to categories.cat_id

You can generate your categories however you wish. Just keep plugging em in, until they are put in the heirarchy they aren't used.

1 tv's
2 cameras
3 Big Screens
4 Plasmas
5 digital
6 35mm
7 Smart Media

Add your categories to the heirarchy, root nodes should point back to themselves like this:

1 1 -- tv's points to tv's, indicating a root node
2 2 -- same for cameras

then add to the heirarchies like this:

3 1 -- point Big Screens to the tv's category
4 3 -- point Plasmas to the Big Screens category
5 2 -- point digital to the cameras category
6 2 -- point 35mm to the cameras category
7 5 -- point Smart Media to the digital category

Now to traverse the tree you need a couple of queries:

Select all root nodes:
SELECT cat_id FROM heirarchy WHERE cat_id = parent_id;

Select child nodes:
SELECT cat_id FROM heirarchy WHERE parent_id = ?
Using cat_id from the parent node as the only parameter.

Now in code, basically you want to build your root node list, then recursivley iterate through each node following the heirarchy. For each child node you read from your select statement, you have to call the "Select child nodes" query usings cat_id as the parent_id.

What can get really weird here is that there is nothing preventing you from adding the Smart Media category with a 35mm parent as well, and many times this is exactly what you want to do. However, there is also nothing preventing you from adding tv's to ameras and then cameras to TV's creating an infinite loop. These are all things that have to be done programatically and very carefully.

I hope this helps a bit. Don't give in, these kinds of features are really nice to have!

[sde]

thank you! yesterday i got very fusterated. it was the first time i hit a brick wall with php, and not a very good feeling. i decided to scrap the forums and ecommerce sites i've been working on for the last few months because of this database flaw. they only had 2 levels, and you could only add items, or forums to the sub category , or second level.

i am going to see how i do with this approach later today. thanks a bunch.

[abc123]

hmmm that reminds me of a linked list..

[sdeming]

It's similar to a linked list, but each node can begin a new list. The way this is implemented is incredibly simple and does rely on basic list principles and nothing more.

[technobard]

Just to add my two cents, I will both agree and disagree with sdeming's proposed solution. First the agreement: for small enough volumes of data, this approach should work fine. It's an understandable solution (which is always nice to have!).

Now the disagreement: using successive queries to the database to walk the tree is very inefficient. The proposed solution, assuming you just print the results, also does not preserve the parent/child relationship. I'm guessing that you will eventually want to do more than just display an indented list.

I would suggest keeping the data as you had it in a single table: ID, PARENT_ID, DESCRIPTION
sdeming's solution is more normalized, but it only matters if you plan on allowing a child to have more than one parent (which I believe is a bad idea)

The first step is to read all of the data from the table:

select id, parent_id, description from hierarchy
order by parent_id

The next step is to loop through each row and create an in-memory tree structure. This would start with an imaginary root node at level 0. The root is the parent to all level 1 objects. The class defining your tree structure would have an id, parent_id, description, level, and an array of children. Level is optional, but could be used by a print method to specify the number of tabs to use for indenting. The array would only store the id values for each of the children.

I specified in the SQL that the rows be ordered by parent_id so that all children are grouped together (not strictly necessary). For each row, check to see if an object exists with that id. If not, create a new object. Check to see if the parent exists. If not create a new object. Add an array element to the parent for this id. Go to the next element and repeat.

As each object is created, an element is added to an associative array that uses the id as the key, and a pointer to the object as the value. In Java, I'd use a Hashtable. I know PHP allows this type of structure, but I'm not sure what it is called. This allows you to take an id from the array of child ids and immediately reference the object that it belongs to.

To print the tree in order, you have to traverse it. You start by retrieving the pointer to the object whose id = 0 (the root node). You then loop through the array of child ids (your top level of categories -- level 1), retrieving the objects along the way and calling the print method. If children exist, you perform the same function on the next level (looping through child ids...calling print methods). This would work nicely as a recursive function call that terminates when an object has no children. When this happens, the program goes to the next level 1 category and repeats until all level 1s are depleted.

This solution will work for any depth tree, executes a single SQL query, and preserves the parent/child relationship.

One last thing. If the description "Cameras" appears under multiple categories, I would create unique ids for each entry. This preserves the single parent rule and keeps your tree traversal consistent. If the description has to change across the board, you can change it with a single update statement.

[sdeming]

Technobard, you have some good and valid points. With the software I write, we rely heavily on breaking the multiple parent rule that you describe. It was important to us to break this rule because of our environment; imagine doing telephone billing for a large coroporation who requires multiple levels of billing statements, reports, and the like across many departments rolled up and aggregated in different ways. Believe it or not, a single department may have to be reported for multiple department heads who live in parallel.

Further, this company wanted to arrange their reporting heirarchies differently for varying views. To accomodate this requirement we simply added a new field to the heirarchy table, called it heirarchy_id and now they can have separate living heirarchies representing the same data set. The lesson learned here was that when people were trying to talk me out of "over normalizing" the database, I had to keep repeating to them that intentionally limiting yourself at any point is more distracting than just doing things the more complicated complete way from the start.

Basically, let your data be your data and not your guide. Guide your data through other means, programmatically or with other data constructs but not embedded within. It's when you least expect it that you'll be rearchitecting your database simply because the data is too specific for a single need.

Sometimes I talk to much.

Oh, just to add about this real quick:

One last thing. If the description "Cameras" appears under multiple categories, I would create unique ids for each entry. This preserves the single parent rule and keeps your tree traversal consistent. If the description has to change across the board, you can change it with a single update statement.

If you do this, then your reporting can no longer rely on your heirarchy or you'll end up with two identical categories listed with two different numbers.

If I come across as rude I apologize. It certainly is not my intent to do so but re-reading this it does seem a little, rash.

[technobard]

You didn't come across as rude at all. Sometimes I talk too much, too. One size doesn't fit all. I wanted to present a different view based on my experience. If multiple hierarchies are required, then by all means. On a project I worked on, we didn't actually want multiple hierarchies just duplicate descriptions. Later those descriptions changed slightly in some cases, which is why I brought up the point.

In real life, I'm a DBA. I write code when I can get away with it.

[sde]

ok, i'm trying this again, but here is where i get stuck. I can not figure out the logic on how to set up the code so it can keep grabing cat_id's from the parent_id's forever. I can only figure out how to make it travers to a set number of levels.

For Example, here is a script that will pull 2 levels:

PHP Code:

<?
$result=mysql_query("select cat_id,cat_name from heirarchy where cat_id=parent_id");
        $num=mysql_numrows($result)
        for($i=0;$i<$num;$i++)
        {
            $cat_id=mysql_result($result,$i,"cat_id");
            $cat_name=mysql_result($result,$i,"cat_name");
            
            echo "$cat_name";
            
            $result=mysql_query("select * from heirarchy where parent_id='$cat_id'");
            $num=mysql_numrows($result);
            for($i=0;$i<$num;$i++)
            {
                $cat_id=mysql_result($result,$i,"cat_id");
                $cat_name=mysql_result($result,$i,"cat_name");
                
                echo "&nbsp; &nbsp; $cat_name";    
            }
        }
?>

If I want it to run 5 levels, .. then i have to keep repeating the second query 5 times.. each inside the one above it. The concept of infinity still baffles me.

Does this make sense? My brain just won't work like that. Is there a way to run a loop that will just keep going until there are no parent id's left?

[sde]

here's anothing thing i am noticing.

in the heirarchy table, there will be 1 parent id for each category id, .. so why does this need to be in a different table?

the only reason i can think of is if the category would have more than 1 parent, in which case the category id field could not be a primary field because there could be duplicates.

i'm just trying to figure this out so i don't waste time developing something i will later find a better way to design.

[sdeming]

Actually, you don't really need the other table as Technobard noted in his response. It's a design decision as to whether or not you'll ever want multiple heirarchies and categories with multiple parents. The design principles that say you should keep the heirarchy definition separate are based on normalization rules and keeping your data guidance separate from your data.

The primary key should be on both fields together, cat_id and parent_id so you can have duplicates of each but not a duplicate of the same combination.

Now on to your code troubles. The easiest way to resolve your problems is to use recursion. Create a function that traverses a single categories children then calls itself on each child. By nature while it's processing a the child it'll be calling itself again for each of the childs child infinitely until it reaches the end. This is common for traversing any tree.

I'd be interested in seeing your code when you do this! I've not even considered doing any of this in PHP yet.

[sde]

this must be very very difficult, or i just must be a really crappy php programmer.

i've spent most of today on this and have yet to come up with a solution. i tried to follow techno's very well explained tutorial. i can get each category into it's own object, but i keep getting stuck at the same place i did before. that place is when i have to sort all this data after the objects are created. with php, creating an object for each category is probably not necessary.

i think i'm just going to build a system that has a fixed amount of tables. 5-10 will be enough for my applications.

i am now officially throwing in the towel. . . way too much time has been spent on this.

thanks everyone for all the help anyhow

[abc123]

i haven't read most of whats been said up there, but you are having trouble getting multiple hierarchies out of your object or set?

i wouldn't use a "for" loop but a while

//in java
public static void start()
{
  //get the query
  //$result=mysql_query("select cat_id,cat_name from heirarchy where cat_id=parent_id"); 

}

public static void processNewCat(String catID)
{
   cat_id = catID;
   while(cat_id != null)
   {
      processNewCat(cat_id);
    }
}

erm
anyway, that doesn't mean much up there, i can't really write it in this thing (i need textpad) but you need a function that calls itself for each node and gets nodes from that node and calls itself based on them each time until the node == null then you've reached the end of a category

e.g
People
- Men
- Boys
- Blonde haired boys

people finds men, which calls the same function again for boys etc etc etc

i hope you understand this, if not im sure sdeming or techno will explain it further.. i know what im talking about.

[sdeming]

Nicely put abc! He's nailed it with a nice example.