Re: Questions about Nested Intervals by Vadim Tropashko one more time

From: Vadim Tropashko <vadimtro_at_yho.cm>
Date: Mon, 01 Dec 2003 15:08:56 -0800
Message-ID: <LZPyb.32$Na6.195_at_news.oracle.com>


Alexander,

Thank you for the reference
(http://www.scenic-route.com/program/db/lists3.htm)

As of today, I don't think Nested Intervals have any advantage over Materialized Path method. They are mathematically equivalent,

  N PATH NUMER/DENOM

  1   .1      3/2
  2   .1.1    7/4
  3   .2      3/4
  4   .1.1.1  15/8
  5   .1.2    11/8
  6   .2.1    7/8
  7   .3      3/8
  8   .1.1.1.1  31/16
  9   .1.1.2  27/16
  10  .1.2.1  23/16
  11  .1.3    19/16
  12  .2.1.1  15/16
  13  .2.2    11/16
  14  .3.1    7/16
  15  .4      3/16
  16  .1.1.1.1.1   63/32

and, in fact, PATH encoding for each node between N=2^(k-1), and N=2^k-1 is an ordered partition (http://www.math.ksu.edu/~jasonr/book4.pdf) of integer k.

These 2 methods, however, are still very different from implementational perspective: you have ~4000 characters to store each node for materialized path compared to several dozens bytes for integers. If you would like to create a user-defined domain of integers with unlimited precision, the amount of work would be probably no less than just plain string parsing routines for materialized path.

Here is BTW new article
http://dbazine.com/tropashko5.shtml
but, yet again, don't take this implementation literally.

alexzar_nospam_at_zorranlabs.com wrote:
> Hello everybody,
>
> I would like to touch Nested Intervals by Vadim Tropashko one more time.
> It seems to me that it is the best implementation of storing Trees in SQL,
> and I want to implement few functions based on Vadim's algorithm:
>
> 1) Insert new node under ANY other node, such as insert new node "p" under
> x.z.y.k.d to get the whole path to new node as x.z.y.k.d.p
> 2) Move ANY node in the tree under another node, such as for the two
> branches x.z.y.k.d.p.k.t and x.w.f.g.i, move branch y.k.d.p.k.t under node
> f, to get x.w.f.y.k.d.p.k.t
>
> For the 1), I tried to use sample code from "More pain and suffering with
> Tropashko's materialized path..." thread,
> http://dbforums.com/arch/57/2003/9/917999, and sample and formulas,
> http://www.scenic-route.com/program/db/lists3.htm to calculate Numerator
>
> CREATE FUNCTION dbo.Calculate_Numerator
> ( _at_numer INTEGER, @child INTEGER )
> RETURNS INTEGER
> AS
> BEGIN
> RETURN _at_numer * POWER ( 2, @child ) + 3 - POWER ( 2, @child )
> END
>
> It seems to me that Denominator depends only of _at_child, so
> Calculate_Denominator looks this:
>
> CREATE FUNCTION dbo.Calculate_Denominator
> ( _at_child INTEGER )
> RETURNS INTEGER
> AS
> BEGIN
> RETURN POWER ( 2, _at_child )
> END
>
> Now, I am trying to test it against the sample
> http://www.scenic-route.com/program/db/lists3.htm, Tropashko Nested
> Intervals:
>
> Category Path Numer Denom
> a__ .1 3 2
> | b__ .1.1 7 4
> | e .1.1.1 15 8
> | f__ .1.1.2 27 16
> | k .1.1.2.1 55 32
> | g .1.1.3 51 32
> | c__ .1.2 11 8
> | h .1.2.1 23 16
> | i .1.2.2 43 32
> | d .1.3 19 16
>
>
> For the node a_, path .1, SELECT dbo.Calculate_Numerator ( 1, 1 ), I get 3
> node a -> b, path .1.1, SELECT dbo.Calculate_Numerator ( 2, 2 ), I get 7
> node a -> b -> e, path .1.1.1, SELECT dbo.Calculate_Numerator ( 3, 3 ), I
> get 19, but it should be 15
>
> Could you explain what is wrong with parameters of calls, and how they
> should be different for .1.1.2.1, and .1.1.3 calls, for example?
> What should be _at_child and @numer for this x.z.y.k for example?
>
> For 2) do you have any ideas about implementation?
>
> Thanks,
> Alex
>
>
> ----- Posted via NewsOne.Net: Free (anonymous) Usenet News via the Web -----
> http://newsone.net/ -- Free reading and anonymous posting to 60,000+ groups
> NewsOne.Net prohibits users from posting spam. If this or other posts
> made through NewsOne.Net violate posting guidelines, email abuse_at_newsone.net
Received on Tue Dec 02 2003 - 00:08:56 CET

Original text of this message