Re: self referencing tables/ nested sets etc...

mkoi-pg(at)aon(dot)at (Manfred Koizar) wrote in message news:<lao7605t695dguk7ehql7ikcm56rufhc0s(at)email(dot)aon(dot)at>...
> BTW, I've read Tropashko's follow-up articles
> http://arxiv.org/html/cs.DB/0401014, http://arxiv.org/pdf/cs.DB/0402051,
> as well as various discussions on comp.databases.theory. My conclusion
> is that OMPM is irreparably broken. With every kludge added to it
> (Farey Intervals, Continued Fractions) the correspondence to
> materialized path strings gets even more obfuscated, but the main
> shortcoming remains: If you try to store materialized path information
> in a fixed number of integers you run out of bits very soon.

The article series
Binary Fractions (dbazine) -> Farey Fractions -> Continued Fractions

might give you wrong impression that it's one kludge upon another. In
reality it's just a trail of discovery process. Let me summarize what
I think withstanded the test of time:

http://www.dbazine.com/tropashko4.shtml
The idea of generalizing nested integers to nested fractions is still
valid, although the particular encoding schema with Binary Rationals
proved to be not practical.

http://www.dbazine.com/tropashko5.shtml
Uses the same Binary Rationals encoding schema solving tree relocation
problem.

Farey Fractions
Different encoding schema, that still is waiting somebody to refute
it. Unlike previous articles I did some volume testing there.

Continued Fractions
That is just a different perspective into essentially the same
encoding. Now the connection to Materialized Path is transparent:
whenever you concatenate paths in path encoding, for example
11.2 + 7.3.5 = 11.2.7.3.5
you nest continued fractions
x=7+1/(3+...) inside 11+1/(2+1/x) to get 11+1/(2+1/(7+...))
Technically, this could be done much easier than nesting continued
fractions. The encoding is just four integer numbers <a,b,c,d> that
can be arranged either into Moebius function
(ax+c)/(bx+d)
so that concatenation of paths is substitution of functions, or
alternatively, into 2x2 matrix:
Matrix([a,c],[b,d])
so that concatenation of paths is Matrix multiplication. Example:
path
3.1.1.9.9.9.12.31.24.500.17.4.39
corresponds to continued fraction
3+1/(1+1/(1+1/(9+1/(9+1/(9+1/(12+1/(31+1/(24+1/(500+1/(17+1/(4+1/39)))))))))));
which corresponds to
Matrix([68075613118554,1734570625891],[19306670376781,491935096655])
All matrices have additional property that absolute value of the
determinant is 1 (Proposition 1). In our case
68075613118554*491935096655-1734570625891*19306670376781=1

In short, I'm taking back my previous accessment that for all
practical purposes Materialized Path is the best encoding. Continued
Fractions/Moebius transformations/2x2 Matrices are much nicer IMO. But
this totally depends upon how comfortable are you with math.