Oracle FAQ Your Portal to the Oracle Knowledge Grid
HOME | ASK QUESTION | ADD INFO | SEARCH | E-MAIL US
 

Home -> Community -> Usenet -> comp.databases.theory -> Re: pointers on representing tree in db?

Re: pointers on representing tree in db?

From: Lennart Jonsson <lennart_at_kommunicera.umea.se>
Date: Mon, 23 Apr 2001 11:55:11 GMT
Message-ID: <zKUE6.1724$QV4.134204@www.newsranger.com>

In article <u7vgnwq6kr.fsf_at_sol6.ebi.ac.uk>, Philip Lijnzaad says... [...]
>
>Ah ... now I'm starting to get it; does the ancestor table contain, for each
>node, _all_ ancestors (not just the direct parent) up to the top? (Ancestors
>is the transitive closure of Data, in other words)? That is interesting, if
>expensive, much too expensive too my liking ... I think I would only keep an
>explicit transitive closure for complicated general graphs, not for trees.
>
>Sorry for not getting this earlier ...
>

well, I dont think my explanation where that good so you are excused :-)

[...]
>
>well, not so open: Celko's nesting set representation does really minimize
>this. The trick is that you use the ordering of the natural numbers to
>describe subtrees implicitly, rather than explicitly using a complete
>explicit description using the ancestors tables.
>
>To me it is now clear that the solution you presented is really very wrong
>(sorry to be so adamant ...).

No problem.

>Celko's nested set representation (with the
>addition of direct parent_id, which in a sense is a denormalization) gives
>you this and more (ordering of the direct children, easy detection of leaf
>nodes) for far less.

I agree that Celko's method is more powerfull, yet requires less space. On the other hand adding and moving nodes (including subtrees) requires somewhat more work in his method (I think, havent actually tried it yet).

Anyhow, initially I posted to get pointers to information on how to represent trees in a db (since I had no idea on how this is usually done). I certanly did. Thanks to everyone.

/Lennart Received on Mon Apr 23 2001 - 06:55:11 CDT

Original text of this message

HOME | ASK QUESTION | ADD INFO | SEARCH | E-MAIL US