Multiple tables in nested sets hierarchy

Question

I have a number of distinct items stored in different MySQL tables, which I'd like to put in a tree hierarchy. Using the adjacency list model, I can add a parent_id field to each table and link the tables using a foreign key relationship.

However, I'd like to use a nested sets/modified preorder tree traversal model. The data will be used in a environment that's heavily biased towards reads, and the kind of queries I expect to run favour this approach.

The problem is that all the information I have on nested sets assumes that you only have one type of item, stored in a single table. The ways round this that I can think of are:

Having multiple foreign key fields in the tree, one for each table/item type.
Storing the name of the item table in the tree structure as well as the item ID.

Both approaches are inelegant to say the least, so is there a better way of doing this?

I can't think of any way to do this other than those you mention. I'd lean towards the second, storing a type discriminator in the tree nodes, then having the item tables refer to the tree nodes. I'd go so far as to use the same primary key for the tree node and the corresponding item, making the PK of the item table also an FK referencing the tree table. This is broadly the approach taken by most object-relational mappers for handling inheritance, FWIW. — Tom Anderson

nawroth nawroth · Accepted Answer · 2009-07-07T16:25:13

RDBMS are not a good match to storing hierarchies to begin with, and your use case makes this even worse. I think a little more fine tuned but still ugly variations of your own suggestions are what you are going to get using a RDBMS. IMHO other data models would provide better solutions to your problem, like graph databases or maybe document databases. The article Should you go Beyond Relational Databases? gives a nice introduction to this kind of stuff.

Multiple tables in nested sets hierarchy

2 Answers