Getting a grip on nested intervals and matrix encoding

External Since: Jul 01, 2010 Posts: 10

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 @a11, @a12, @a21, @a22 FROM
MatrixTreeNodes WHERE name = 'BLAKE';
SELECT a11, a12, a21, a22 INTO @b11, @b12, @b21, @b22 FROM
MatrixTreeNodes WHERE name = 'FORD';

SELECT name, a11, a12, a21, a22, materialized_path,
( @b12 * @a21 - @b11 * @a22 ) * c.a11 + ( @b11 * @a12 - @b12 * @a11 )
* c.a21 AS new_a11,
( @b12 * @a21 - @b11 * @a22 ) * c.a12 + ( @b11 * @a12 - @b12 * @a11 )
* c.a22 AS new_a12,
( @b22 * @a21 - @b21 * @a22 ) * c.a11 + ( @b21 * @a12 - @b22 * @a11 )
* c.a21 AS new_a21,
( @b22 * @a21 - @b21 * @a22 ) * c.a12 + ( @b21 * @a12 - @b22 * @a11 )
* c.a22 AS new_a22
FROM MatrixTreeNodes AS c
WHERE ( @a11 - @a12 ) * ( c.a21 - c.a22 ) <= ( c.a11 - c.a12 ) *
( @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.
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. Smile

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,
( @b12 * @a21 - @b11 * @a22 ) * c.a11 + ( @b11 * @a12 - @b12 * @a11 )
* c.a21 AS new_a11,
( @b12 * @a21 - @b11 * @a22 ) * c.a12 + ( @b11 * @a12 - @b12 * @a11 )
* c.a22 AS new_a12,
( @b22 * @a21 - @b21 * @a22 ) * c.a11 + ( @b21 * @a12 - @b22 * @a11 )
* c.a21 AS new_a21,
( @b22 * @a21 - @b21 * @a22 ) * c.a12 + ( @b21 * @a12 - @b22 * @a11 )
* c.a22 AS new_a22
FROM MatrixTreeNodes AS c
WHERE ( @a11 - @a12 ) * ( c.a21 - c.a22 ) <= ( c.a11 - c.a12 ) *
( @a21 - @a22 ) AND c.a11 * @a21 <= @a11 * c.a21;

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

External Since: Jul 02, 2010 Posts: 6

On Sep 13, 11:39 am, creecode 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 @a11, @a12, @a21, @a22 FROM
> MatrixTreeNodes WHERE name = 'BLAKE';
> SELECT a11, a12, a21, a22 INTO @b11, @b12, @b21, @b22 FROM
> MatrixTreeNodes WHERE name = 'FORD';
>
> SELECT name, a11, a12, a21, a22, materialized_path,
> ( @b12 * @a21 - @b11 * @a22 ) * c.a11 + ( @b11 * @a12 - @b12 * @a11 )
> * c.a21 AS new_a11,
> ( @b12 * @a21 - @b11 * @a22 ) * c.a12 + ( @b11 * @a12 - @b12 * @a11 )
> * c.a22 AS new_a12,
> ( @b22 * @a21 - @b21 * @a22 ) * c.a11 + ( @b21 * @a12 - @b22 * @a11 )
> * c.a21 AS new_a21,
> ( @b22 * @a21 - @b21 * @a22 ) * c.a12 + ( @b21 * @a12 - @b22 * @a11 )
> * c.a22 AS new_a22
> FROM MatrixTreeNodes AS c
> WHERE ( @a11 - @a12 ) * ( c.a21 - c.a22 ) <= ( c.a11 - c.a12 ) *
> ( @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. Smile

>
> 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,
> ( @b12 * @a21 - @b11 * @a22 ) * c.a11 + ( @b11 * @a12 - @b12 * @a11 )
> * c.a21 AS new_a11,
> ( @b12 * @a21 - @b11 * @a22 ) * c.a12 + ( @b11 * @a12 - @b12 * @a11 )
> * c.a22 AS new_a12,
> ( @b22 * @a21 - @b21 * @a22 ) * c.a11 + ( @b21 * @a12 - @b22 * @a11 )
> * c.a21 AS new_a21,
> ( @b22 * @a21 - @b21 * @a22 ) * c.a12 + ( @b21 * @a12 - @b22 * @a11 )
> * c.a22 AS new_a22
> FROM MatrixTreeNodes AS c
> WHERE ( @a11 - @a12 ) * ( c.a21 - c.a22 ) <= ( c.a11 - c.a12 ) *
> ( @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 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