DB Design: best practices to hierarchical structure.

Question

I'll try to expose as clear as possible ;)

Well, i need to store some data that can be linket to themselves as the parent > child relationship, with no-limit deep.

My first try was:

entry_id | parent_id | value
    1    |   NULL    | Foo //foo is the grand parent
    2    |    1      | Bar //bar is child of Foo
    3    |    1      | Baz //baz too
    4    |    2      | Bho //bho is child of Bar
    5    |    4      | Som //som is child of Bho
    6    |   NULL    | Git //another grand parent
    7    |    6      | Tim //Git's child

..and so on.

This structure works, but its is impossible (or at least, i couldnt go throught) find all the Foo childs and 'sub-childs' with just 1 query.. this need a loop.

My goal is to have a structure optimized for SELECT query, that can give me all the relationships in one shot, something like:

 SELECT "ALL SONS OF Bar"

output:

  entry_id | parent_id | value
     1     |   NULL    |  Bar
     4     |    2      |  Bho
     5     |    4      |  Som

but this structure doesnt seem to let me do that.

Any idea?

If can matter, i'll run on Postgresql (i thought to use array fields type, but the query wont be much fast)

Edit for the philip comment: in my specific, the data shouldnt change too often, but i'll probably need to use this structure for other tasks similar -but not equal- where the data can be updated many many times.

As a side note, using foreign keys (or a similar behavior) will be the best (deleting one 'father' should delete all the childs - no orphans are allowed)

Answer 1

I think you would benefit from reading this text from MySQL: http://dev.mysql.com/tech-resources/articles/hierarchical-data.html It tells how to turn a flat table into a hierarchy with just a couple of attributes and some housekeeping. Even if you're not going to go that way, it's insightful.

For PostgreSQL you can do it with WITH RECURSIVE queries: http://www.postgresql.org/docs/8.4/static/queries-with.html You need at least version 8.4 to use them.

Answer 2

Bill Karwin has made a nice slideshow about hierarchical data:

http://www.slideshare.net/billkarwin/models-for-hierarchical-data

And as jmz already said, the recursive queries are a real problem solver.