self referencing tables/ nested sets etc...

Skip to first unread message

Vadim Tropashko

Mar 29, 2004, 9:24:29 PM3/29/04
to (Manfred Koizar) wrote in message news:<>...
> BTW, I've read Tropashko's follow-up articles
> 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:
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.
Uses the same Binary Rationals encoding schema solving tree relocation

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 =
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
so that concatenation of paths is substitution of functions, or
alternatively, into 2x2 matrix:
so that concatenation of paths is Matrix multiplication. Example:
corresponds to continued fraction
which corresponds to
All matrices have additional property that absolute value of the
determinant is 1 (Proposition 1). In our case

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.

Reply all
Reply to author
0 new messages