Re: pointers on representing tree in db?

In article <u7zodbrfm7.fsf_at_sol6.ebi.ac.uk>, Philip Lijnzaad says... [...]
>>>
>>> what is Data.parent_id for ?
>
>Lennart> Each row in the Datatable represent a treenode. parent_id is a
>Lennart> reference to another row which acts as a parent for the current
>Lennart> one.
>
>why ? this information is already in the Ancestor table. So what is the
>difference between Data.parent_id and Ancestor.ancestor_id ? Is this a
>deliberate denormalization or a typo ?
>

More of denormalisation then. From a client point of view you dont want to retrieve the entire tree. Often I'm just interested in the next level (expanding the tree one level). This can be done by asking the Data table (I agree that this is a stupid name, but I started using it so I'll continue) for each row where I am parent_id.

If Ancestor should fulfill that, it would have to include some kind of ordering number as well (which I assume would make moving around things in the tree more complex).

Another aproach would be to remove the id - parentid row from Ancestor, thus keeping all ancestors but parent there. This would however make queries like "look for all Data that fulfills condition x in my subtree" more complicated.

>The way you present it, make you think that Data is just data on the nodes
>per se, not on the tree topology.
>

Sorry for beeing fuzzy. DataNode would perhaps have been better

[...]
>
>this depends a bit on how you define tree. As mentioned earlier, the above
>approach (termed 'adjacency list' by Celko) is very bad at dealing with trees
>as sets of nodes; all you get is one tree node, or perhaps a few nodes that
>have a fixed number (usually 1, and at great expense more) of levels between
>the parent and the children. Displaying stuff with this approach requires
>several roundtrips to the database, which is hardly elegant, and in the case
>of huge trees (we're dealing with trees of > 100,000 nodes, 10 or 12 levels
>deep), simply too slow.
>
>Lennart> Major drawback is that the ancestor table
>Lennart> grows quite fast for large trees.
>
>why? How else can you store the tree topology in minimal space ? I don't
>think you can minimize this any more (even Celko's nested set approach takes
>an extra id)
>

I grows big since adding a node at level x means adding (x-1) rows in the ancestor table. Whether one can minimize it or not is an open issue.

[...]
>
>Please do; it's very nifty, and the news posting I reposted should be enough
>to get the thing working. (The detailed description in his book tells you all
>the delete and update statements using standard SQL queries that seem not
>very practical to me). Cheers,
>

I will.

/Lennart, who finally found a newsserver where one can both read and post :-) Received on Sat Apr 21 2001 - 10:26:48 CEST