Re: yet another hierarchy model

Vadim Tropashko wrote:
>
> Is there a document where all the known representations of tree in relational
> database enumerated? I know only those that pop up on this newsgroup (J.Celko's
> method, materialized path, that's all:-(
>
> Here is one more way to represent hierarchy: just store depth-first sequence
> number and level (simple, indeed!).

[snipped example 1]

> 2. To find out all the nodes in a subtree, we find a next node on the same level
> and the next node on the parent level, choose the closest of the two and, then,
> select all the nodes between the given node and the chosen one.

One minor correction:
You choose the closet of the nodes at any level <= the same, since there is no requirement that a node is somewhere followed by a node at the same or the parent level without any lower parent level inbetween.

> For node #4 we pick up nodes 8 and 10, and select every node between 4 and 8
> (exclusive).

[snipped examples]

I think this approach is somewhat simular to Celko's nested set: Your approach: strictly ascending depth-first sequence number (seqNr) + level Celko: strictly ascending depth-first sequence number (with gaps!!) (left) + end of set (right)

Some tasks are easier with one of these models. Some would even be easier with a combination.
I think best would be a combination of both: left, right, level

From the examples given:

1. Find the parent node: Tropashko: select max(seqNr) where seqNr < currSeqNr and level = currLevel - 1 Celko: select max(left) where left < currLeft and right > currRight Combination: select left where left < currLeft and right > currRight and level = currLevel - 1
2. Find out all nodes in a subtree: Tropashko: select * where seqNr > currSeqNr and seqNr < (select max(seqNr) where seqNr > currSeqNr and level <= currLevel) Celko: select * where left > currLeft and right < currRight Combination: use Celko
3. Find all direct children of a parent: Tropashko: select * where seqNr > currSeqNr and seqNr < (select max(seqNr) where seqNr > currSeqNr and level <= currLevel) and level = level + 1 Celko: select * from outer where left > currLeft and right < currRight and not exist (select * where left > currLeft and right < currRight and left < outer.left and right > outer.right) Combination: select * from outer where left > currLeft and right < currRight and level = level + 1
4. Find a path to the root: Tropashko: can't think of a single SQL right now Celko: select * where left < currleft and right > currRight order by left Combination: use Celko

As you can see, some queries benefit from the existance of level, some benefit from the strict definition of the subtree.

Regards,
Heinz Received on Mon Oct 15 2001 - 01:45:33 CDT