Retrieving data with a hierarchical structure in MySQL

Question

Given the following table

id    parentID   name      image
0     0                    default.jpg
1     0          Jason   
2     1          Beth      b.jpg
3     0          Layla     l.jpg
4     2          Hal     
5     4          Ben       

I am wanting to do the following:

If I search for Ben, I would like to find the image, if there is no image, I would like to find the parent's image, if that does not exist, I would like to go to the grandparent's image... up until we hit the default image.

What is the most efficient way to do this? I know SQL isn't really designed for hierarchical values, but this is what I need to do.

Cheers!

Answer 1

MySQL lacks recursive queries, which are part of standard SQL. Many other brands of database support this feature, including PostgreSQL (see http://www.postgresql.org/docs/8.4/static/queries-with.html).

There are several techniques for handling hierarchical data in MySQL.

• Simplest would be to add a column to note the hierarchy that a given photo belongs to. Then you can search for the photos that belong to the same hierarchy, fetch them all back to your application and figure out the ones you need there. This is slightly wasteful in terms of bandwidth, requires you to write more application code, and it's not good if your trees have many nodes.

There are also a few clever techniques to store hierarchical data so you can query them:

• Path Enumeration stores the list of ancestors with each node. For instance, photo 5 in your example would store "0-2-4-5". You can search for ancestors by searching for nodes whose path concatenated with "%" is a match for 5's path with a LIKE predicate.

• Nested Sets is a complex but clever technique popularized by Joe Celko in his articles and his book "Trees and Hierarchical in SQL for Smarties." There are numerous online blogs and articles about it too. It's easy to query trees, but hard to query immediate children or parents and hard to insert or delete nodes.

• Closure Table involves storing every ancestor/descendant relationship in a separate table. It's easy to query trees, easy to insert and delete, and easy to query immediate parents or children if you add a pathlength column.

You can see more information comparing these methods in my presentation Practical Object-Oriented Models in SQL or my upcoming book SQL Antipatterns Volume 1: Avoiding the Pitfalls of Database Programming.

Answer 2

Perhaps Managing Hierarchical Data in MySQL helps.