Re: Hierarchcal Task Lists
From: Lennart Jonsson <lelle2_at_bonetmail.com>
Date: Sat, 16 Nov 2002 00:10:53 +0100
Message-ID: <ar3usp$f6odu$1_at_ID-167942.news.dfncis.de>
>
> 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
Date: Sat, 16 Nov 2002 00:10:53 +0100
Message-ID: <ar3usp$f6odu$1_at_ID-167942.news.dfncis.de>
On Thu, 14 Nov 2002 13:40:50 +0100, Jan Hidders wrote:
> 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
Jans explanation is about it (as usual I might add :-). However, there is another possability worth mentioning. Some db vendors (DB2, Oracle for example), provide recursion which may be used for hierarcical queries. At least for DB2 (I'm sure there are for other vendors as well, I just dont know) there are a couple of examples which you could have a look at. See for example:
http://www7b.boulder.ibm.com/dmdd/library/techarticle/0203venigalla/0203venigalla.html
/Lennart Received on Sat Nov 16 2002 - 00:10:53 CET