Newsgroups: comp.databases.theory From: Lennart Jonsson References: <3ad9cbbf$1@news.kommunicera.umea.se> <3adf4543$1@news.kommunicera.umea.se> Subject: Re: pointers on representing tree in db? Lines: 42 Message-ID: X-Abuse-Info: When contacting newsranger.com regarding abuse please X-Abuse-Info: forward the entire news article including headers or X-Abuse-Info: else we will not be able to process your request X-Complaints-To: abuse@newsranger.com NNTP-Posting-Date: Mon, 23 Apr 2001 07:55:11 EDT Organization: http://www.newsranger.com Date: Mon, 23 Apr 2001 11:55:11 GMT In article , 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