61 views

Skip to first unread message

Mar 29, 2004, 9:24:29 PM3/29/04

to

mko...@aon.at (Manfred Koizar) wrote in message news:<lao7605t695dguk7e...@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.

> 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.

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu