Recursive structure in SQL
In my current project I have to store a hierarchical structure into an SQL database.
I use OpenJPA 2.x as JPA implementation.
The structure is :
- A drawing root, as the name implies, hold the root of the structure;
- A drawing, which is attached to the drawing root, and is the main drawing. The root has only one drawing attached to it;
- Subdrawings, attached to a drawing. They can have subdrawings as well, forming the recursive structure
- Any subdrawing can be attached to more than one parent drawing and can be present in more than one drawing root structure
The last point is important since it adds extra information that we have to store into the database.
Some notes :
- I use DTO’s in the presentation layer, so there’s no problem in having a different representation in the database layer and in the former layer.
- I use separate service and DAO layers
It’s worth to mention that although I’ve kept things slightly simple in this example, in reality there are plenty of other informations linked to each (sub)drawing.
The naive solution
At first - and I must say it’s the current, and thus flawy, solution - I’ve implemented this the naive way, that is, with a foreign key from a drawing to its parent
The drawing root
Of course, since you cannot do JOINS with an unknown depth in SQL, the ORM fetches all drawings one at a time, highly inefficient then.
The real solution
A better solution consists of a table holding foreign key to the drawing roots, the drawings, as well as the parent of each drawings. Furthermore, we add the position - which is important in my context.
So basically we fetch all instances of DrawingHierarchy thanks to a DrawingRoot and then we assemble them in the service layer, looking at the drawing parent (which is NULL for the subdrawing of the DrawingRoot only) and the position.
It works pretty well but has better read performance than write, because each time a DrawingRoot is saved, I have to delete all records having a reference to it and then save all drawings, performing a tree traversal.
Do you have some optimizations to this kind of problem ?