Re: matrix encoding IS adjacency list

"Vadim Tropashko" <vadimtro_invalid_at_yahoo.com> wrote in message news:1127168534.689248.131360_at_g43g2000cwa.googlegroups.com...
>
> 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.

OK, at first you talked about an adjacency list, but no matter. Let a,b,c,d,e be some nodes. Then an adjacency list for some DAG/tree might be a set of pairs:

{(a, {b,c}), (b, {d,e}) or, equivalently, {(a,b), (a,c), (b,d), (b,e)}

 In the RM, an adjacency list is usually emulated by a (child, parent, data) relation with the 'child' attribute being the primary key. One can enforce a referential integrity constraint if need be, but that's although desirable is not required in order to express a hypothetical tree topology.

>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.

It's as trivial with a materialized path: in the above example in order to find all node a.b 's children, just say 'find tuples where prefix(materialized_path) = a.b'.

>
> 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

This actually follows from the fact that a rational number, as a continued fraction, has two encodings (if we are talking about the same thing).

>
> 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!

Of course it is, m.e being a materialized path encoding. You seem to imply that the constraint makes finding, say, all the immediate children somehow easier compared to the constraint-less search. Could you please elaborate ?

>
Received on Tue Sep 20 2005 - 03:06:33 CEST