Storing and Displaying Hierarchical Data

Submitted by Jeff Howden,[e-mail]

Storing and displaying hierarchical data often called a tree is not a simple task, but it often is an unfortunate necessity to show the relationship between sets of data. The most common type you'll find is probably nested categories with parent/child relationships for products.

If you've ever worked with hierarchical data before, you know it's not a simple task. There are a number of ways to store the data, but most of them seem to put a lot of extra burden on the ColdFusion Server to retrieve and display for the user in its entirety. If you've never worked with hierarchical data, don't worry; you'll run up against it sooner or later. I'm going to show you what I believe is the simplest way, from a web-based perspective, to store this type of data to make displaying it as efficient as possible.

The important thing on the web is to think about what actions that can be taken against the data will be performed the most and try to structure your data to make the most common action the least hit on the database and the ColdFusion user. If you've guessed that the most common thing you'll do is retrieve data from the database and display it, give yourself 10 points. If you said that adding new data or updating the data is the most common, deduct 10 points.

To make the data as simple as possible to retrieve and display, we'll need to store a couple of small tidbits about each record: parent_id, tree_level, and rank. (see Table 28.3).

Table 28.3. The Three Columns That Make This Approach Work

Parent_id	This is a foreign key that tells us what record in the table the current record is a child of.
Tree_level	This is a number that represents how many positions the record is indented.
Rank	This is a number that represents the current record's placement among all the other records, without regard for what's a parent or child of what.

Let's take a look at some sample data. The hierarchical data in Table 28.4 represents a guessing game. I only show three levels of nesting, but this method could handle as many levels as you want. Along with the three columns previously detailed, we'll also need two additional columns at a minimum: id (the primary key column) and name. You can store additional information if the situation warrants.

Table 28.4. The Raw Data We'll Be Using for This Example from a Table Named game

Id	Name	Parent_Id	Tree_Level	Rank
1	Guessing Game	0	1	1
2	Animal	1	2	2
3	Elephant	2	3	3
4	Aardvark	2	3	4
5	Lemur	2	3	5
6	Mineral	1	2	6
7	Titanium	6	3	7
8	Gold	6	3	8
9	Carbon	6	3	9
10	Vegetable	1	2	10
11	Broccoli	10	3	11
12	Spinach	10	3	12
13	Cauliflower	10	3	13

The simplest thing you can do is query for all child records that are one level in and that match an id that's passed in the URL or by a form post.

 <cfparam name="url.parent_id" default="0">  <cfquery name="getchildren">    SELECT id         , name      FROM game     WHERE parent_id = #Val(url.parent_id)#  </cfquery> 

This would be used in the classic drill-down approach you see often on the web. However, you usually need to be able to display more of the tree at a time. So, let's see how to retrieve the entire tree and display it to the user.

 <cfquery name="gettree">    SELECT name         , tree_level      FROM game     ORDER BY rank  </cfquery> 

To display the results, all we need to is use a simple CFOUTPUT and pad the left side of each record with the appropriate amount of space to indicate a relationship between the records.

 <cfoutput query="gettree">  #RepeatString("&nbsp;&nbsp;", tree_level - 1)##name#<br>  </cfoutput> 

The preceding code results in the following output:

 Guessing Game    Animal      Elephant      Aardvark      Lemur    Mineral      Titanium      Gold      Carbon    Vegetable      Broccoli      Spinach      Cauliflower 

What if you want to grab an entire branch of the tree, including the parent record based on a parent_id that was passed via the query string? All you'd need to do is use the following query. The two subselects keep the database from returning records with a rank and tree_level less than or equal to the selected record. This guarantees that you're only selecting those records that belong to the branch (provided you've taken precautions that the data is all correct in the three integral columns: parent_id, tree_level, and rank).

 <cfquery name="gettree">    SELECT name         , tree_level      FROM game     WHERE id = #Val(url.parent_id)#        OR (rank > (SELECT rank                      FROM game                     WHERE id = #Val(url.parent_id)#)        AND tree_level > (SELECT tree_level                            FROM game                           WHERE id = #Val(url.parent_id)#))     ORDER BY rank  </cfquery> 

Assuming the value 2 was passed to this query and we're using the simple CFOUTPUT code sample from earlier, here's what the server would return:

 Animal    Elephant    Aardvark    Lemur 

There are other ways in which you'll need to query the data to get things like a record's parent record, all the sibling records for a given record, and so on, but I'll leave that for you to figure out. (It's not as tough as it looks. I promise.)

I'll warn you right now, though, that this method of storing the data does not solve the problems of adding new records and updating existing records. You'll still need to come up with ways to move things around and maintain the proper parent_id, tree_level, and rank values. The solutions to these problems can be difficult to solve, but the burdens on the server are few and far between. Thankfully, using this method, you'll be reducing the load on the server for the action that's taken most often, thereby making your application much better performing for the end user.