Re: More pain and sufferring with Tropashko's materialized path...

From: Vadim Tropashko <vadimtro_at_yho.cm>
Date: Tue, 11 Nov 2003 09:46:42 -0800
Message-ID: <Dp9sb.20$Up4.46@news.oracle.com>

Mark Johnson wrote:
> vadimtro_invalid_at_yahoo.com (Vadim Tropashko) wrote:
>
>

>>Mark Johnson <102334.12_at_compuserve.com> wrote in message news:<ttasqvgjh5v48p40i6ebhkbpu9n81fg42u_at_4ax.com>...

>
>

>>For balanced trees yes. For unbalanced trees, for instance, tree
>>degrading into a list,

>
>

>>1
>>1.1
>>1.1.1
>>1.1.1.1
>>...

>
>

>>it's still a problem.

>
>
> I don't know if my other message got to your server. But I can see
> that you might still have the problem of geometric expansion. You
> don't need to use the path, at all. But in creating your 'single
> integer key', you seem to retain the binary shifting previously used
> for denom and numer. So 1.1, is twice 1, and 1.1.1, is twice 1.1, and
> so on.

Yes "1.1.1"=4 is twice as large as "1.1"=2. But on the same note 1.1.1 as materialized path encoding is 2 bytes longer than 1.1, which is essentially the same thing: Geometrically increasing number requires linear increase in number storage. No wonder, because, all those codings in the article are natural mappings of materialised path into numbers.

> Am I correct in thinking that 'siblings', list ordering, is
> accomplished by shifting the key from the prevous item, and adding 1
> to it? So that 1.1.2 is the key for 1.1.1 shifted, plus 1?

Yes.

>>Celko's Nested Sets encoding is dense, while Binary Rationals are
>>sparce, indeed. This is the price one have to pay for nonvolatile
>>encoding schema.

>
>
> Don't you have to recalcuate every key in a sub-tree if you relocate
> it? with this single key method.

Yes, I would have to recalculate every key in the subtree, but all the rest of the tree stays untouched. Besides, the recalculation formula is very simple. The idea is the same as in http://www.google.com/groups?hl=en&lr=&ie=UTF-8&oe=UTF-8&selm=Fs58b.22%24927.175%40news.oracle.com

>>>And I wonder, from that trop4 URL, that you suggest an 'adjacency
>>>list' is synonymous with a table of contents, or XML tree, or the
>>>like. That is, is the adjacency model still the description of any
>>>particular XML tree, say for example, even if that is stored as nested
>>>sets for purposes of rapid query and retrieval - assuming some custom
>>>'parser'? I might well misunderstand. But I thought the adjacency
>>>model wasn't based on the tree being a tree, but on how the tree was
>>>represented in a table.

>
>
> That is, did you mean the adjacency model was synonymous with a simple
> table of contents, or outline, or rather that the one-way link-up was
> what is meant by the adjacency model? or something else more general?

I didn't give much thought to terminology, and took whatever term Celko used in his series of articles about Nested Sets. But little research shows that his terminology is justified:

http://mathworld.wolfram.com/AdjacencyMatrix.html http://mathworld.wolfram.com/AdjacencyList.html Received on Tue Nov 11 2003 - 11:46:42 CST