As I mentioned in an earlier post, I’m working (slowly) on a web app for my municipality’s Office of Emergency Management. The app is meant to keep track of “first responders” - people who will respond in an emergency situation. This includes the local volunteer fire departments, rescue squad, OEM members, city public works employees, etc. This means that the app is going to have to keep track of hierarchies of people. For the sake of simplicity, let’s call this “departments” and “employees”, even though most folks are volunteers.

The interesting problem to solve here is hierarchical SQL queries. Let’s say someone has the role of Department Admin for the top-level “Fire Department”. Lambertville has several fire departments, which all ultimately are overseen by the city-wide Fire Chief. The Fire Chief may want to see the record of all of the Fire Department staff, city-wide. So, we’d need to be able to query the database for all “employees” in the “Fire Department” department, and all departments that are sub-departments of the “Fire Department” department.

If you search the web, you’ll find all sorts of schemes for solving this problem, including vendor-specific sql extensions in various databases, such as SQL Server’s “Common Table Expression” and Oracle’s “START WITH and CONNECT BY”. But, as usual, I’m looking for a vendor-neutral solution.

Several web sites promote the “adjacency model”, where each row stores a reference to it’s parent. I found the sql queries required with this model to be more trouble than it’s worth.

I came up with an easier model, which I later discovered was thought of by other folks too. The folks at sqlteam.com call this a ‘lineage model’ - seems like a good name, so I’ll use that. I think that my approach goes a little further than theirs, so read on…

The basic idea is to store the entire lineage of each row, rather than just it’s parent id. So, if we have a three-department hierarchy, A -> B -> C, with primary keys 1, 2, and 3 respectively, C’s ‘lineage’ is ‘1|2’. The sqlteam example uses this for sorting purposes, but it is also useful for selecting particular parts of the hierarchy. For example, if I want to see dept A and all of it’s sub-departments, I can use the following sql:

select * from dept where id = 1 or lineage like ‘%1%’;

If I want to see just direct sub-departments of dept A, I can use:

select * from dept where lineage = ‘1’;

The observant reader will notice that this extended use of the lineage model will only work properly with fixed-width keys. You wouldn’t want the ‘like ‘%1%’ where-clause above to match a row with, say, and id of ‘12’. But how to produce fixed-width keys?

I’m using Hibernate in this project, so the obvious answer was to write a new IdentityGenerator subclass. I wrote FixedWidthStringIdGenerator, based on Hibernate’s existing IncrementGenerator.

FixedWidthStringIdGenerator generates ids in the same way as IncrementGenerator, but then base-36 encodes the value (producing digits in the range [0-9][a-z]), and then left-pads the result with zeroes to produce a fixed-width string. When configured to produce ints, the width is 6 chars. Longs produce 13 chars.

This worked out so well that I submitted a patch to the Hibernate project. This is my first-ever contribution to an open-source project. Here’s hoping that they accept it.

Just in case the patch is not accepted, and you’re interested in using it, you can download it here.

Happy Hibernating!