Re: Hierarchcal Task Lists

stu wrote:
>Has anybody seen or designed a DB for tasks where 1 task can have any number
>of sub tasks using the relational model? Could Celkos Nested Set be used
>for this? Or is there a simple way?

The most important question is if the nesting depth is bounded or not. So can you have subtasks, subsubtasks, subsubsubtasks, et cetera. If there is no limit or the limit is large then you should start thinking about special constructs for representing hierarchical data. In that case there are roughly 4 approaches and which one is best depends upon how your data typically looks and what your acces patterns are, i.e., what the typical queries and updates look like and how often they are done.

The 4 approaches are:

• The adjacency list approach: in some relation you store which child has which parent. Simple and straightforward, cheap to update, especially when you do things like moving subtrees, but some typical hierarchical queries cannot be expressed in one SQL query and require some iteration in the programming language in which the SQL is embedded.
• The transitive closure approach: in a relation you store the ancestor-descendant relationship, which is the transitive closure of the parent-child relationship. The transitive closure can ben maintained quite easily for small updates, but the relation can get much bigger than the parent-child relation.
• The nested sets approach: you introduce a numbering scheme that allows you to express hierarchical queries very efficiently by comparing numbers. Is simple if you understand it, but can sometimes be a bit expensive you have a lot of updates.
• The path approach: you store with every node in the hierarchy the path of identifers that you encounter if you walk to it from the top of the hierarchy. Very similar to paths in file systems where "/a/b/c" identifies a file. Many hierarchial queries then can be done with efficient string matching.

Take your pick.

• Jan Hidders