Re: Hierachical structures - an overview

"Mike MacSween" <mike.macsween.nospam_at_btinternet.com> wrote in message news:<3ff7e63a$0$52881$5a6aecb4_at_news.aaisp.net.uk>...
> I have an app I need a hierachical structure for. There seem to be 3 ways of
> implementing this, as far as I can see:
>

[...]

>
> 1a. Adjacency list + as per:
> http://fungus.teststation.com/~jon/treehandling/TreeHandling.htm
> Not sure about this. It claims to give the path upwards. It looks like it
> merely gives the ancestors, which isn't the same thing.
>

In what way does this differ? Are you meaning that the set of ancestors is unordered, compared to the path? In that case the path is easy to create from the ancestor set.

It is also possible to create a total ordering of a subtree and thereby do, for example an inorder traversal. However, this becomes impractical for relatively small subtrees since the total ordering is prox O(n^2) (where n is the cardinality of the ancestor relation for the subtree)

> Any other techniques?
>

Recursive SQL. It is supported by atleast two databases, DB2 (WITH) and Oracle (CONNECT BY).

+ You dont have to change anything in the way data is represented (assuming adj. ,list)

• Performance (I have tried it far to little to claim this, but this is my impression so far)

Also, IMO the syntax/semantics is a bit weird (compared to other languages, I've encountered)

[...]

Kind regards
/Lennart Received on Sun Jan 04 2004 - 16:38:59 CET