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

mkoi-pg_at_aon.at (Manfred Koizar) wrote in message news:<lao7605t695dguk7ehql7ikcm56rufhc0s_at_email.aon.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. Received on Tue Mar 30 2004 - 04:24:29 CEST