Monday, December 17, 2007

Calculating Hierarchical Roll-ups: The Adjacency List Model

I've worked on a couple of projects where the requirements involved calculating a part of an organization chart. There are a number of ways to do this with standard SQL, with the help of database-specific solutions like "CONNECT BY" in Oracle or recursive queries in SQL Server 2005, but in general I think the adjacency list model is a good approach.

For example, take a look at this organizational structure for this
fictional 6 person software start-up

CEO: Joseé Roarke
---CIO: Maria Gandalfino
------Director: Product Development Alex Cohen
---------Developer: Peter Chin
---------Developer: Jake Murphy
---------Developer: Catherine McLaren

Here's what the data would look like in a table in a database:
EmployeeIDTitleNameBossID
2052CEOJoseé RoarkeNULL
2053CIOMaria Gandalfino2052
2054DirectorAlex Cohen2053
2055DeveloperPeter Chin2054
2056DeveloperJake Murphy2054
2057DeveloperCatherine McLaren2054

In the adjacency list model, the data is transformed so that the
parent and child (boss and employee) data is stored in the same row.

Boss's BossBossEmployee
Joseé RoarkeMaria GandalfinoAlex Cohen
Maria GandalfinoAlex CohenPeter Chin
Maria GandalfinoAlex CohenJake Murphy
Maria GandalfinoAlex CohenCatherine McLaren

This way, with a bit of SQL, any structure in a hierarchy can be
calculated. This can be combined with other parameters like date
ranges, geographical regions to create dynamic reports.

3 comments:

  1. tricky stuff, but nice when you can get it to work - We use this for our corporate directory

    ReplyDelete
  2. thanks - good consise overview of a tough concept.

    ReplyDelete
  3. the wikipedia article on this is better than it used to be

    http://en.wikipedia.org/wiki/Adjacency_list

    ReplyDelete