Hierarchical data in MySQL (and other RDBMS)

Introduction

There are lot of cases we want to store hierarchical data into relational database instead of hierarchical ones like XML databases. Several approaches exist and are already well explained, the most well known are the adjacency list and the nested set models. After briefly introducing those models I will present an extension to the first one making it much more usable. This extension has already been presented by Joe Celko under the name Path enumeration

The adjacency list model

The most common way to store such data is using the adjacency list model as introduced by former IBM fellow Edgar F. Codd (the father of relational database theory):

id	name	boss
1	Anne	NULL
2	Bernard	1
3	Charlie	1
4	Delphine	3
5	Elodie	3
6	Fanny	3
7	Georges	5

Such model respects fully the relational idea based on primary and foreign keys, but this system shows his limit when we have to retrieve the full path to a node: "Anne > Charlie > Elodie > Georges" or when we need all people working below Charlie. Such question typically requires recursion with many queries which may become very slow:

-- Path to Georges?
SELECT * FROM people WHERE id = 7; -- boss = 5
SELECT * FROM people WHERE id = 5; -- boss = 3
SELECT * FROM people WHERE id = 3; -- boss = 1
SELECT * FROM people WHERE id = 1; -- boss = NULL (STOP)

-- People under Charlie?
SELECT * FROM people WHERE boss IN (3); -- id = 4,5,6
SELECT * FROM people WHERE boss IN (4,5,6); -- id = 7
SELECT * FROM people WHERE boss IN (7); -- no results (STOP)


The nested set model

The second popular approach is to make use of the depth first traversal algorithm to assign a left and right number to any node of the tree:

id	name	lft	rgt
1	Anne	1	14
2	Bernard	2	3
3	Charlie	4	13
4	Delphine	5	6
5	Elodie	7	10
6	Fanny	11	12
7	Georges	8	9

This model is algorithmically beautiful! It solves in an elegant way the problem of running multiple queries to retrieve hierarchical information:

-- Path to Georges?
SELECT * FROM people WHERE 8 BETWEEN lft AND rgt ORDER BY lft;

-- People under Charlie?
SELECT * FROM people WHERE lft BETWEEN 4 AND 13 ORDER BY lft;


While this model is very good at retrieving hierarchical information, it is somewhat more complex and less competitive at updating the hierarchy (inserting, moving or removing nodes) since it requires to update several records even if it is feasible in one query. Not to mention that this model is not relational at all and does not prevent through integrity constraints the accidental removal of a boss! However, this is easily circumvented by adding the boss column and then mixing both models.

Path enumeration model

The path enumeration model is based on the adjacency list one, the idea is quite simple: add a column materializing the full path (which is unique) to your node.

id	name	boss	path
1	Anne	NULL	/1/
2	Bernard	1	/1/2/
3	Charlie	1	/1/3/
4	Delphine	3	/1/3/4/
5	Elodie	3	/1/3/5/
6	Fanny	3	/1/3/6/
7	Georges	5	/1/3/5/7/

The path is always computed by taking the path of the parent node concatenated with "<ID>/". Retrieving the path to Georges or people working for Charlie is a kid's game:

-- Path to Georges?
SELECT path FROM people WHERE id = 7; -- path = /1/3/5/7/
SELECT * FROM people WHERE id IN (1,3,5,7) ORDER BY path;

-- People under Charlie?
SELECT * FROM people WHERE path LIKE '/1/3/%' ORDER BY path;


To benefit from all the speed of this solution, you should have a UNIQUE KEY on your path column. Unfortunately it isn't (yet?) possible to know the assigned auto-increment ID inside an insert-trigger using MySQL, it is then mandatory to work in two phases while inserting a record. A first solution is to insert dummy data in the path while taking care of the UNIQUE KEY constraint and then updating the record using LAST_INSERT_ID(). My preference goes to using another table (people_tree) with a 1..1 relation. Here is an example:

-- Adding Helena below Bernard
INSERT INTO people (name, boss) VALUES ('Helena', 2);
INSERT INTO people_tree
SELECT p.id, CONCAT(pt.path, p.id, '/') FROM people p JOIN people_tree pt ON p.boss = pt.id WHERE p.id = LAST_INSERT_ID();

Of course, this complexity may be hidden in a stored procedure.

Related links

• Managing Hierarchical Data in MySQL
• Storing Hierarchical Data in a Database
• Hierarchical SQL