Re: Yet another tree labeling

No, I wouldn't rely on it, especially when being constrained by project schedule. For one thing, this new labeling method works well when traversing hierarchy up. When traversing hierarchy down (for example, aggregated total report), then the subtree is potentially too large to build "in-list" of node labels, but yet small enough for range scan in nested intervals method. Therefore, you would still need to translate to intervals in that case, which renders the method much less useful.

In short, fix the ariphmetics. It's something much more straightforward than inventing new tree labeling method.

As some more goofy alternative you can write parsing functions which would work with materialized path exclusively. For example, the distance function is the difference in the number of dots (or whatever separator token is), assuming that one path is the prefix of the other.

"Robin Tucker" <r.tucker_at_thermoteknix.com> wrote in message news:<bk6p4d$4dg$1$830fa7b3_at_news.demon.co.uk>...
> Excellent. However, as I have project meeting this afternoon to discuss my
> technical specification for our project, I am still not sure whether to
> recommend Materialized Path or Adjacency List - perhaps you could flesh it
> out a little more before then ;) ?
>
> "Vadim Tropashko" <vadimtro_at_yahoo.com> wrote in message
> news:22d2e427.0309151626.116ba0d5_at_posting.google.com...
> > We label each tree node with a single positive integer number. This
> > labeling is closely related to binary rational interval labeling
> > defined in http://www.dbazine.com/tropashko4.html
> >
> > Given natural number N, let k be maximal integer satisfying 2^k <= N.
> > In other words
> >
> > k = floor(log(2,N))
> >
> > We define mapping between binary rational interval labeling (x,y) and
> > N as follows:
> >
> > y+(1-x) = 1 - 1/2^(k+1)
> >
> > 1-x = (N-2^k)/2^k
> >
> > For example, the node "1.4" or <x=9/16, y=17/32> corresponds to N=23.
> >
> > The nice property of single integer labeling is very simple definition
> > of transitive closure relation. Given 2 nodes i and j such that i <= j
> > let k' be maximal integer satisfying i*2^k' <= j. Consider binary
> > relation "le" satisfying
> >
> > i "le" j <=> j-i*2^k' < i*2^(k'-1)/j or i = j.
> >
> > Here is implementation as a distance function
> >
> > CREATE or replace
> > function dist ( child integer, parent integer )
> > RETURN integer IS
> > ret integer;
> > arifgeom integer;
> > pwr integer;
> > BEGIN
> > if parent > child then
> > RETURN -1;
> > end if;
> > if parent = child then
> > RETURN 0;
> > end if;
> > arifgeom := parent;
> > pwr := 0;
> > while arifgeom*2 <= child loop
> > arifgeom := arifgeom*2;
> > pwr := pwr+1;
> > end loop;
> > if child-arifgeom < arifgeom/(parent*2) then
> > RETURN pwr;
> > end if;
> > RETURN -1;
> > END;
> > /
> >
> > select dist(11,3), dist(12,3), dist(13,3), dist(14,3) from dual
> > -1 2 2 -1
> >
> > In other words the function returns distance between parent and child
> > in the tree or -1 if child is not reacheable from parent.
> >
> > I'll submit more readable version to dbazine.com (with pictures!)
Received on Tue Sep 16 2003 - 18:39:01 CEST