mkoi-pg@aon.at (Manfred Koizar) wrote in message news:<lao7605t695dguk7ehql7ikcm56rufhc0s@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. ---------------------------(end of broadcast)--------------------------- TIP 6: Have you searched our list archives? http://archives.postgresql.org
