Cameron Perry | Archives

Second part in this series of discussions/tutorials on storing hierarchical data in a database. You can read the first on here. The original article I read that got me started on these ideas can be found here (you’ll notice the tree diagrams are similar). Most credit should be given to Gijs Van Tulder; I simply modified some of his code and added to his explanation where appropriate.

This time we’re going to take a look at the basics of the modified preordered tree traversal algorithm.

Consider the tree used in part 1, which uses the adjacency list model:

[table: animal_tree, adjacency list model]
| 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
|-----+-------------+-------------

What the modified preordered method does is store the relationships between neighboring nodes in order to recreate the tree structure. We do this by storing “lft” and “rght” (“left” and “right” are reserved SQL keywords) values at each node; as you descend a tree, the left-hand values increase, and likewise, as you ascend the right-hand values increase. It’s hard to visualize until you see it in action:

Pay special attention to the sequence in which these nodes are ordered, as shown by the arrows.

Here’s the presorted table for the above tree:

[table: animal_tree, presorted model]
| lft | rght        | name
|-----+-------------+-------------
| 1   |  18         | Animals
| 2   |  11         | Fish
| 12  |  17         | Mammals
| 3   |  6          | Marine
| 7   |  10         | Fresh Water
| 4   |  5          | Halibut
| 8   |  9          | Rainbow Trout
| 13  |  14         | Dog
| 15  |  16         | Cat
|-----+-------------+-------------

…and one of the first things you probably want to do with your new presorted data? Create a tree. First things first, though. The code behind it is more difficult to understand than the adjacency model but the overhead is greatly reduced because you only need two queries for to retrieve tree information from the database (adjacency uses a new query every time you recursively enter the retrieve function).

In its simplest form the queries are:
(retrieves the left and right values for the starting node)
SELECT lft,rght FROM animal_tree WHERE name="$name";
SELECT * FROM animal_tree WHERE lft BETWEEN $row['lft'] AND $row['right'] ORDER BY lft ASC;…and that’s it.

Take a look at the code (modified from the example in the Sitepoint article):

//I use my own database classes, but it should be easy enough to follow what's happening.
function get_tree($name="Animal",&$DB) {

$result=$DB->query("SELECT lft,rght FROM animal_tree WHERE name="$name"");
$row=$DB->fetchRow($result);
$result2=$DB->query("SELECT * FROM animal_tree WHERE lft BETWEEN {$row['lft']} AND {$row['rght']} ORDER BY lft ASC");

$right = array();

$row=$DB->fetchAssoc($result2);

$ii=0; //start counter at 0
foreach($row as $row) {
if(count($right)>0) {

/* $right[max#] is the last array element, which holds the
* rght value from the previous row, which is a parent in
* many cases, but if not a parent, it keeps popping-off
* the last element of the $right array - going back up
* the tree until $row[right] (current node) finds its
* parent (the parents rght value is greater than the
* child's rght)
*/
while($right[count($right)-1]$value)
{
print(str_repeat(' ',$value['indent'])."({$value['lft']})".$value['node']."({$value['right']})n");
}
}


…and in-case you want the path to a particular node:
SELECT * FROM animal_tree WHERE lft$rght ORDER BY lft ASC

..to count the number of descendants: $d=(rght-lft-1)/2

Thanks, again to Gijs for the excellent tutorial. Next time we will explore some ways to modify and manipulate the tree.

(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.