> In my particular exploration of this topic, I do, indeed have all four
> elements of a 2x2 matrix stored
Then, applying the extended Euclidean algorithm is unambiguous, right?
The sigmod paper p.4 illustrates how to expand the matrix by adding
more columns. The algorithm stops as soon as we add column [0,1].
> -- and the right column is the continued
> fraction of the node's parent; so I don't think the properties of adjacency
> list are particular to Farey fractions.
I'm not sure I understand your comment. Sure the left column [3,4] of
the child
[3 5]
[4 7]
refers to the right column of the parent
[2 3]
[3 4]
In this sense it is similar to adjacency list. The difference, of
course, is that in matrix encoding we have a very strict policy what
values are admitted, and in adjacency list you can label tree nodes by
anything.
Tegiri Nenashi - 03 Jul 2008 23:58 GMT
> [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).