Re: Nested interval tree encoding

On Jul 3, 3:31 pm, Tegiri Nenashi <TegiriNena..._at_gmail.com> wrote: > [3 5]
> [4 7]

To expand it a little more, considering the above matrix what fraction 3/4 or 5/7 we choose as tree encoding? I suggest that thinking of tree node encoded by a single fraction is a wrong idea. The node is encoded by the interval [3/4,5/7). But then we have this inconvenience of the intervals changing orientation every time we go one level up in the tree. Changing orientation is not really a show stopper, but one have to be careful when writing nesting interval condition in SQL queries.

The crux of the problem is the alternating matrix determinant. Dan's solution is to interleave materialized path with 1's so that

3.4.5

becomes something like

3.1.4.1.5.1

Dan's approach is essentially matrix encoding with atomic matrices of the kind

[n + 1 n]
[ ]
[ 1 1]

Each atomic matrix has determinant equal to one, therefore we see that even if we multiply them, the determinant are not alternating, and nested interval orientation does not change when we ascend to the next tree level. Each Dan’s atomic matrix is a product of the familiar atomic matrix

[n 1]
[ ]
[1 1]

with an auxiliary matrix

[1 1]
[ ]
[1 0]

This is why Dan’s continued fractions contain interleaving sequences of 1s.

An alternative to Dan's approach is suggested in chapter 5 of "SQL design patterns" book. The atomic matrices of the kind

[n + 1 -1]
[ ]
[ 1 0]

also always have determinant 1. One more encoding with this property is hinted in the book exercises:

[n + 1 i]
[ ]
[ i 0]

This was perhaps an attempt to keep the determinant property, and also be able to organize matrices into the number wall which was lost for the

[n + 1 -1]
[ ]
[ 1 0]

encoding. (Not that there is a compelling practical reason to insist on number wall property). Received on Fri Jul 04 2008 - 00:58:09 CEST