Re: Getting a grip on nested intervals and matrix encoding

On Sep 13, 11:39 am, creecode <creec..._at_gmail.com> wrote:
> Hello all,
>
> I'm onto the relocating tree branches section of the chapter in the
> book.  The query in the book didn't originally work for me and I think
> that was due to the WHERE part of the query not selecting the
> descendants correctly.  I want to verify that my modified query is
> doing what the book intended to show.
>
> So using my previous favorite MatrixTreeNodes...
>
> /* relocate tree branch */
>
> SELECT a11, a12, a21, a22 INTO _at_a11, @a12, @a21, @a22 FROM
> MatrixTreeNodes WHERE name = 'BLAKE';
> SELECT a11, a12, a21, a22 INTO _at_b11, @b12, @b21, @b22 FROM
> MatrixTreeNodes WHERE name = 'FORD';
>
> SELECT name, a11, a12, a21, a22, materialized_path,
>  ( _at_b12 * @a21 - @b11 * @a22 ) * c.a11 + ( @b11 * @a12 - @b12 * @a11 )
> * c.a21 AS new_a11,
>  ( _at_b12 * @a21 - @b11 * @a22 ) * c.a12 + ( @b11 * @a12 - @b12 * @a11 )
> * c.a22 AS new_a12,
>  ( _at_b22 * @a21 - @b21 * @a22 ) * c.a11 + ( @b21 * @a12 - @b22 * @a11 )
> * c.a21 AS new_a21,
>  ( _at_b22 * @a21 - @b21 * @a22 ) * c.a12 + ( @b21 * @a12 - @b22 * @a11 )
> * c.a22 AS new_a22
> FROM MatrixTreeNodes AS c
> WHERE ( _at_a11 - @a12 ) * ( c.a21 - c.a22 ) <= ( c.a11 - c.a12 ) *
> ( _at_a21 - @a22 ) AND c.a11 * @a21 < @a11 * c.a21;
>
> name    a11    a12    a21    a22    materialized_path    new_a11
> new_a12    new_a21    new_a22
> ALLEN    8    5    5    3    1.2.1    11    7    8    5
> WARD    13    5    8    3    1.2.2    18    7    13    5
> MARTIN    18    5    11    3    1.2.3    25    7    18    5
>
> I am a bit unclear from the language in the book if we're dealing with
> moving only the descendants of node A or node A and its descendants.

By "descendants of A" I meant "node A and its descendants". However, matrix algebra is ambivalent about it. Indeed, the node relocation formula

C -> B A^-1 C

can be interpreted with either strict or reflective transitive closure convention. For the root of the branch it's relative position A^-1 C is the identity matrix. Therefore, if we want to move the whole branch including the root node, we'd better clean up the space at the new location, because the root of the branch is going to occupy the exact location of B! But then, even if you move strict descendants only, you still can have descendants of B with encoding colliding with the new encoding of C.

> The text first mentions "Consider a tree branch located at the node
> encoded with matrix A" and then "How would the encoding of some node C
> (which is located in the tree branch under A) change and "-- all the
> descendants of matrix -- [[:a11,:a12][:a21,:a22]]".  I'm leaning
> towards descendants. :-)
>
> Although with a small change the query seems to deal with relocating
> node A and descendants into the place of node B...
>
> SELECT name, a11, a12, a21, a22, materialized_path,
>  ( _at_b12 * @a21 - @b11 * @a22 ) * c.a11 + ( @b11 * @a12 - @b12 * @a11 )
> * c.a21 AS new_a11,
>  ( _at_b12 * @a21 - @b11 * @a22 ) * c.a12 + ( @b11 * @a12 - @b12 * @a11 )
> * c.a22 AS new_a12,
>  ( _at_b22 * @a21 - @b21 * @a22 ) * c.a11 + ( @b21 * @a12 - @b22 * @a11 )
> * c.a21 AS new_a21,
>  ( _at_b22 * @a21 - @b21 * @a22 ) * c.a12 + ( @b21 * @a12 - @b22 * @a11 )
> * c.a22 AS new_a22
> FROM MatrixTreeNodes AS c
> WHERE ( _at_a11 - @a12 ) * ( c.a21 - c.a22 ) <= ( c.a11 - c.a12 ) *
> ( _at_a21 - @a22 ) AND c.a11 * @a21 <= @a11 * c.a21;

Yes, it all depend on the where clause: do you want to move strict descendants or the whole branch.

> name    a11    a12    a21    a22    materialized_path    new_a11
> new_a12    new_a21    new_a22
> BLAKE    5    2    3    1    1.2    7    3    5    2
> ALLEN    8    5    5    3    1.2.1    11    7    8    5
> WARD    13    5    8    3    1.2.2    18    7    13    5
> MARTIN    18    5    11    3    1.2.3    25    7    18    5
>
> Once the relocating query seems to be verified as OK then I'll
> probably ask some questions about how to best go about dealing with
> collisions.
>
> TIA!
>
> > On Jul 1, 2:05 pm, creecode <creec..._at_gmail.com> wrote:
> > I'm attempting to use Vadim Tropashko's nested intervals and matrix
> > encoding technique.  As described in chapter 5 of his "SQL Design
> > Patterns" book and also in various online articles and discussion
> > groups.
>
> Toodle-loooooooooo.............
> creecode
Received on Tue Sep 14 2010 - 04:38:50 CEST