This is a very typical situation when you have a hierarchical data structure of the type like forum posts or comments:
Let’s store it in a relational database (e.g. MySQL). For this we need to create a table:
id int PRIMARY KEY,
comment text,
parent_id int,
FOREIGN KEY (parent_id) REFERENCES Comment(id)
);
And you need to show it in a tree view, e.g.:
/Comment#2 (Reply to Comment#1)
/Comment#4 (Reply to Comment#1)
/Comment#8 (Reply to Comment#4)
/Comment#7 (Reply to Comment#1)
/Comment#3
/Comment#5
/Comment#6 (Reply to Comment#5)
/Comment#9 (Reply to Comment#6)
You can see that comments added in an arbitrary order (by looking at the comment id sequence).
So how are you going to select all the data to build the tree by SQL means? Standard SQL does not provide hierarchical select feature (like Oracle’s CONNECT BY). One would probably end up doing multiple queries, which sounds like a very inefficient thing to do (imagine fetching a 10-level depth tree of 1000 comments). Fortunately, there is a better idea. I would say even more: a solution with one simple select query! 
Excited? It’s very simple, actually.
The idea is to construct a select statement which will return results sorted in an order we need (say, in the tree above each node is a row in the query result set). On the other hand it is very similar to the structure of directories and files in the filesystem. So, we will use a property of files here, which is the path. When creating a new Comment instance we will set its path, and update when setting a parent Comment:
String path;
…
Comment(long id) {
this.id = id;
this.path = "/" + id;
}
void setParent(Comment parent) {
this.parent = parent;
this.path = (parent == null ? "" : parent.path) + "/" + id;
}
}
If we apply this transformation to the example above the data in the table will look like:
————————————-
1 NULL /1
2 1 /1/2
3 NULL /3
4 1 /1/4
5 NULL /5
6 5 /5/6
7 1 /1/7
8 4 /1/4/8
9 6 /5/6/9
Now we can use the path field to retrieve our comments ordered accordingly. By executing
we will get this:
————————————-
1 NULL /1
2 1 /1/2
4 1 /1/4
8 4 /1/4/8
7 1 /1/7
3 NULL /3
5 NULL /5
6 5 /5/6
9 6 /5/6/9
The rest is only a matter of formatting the results in order to get nicely looking comments tree output. (Note: the level can be computed as a number of slashes, ‘/’, in the path string).
Also, when using ORM like Hibernate (or JPA in general), you are not forced to use SQL and can get your job done with simple criteria-based or HQL queries.
As a free bonus, you get pagination working properly without extra tweaking as you would have to do in case of multiple queries.
P.S. One piece that is missing in the above example is that the sorting for strings based on numbers will be done in the alphabetical order, e.g. 11 will appear before 2 (which is obviously not what we want). So to fix this problem you can prefix each part of the path with a length of the numbers in characters. It will result in smth like: 12, 211 (or 1.2, 2.11)…
Tags: hierarchical query, sql
