SQL Query for an Organization Chart?

Question

Hello all,

I feel that this is likely a common problem, but from my google searching I can't find a solution quite as specific to my problem.

I have a list of Organizations (table) in my database and I need to be able to run queries based on their hierarchy. For example, if you query the highest Organization, I would want to return the Id's of all the Organizations listed under that Organization. Further, if I query an organization sort of mid-range, I want only the Organization Id's listed under that Organization.

What is the best way to a) set up the database schema and b) query? I want to only have to send the topmost Organization Id and then get the Id's under that Organization.

I think that makes sense, but I can clarify if necessary.

Much appreciated,

-Matt

Answer 1

You could have an Organization have an id PK and a parent FK reference to the id. Then for the query, use (if your database backend supports them) recursive queries, aka Common Table Expressions.

Answer 2

The easy way is to have a ParentID column, which is a foreign key to the ID column in the same table, NULL for root nodes. But this method has some drawbacks.

Nested sets are an efficient way to store trees in an relational database.

Answer 3

One simple way is to store the organization's parentage in a text field, like:

SALES-EUROPE-NORTH

To search for every sales organization, you can query on SALES-%. For each European sales org, query on SALES-EUROPE-%.

If you rename an organization, take care to update its child organizations as well.

This keeps it simple, without recursion, at the cost of some flexibility.

Answer 4

As promised in my comment, I dug up an article on how to store hierarchies in a database that allows constant-time retrieval of arbitrary subtrees. I think it will suit your needs much better than the answer currently marked as accepted, both in ease of use and speed of access. I could swear I saw this same concept on wikipedia originally, but I can't find it now. It's apparently called a "modified preorder tree traversal". The gist of it is you number each node in the tree twice, while doing a depth-first traversal, once on the way down, and once on the way back up (i.e. when you're unrolling the stack, in a recursive implementation). This means that the children of a given node have all their numbers in between the two numbers of that node. Throw an index on those columns and you've got really fast lookups. I'm sure that's a terrible explanation, so read the article, which goes into more depth and includes pictures.