SQL Trees
Date: Sat, 05 Jun 2004 10:17:02 -0700
Message-ID: <ppnwc.4$_a1.87_at_news.oracle.com>
Ilia Kantor wrote:
>Dear Sir,
>
>I've read a few articles of yours devoted to SQL trees.
>And I belive there are no other materials with such in-depth study of the
>topic.
>
>Howether there are doubtful points in effectiveness of such methods.
>
>======================================================
>The first point is about exponential growth of nested intervals, that
>was 'fixed' using Farey series.
>Theoretically speaking, the core of the problem remained, because
there still exists
>a sequence of insertions leading to exponential growth of denominator.
>It is formed using a simple rule: "take nodes with maximal
>denominators and insert a circle between them".
>
>'Bad' tree shape
> 1/2
> / \
> 3/5 2/3
> / \
>8/13 5/8
> /
> ...........
>
>We have Fibonacci sequence of denominators 2,3,5,8,13..
>It can be shown that Fib_n ~ phi^n/sqrt(5)
>where phi represents golden mean.
>
>Finally, we get O(1.6^n) growth instead of 3^n in a simple nested
>interval schema. So the size of 'worst-case tree' is about 4-5 times
>larger for Farey series approach compared to simple approach.
>
>That saves ~2 bits for denominators, but does not solve the problem.
>
>Practically speaking, such tree construction is much less common
>then a linked-list which forms worst case for simple intervals.
>
>But in certain applications it may be intentively formed causing the
>whole construction to fall soon: for 32-bit denominators 80-100 steps
>of such exponential growth is enough.
>
>That leads to reindexing problem.
>
>Do you have ideas/articles on this point?
The idea that you can find a tree shape that overflows a particular encoding schema is not surprising at all. After all, number of nodes in any tree is growing exponentially with the level, so that whatever coding one choses, the opponent can point out a strategy for overflowing this encoding.
The article http://arxiv.org/abs/cs.DB/0402051 shows connection between Materialized path encoding and Farey/Continued Fractions/Moebius transformations/Orthogonal 2x2 matrices. Therefore, if we overflow Materialized path encoding, then we overflow the others too. And the easiest way to overflow Materialized path encoding is: 1
1.1 1.1.1 1.1.1.1
The continued fraction
1+1/(1+1/(1+...
is the Golden Mean, no wonder it appears in your asymptotic complexity estimation formula.
All that is required is mapping this path into Farey/Continued Fractions/Moebius transformations/Orthogonal 2x2 matrices
In Matrix language, the above sequence is
Matrix(2,2,[[1,1],[1,0]]) Matrix(2,2,[[2,1],[1,1]]) Matrix(2,2,[[3,2],[2,1]]) Matrix(2,2,[[5,3],[3,2]]) Matrix(2,2,[[8,5],[5,3]])
where it's indeed obvious, that it's growing as a Fibonacci sequence.
Although overflow problem was helpful by triggering this new interval
encoding schema, I don't think is very interesting at this point. If I
were making a list of problems, then it would be:
1. Finding tree encodings is easy. Is there a "nonvolatile" encoding for
graphs?
2. In Farey/Continued Fractions/Moebius transformations/Orthogonal 2x2
matrices encoding why determinants are alternating with each level? Well
(duh!), the determinant of primitive one level matrix is -1, so,
multiplying these we'll get alternation. Then, why determinant of one
level matrix is -1?
Received on Sat Jun 05 2004 - 19:17:02 CEST