Re: message board thread quandary

[clinton]

shmem's approach is right, and will work very well for smaller sites, but I would say that, for larger sites, you should consider adding a separate table which records all of these relationships. For instance, for:

    blog 1
    - reply 2
      - reply 4
      - reply 5
        - reply 6
    - reply 3
      - reply 7

you could maintain a table like:

      ancestor_id    descendant_id
      ----------------------------
          1              2
          1              3
          1              4
          1              5
          1              6
          1              7
          2              4
          2              5
          2              6
          3              7
          5              6

This would allow you to say: give me all the descendants of blog 1, or of reply 2. It has its own complications in that you're maintaining a separate table, and so need to keep the two in sync.

There are numerous patterns for expressing hierarchies, and the most effective one depends on the depth of your trees and how often that data changes. Have a look at Trees in SQL, adjacency lists and sorting. for a discussion of some of these. Also, look for anything by Joe Celko, author of Joe Celko's Trees and Hierarchies in SQL for Smarties, for example, his article Trees in SQL.

Clint

[shmem]

Why a separate table? This just complicates things, and to build the hierarchy out of the bunch of descendants of blog 1 you still need multiple selects.

[clinton]

It is one way to do it. With the approach you suggested, it means going through this process:
1. fetch an entry
2. find any children
3. for each child, call step 1
This requires multiple calls to the DB, which is likely to be slower than issuing one single call to find all descendants. The process of sending the query to the DB, having the DB parse the SQL, run the query, return the results, and parsing the results has to happen many more times (depending on the nature of your data) than with the structure I suggested.

It, too, is not without its problems though. For instance, keeping the two tables in sync can be tricky. The Nested Set Model of Trees describes a way to do it in a single table, and it is very fast for reads. But inserting a node into the tree can involve a large number of updates, so, depending on your data, it may not be applicable.

I think that there is no perfect solution - each one has its pros and cons, and has to be considered in the context of the type of data (and use of that data) that you have.

Clint

[shmem]

Your comparison is incomplete.

It is one way to do it. With the approach you suggested, it means going through this process:

1. fetch an entry
2. find any children
3. for each child, call step 1

And with an additional table, the steps are?

1. fetch an entry
2. fetch all descendants of that entry (gives a collection)
3. build a tree doing ... what exactly? Probably a select to get its immediate parent.

There. :-)

update - having read the Nested Set Model of Trees - well, that's one way to do it. You have to jump through hoops still to get your data into a tree structure suitable to be displayed in a TT template. But anyways, trading simplicity and additional database calls for just one call (which I doubt would satisfy the OP's requirements) and more code complexity is something I would do only if I had proven the fact that multiple queries are the bottleneck in that application.

update 2: Thinking about it, building a tree given the parent_id in each record would probably be pretty simple, so there's no point discussing your improvement.

cheers,