Storing hierarchical data in a database: Part 1

(Click to see part 2a and 2b)
In this first of two (or three) posts, I’m going to present a fairly conventional way of representing hierarchical data in a database. (The original article I read that got me interested on posting these ideas can be found here, hence the similarity in the tree structure).

My DB of choice is MySQL, so you may have to modify your queries slightly for other DB engines.

Before we even begin, we should consider why we’d even want to do something like that – what can you even use it for? Animals. It’s something we can all relate to. If, for some reason, you needed to catalog the relationships of different animals to one another, you’d have to come-up with some sort of tree diagram to make sense of it all. Take a look at this one, for example:

What else can you say about it? Pretty simple. I particularly like fish, so I expanded a little bit there (later we’ll see how we can expand our tree to include different breeds of dogs and cats). Also notice that you can really create many different types of trees. One tree that I’m working on, for example, will demonstrate the taxonomic relationships between different species of fish for the DFL. Often times the employee/supervisor scheme is used for demonstration purposes.

The first method of storing our data is by simply indicating to which parent does each item belongs. Take a look at this table:

[table: animal_tree]
| id  | parent_id   | name        
|-------------------------------   
| 1   |  0          | Animals         
| 2   |  1          | Fish           
| 3   |  1          | Mammals   
| 4   |  2          | Marine       
| 5   |  2          | Fresh Water
| 6   |  4          | Halibut       
| 7   |  5          | Rainbow Trout
| 8   |  3          | Dog          
| 9   |  3          | Cat           
|---------------------------------

*Note: I chose to have parent=0 to mean that’s the top-level of our tree (there is no row id 0).

That wasn’t too painless, now was it? The parent_id column basically points to the node (location in the tree) to which that particular item belongs. For example, cat (id 9) has a parent_id 3, which is the id of “Mammal.” Using this information we can reconstruct the tree above (it probably won’t look quite like that, but the structure of the data is what we’re concerned with).

There’s essentially only one basic query we need to achieve our goals:
$query="SELECT * FROM animal_tree where parent_id=$id";
Easy, huh? but it doesn’t really do anything for us. Say we wanted to select Animals->Fish->Marine->all, how would we do that?

 SELECT * FROM animal_tree where parent_id=0 (selects Animals)
 SELECT * FROM animal_tree where parent_id=1 (selects Fish)
 SELECT * FROM animal_tree where parent_id=2 (selects Marine)
 SELECT * FROM animal_tree where parent_id=4 (selects all who's parent is "Marine")

In order to make this a bit more automated, since that’s really what we’re trying to do, we need to make use of a recursive function. What is that? you may ask… Well, it’s essentially a function that, at some point, calls itself from within. Here’s a quick example:

function recursive_add($number) {
    $number++;
    echo $number.", ";
    if($number==100) {
        die("All done!");
    }
    else {
        recursive_add($number);
    }
}

recursive_add(0);
//will print 1, 2, 3, 4, 5, ..., 100

This function keeps calling itself until $number equals 100, at which point it kills the script, telling us we’re all done. If we’re going to create a recursive function for our tree, we’re going to need a few modifications to our code first…

function build_tree($parent_id=0,$depth=0) {
    //run our query. by default starts at top of 
    //the tree (with zero depth)
    $result=mysql_query("SELECT * FROM animal_tree "
                                   ."WHERE parent=$parent_id");

    //display each child row
    while($row=mysql_fetch_assoc($result) {
        //indent as necessary and print name
        print str_repeat('....',$level).$row['name']."n";

        //we want to see all the children that belong to this 
        //node... so we need to call *this* function again
       build_tree($row['id'],$level++);
    }
}

That wasn’t too painless, now was it? If this still seems a little to difficult or abstract, don’t worry. Recursive function seem exactly that when you first learn them.

If you ever wanted to find the path to “Halibut,” you can create a similar function that find the parent_id of “halibut”, run the function to find the parent’s parent, so on and so forth.

…enjoy.