Re: matrix encoding IS adjacency list

vc wrote:
> Vadim Tropashko wrote:
> > As it has been written elsewhere, Nested Intervals gradually evolved
> > into matrix encoding. To summarize, each node of a tree is encoded with
> > 4 integers, which translates into the following schema design:
> >
> > table MatrixTreeNodes (
> > a11 integer,
> > a12 integer,
> > a21 integer,
> > a22 integer
> > );
> >
> > As the title of the message says, there is adjacency list relation
> > hidden there!
>
>
>
> It's not surprising since you maintain a sort of materialized path in
> every node containing pairs (parent, child), So given a path 1.2.3.4,
> in order to access the fifth sibling just use 1.2.3.5, that's all.
> Much simpler than the matrix encoding.

I don't follow. In adjacency relation there is an explicit foreign key constraint from child_id to parent_id. Where do you see this constraint with materialized path encoding? In other words, given parent node materialized path encoding, how do I find all the (immediate) children? Trivial with adjacency list.

Referring to the problem of (a11,a21) being not unique, I actually figured it out. There are exactly 2 nodes with the same (a11,a21). This follows from the equation

a11*a22-a21*a12 = 1 or -1

It is possible to amend matrix encoding in such a way that determinant of [[a11,a12],[a21,a22]] matrix is always 1. Then, (a11,a21) is unique, and we can decare foreing key constraint. Matrix encoding IS adjacency list! Received on Tue Sep 20 2005 - 00:22:14 CEST