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.

Join the Conversation

8 Comments

  1. Actually i am working with nested tree. I like the solution, but there is a problem, when i want to display the tree. I cant display as above figure which is shown in example. can anyone help me?

  2. If you’re looking to display the figure as it’s shown above from query results, I don’t know of any simple solution to do that (and I’ve searched before!). The Visualization Toolkit (VTK) has tree mapping functions in its API but that’s much too far from the scope of this blog. The above figures were made using Adobe Illustrator: boxes and lines. The adjacency model works fine and is very common, but make sure to take a look at the Modified Preorder Tree Traversal (MPTT) method in the two posts following this one, Here, and Here

  3. I have tested ur code but the output of this code is
    AnimalFishMarineHalibut….Fresh WaterRainbow Trout….MammalsDog….Cat
    I got a code to display the tree like this,

    * Animal
    o Fish
    + Mrine
    + Fresh Water
    # Halibut
    # Rainbow
    o Mammals
    + Dog
    + Cat

    but i dont understand how i establish this function in case of database.

    will u help me.

  4. Ah… I just noticed a couple little typos in the code:

    function build_tree($parent_id=0,$level=0)
    {
    //run our query. by default starts at top of
    //the tree (with zero depth)
    $result=mysql_query(“SELECT * FROM animal_tree WHERE parent_id=$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+1);

    }

    }
    But I didn’t have a problem with the order of the elements in the tree as you stated.

    The way you would insert a node into the database is by simply creating an INSERT query with the parent_id set to the id of the parent node. For example, you could insert a horse into Mammals with:
    INSERT INTO `animal_tree` ( `parent_id`, `name`) VALUES ('3', 'horse'). You can either rely on the order in which these data are inserted to determine their relative orders in the tree, or better add a sort_order column by which you can assign values so the nodes appear in the order you want them to.

  5. thanks forthis man, but…
    i follwed the instruction i get a result like this…

    Animals
    Fish
    Marine
    Halibut
    ….Fresh Water
    Rainbow Trout
    ….Mammals
    Dog
    ….Cat

    it’s kinda irellevant to what i’d like to show..

Leave a comment

Hey there! Come check out all-new content at my new mistercameron.com!