If you deal with relational database systems on any semi-regular basis, you’ve probably had to support hierarchical data sets before. In genealogical terms, each record may have a logical “parent” record and zero or more “child” records. The approach that you’ve likely taken to support these data sets has been to include a foreign key column in the table in question that references the primary key column in the same table. This approach is called the adjacency list model, where the name is taken from the same concept in graph theory. This model is simple and intuitive, but it has a drawback: to obtain any significant portion of the hierarchy stored in a table can take up to as many queries as there are levels of depth in the hierarchy.
There is an alternative approach, called the nested set model, which finds its basis in set theory. Its development is credited to a man by the name of Joe Celko, who’s written a number of books related to SQL and database design. The basis of the approach is this: each record has numerical left and right bounds that represent the boundaries of a set, where everything within that set is a descendant of that record. By employing some simple joins, most of the subsets of data commonly desired in a hierarchical data set can be retrieved with a single query, which is much more efficient in terms of the number of queries required to fulfill an individual request.
I found out about the nested set model through Elizabeth Smith, one of my fellow developers on the Forkr project. One of my tasks while working on the project was to adapt information from various resources, including code she’d written to implement a combined adjacency list/nested set model approach on a PostgreSQL database, to a component for Forkr to support hierarchical data sets. Why a combined approach? There are several reasons why that is actually better than each individual approach by itself.
- Some of its common queries, mostly those involving only two levels worth of data (i.e. a parent and its children), are more simple and efficient in the adjacency list model than in the nested set model.
- Most sites that support hierarchical data sets already use the adjacency list model, so roughly half the work of implementing a combined approach is already done.
- The adjacency list model is fairly easy to understand and, when effectively laid side-by-side with the nested set model, makes it somewhat easier to follow when looking at data that uses a combined approach.
- When developing an application that uses the nested set model, the logic which controls the bound values for each record can be error-prone early in development. By also maintaining a foreign key column that points back to the parent, the bound values can easily be regenerated at any time.
My work in Forkr is still very much in an alpha stage, but once it’s completed I’ll likely post another blog entry on this topic that outlines how to implement the nested set model with specific SQL examples. So, keep your eyes peeled for it.
Update: Wow… apparently I unknowingly struck a nerve. :P The earlier comments are correct in that manipulating nested set bounds does indeed require updates on many records of a table. The extra speed in retrieving the hierarchy has to come from somewhere, right? The nested set model is admittedly better for instances where the tree isn’t likely to change often or have multiple potential points of modification that can run concurrently. My apologies for not making that clear earlier on.