Hello all,

On Jul 1, 2:05 pm, creecode <creec... (AT) gmail (DOT) com> wrote:

The SQL queries I have so far seem to be working well. I have parent,
descendants, direct descendants, next sibling and previous sibling
queries. The next two queries I need are next and previous nodes.
These queries, given a current node, would return the next or previous
node in the tree if the hierarchy was walked as a flat tree. I hope
that makes sense. With the following data as an example...

name materialized_path a11 a12 a21 a22 idx_left idx_right

KING 1 2 1 1 0 1 2
JONES 1.1 3 2 2 1 1 1.5
SCOTT 1.1.1 4 3 3 2 1 1.33333
ADAMS 1.1.1.1 5 4 4 3 1 1.25
FORD 1.1.2 7 3 5 2 1.33333 1.4
SMITH 1.1.2.1 11 7 8 5 1.33333 1.375
BLAKE 1.2 5 2 3 1 1.5 1.66667
ALLEN 1.2.1 8 5 5 3 1.5 1.6
WARD 1.2.2 13 5 8 3 1.6 1.625
MARTIN 1.2.3 18 5 11 3 1.625 1.63636

Some next examples...

Given KING I would get back JONES.
Given ADAMS I would get back FORD.

And some previous examples...

Given BLAKE I would get back SMITH.
Given MARTIN I would get back WARD.

With a series of next queries I'd be able to walk the hierarchy
like...

KING > JONES > SCOTT > ADAMS > FORD > SMITH > BLAKE > ALLEN > WARD >
MARTIN. And with a series of previous queries I'd be able to do the
reverse...

MARTIN > WARD > ALLEN > etc....

Any help appreciated!

Toodle-loooooooooo.............
creecode

On Aug 15, 3:01*pm, creecode <creec... (AT) gmail (DOT) com> wrote:

The records ordered by idx_left, idx_right desc. I assume you want a
query that when given a node in a hioerarchy fetches the next node
according to the ordering. I found that this query is a mess due to
composite ordering key. Therefore, it makes sence to order the values
by a scalar, something like (a11-a12)/(a21-a22)*10000000000 - a11/a21

Here is the full query:

with OrderedHier as ( select name, (a11-a12)/(a21-a22)*10000000000 -
a11/a21 pos from hierarchy )
SELECT h.name FROM OrderedHier h, OrderedHier node
where node.name = 'BLAKE'
and h.pos > node.pos
and not exists (
SELECT * FROM OrderedHier hh
where h.pos > hh.pos
and hh.pos > node.pos
)
;

fetching ALLEN. (Tested everything between KING and BLAKE)

Hello Vadim,

Sorry for delayed reply.

On Aug 16, 12:52*pm, Vadim Tropashko <vadim... (AT) gmail (DOT) com> wrote:

Excellent! Seems to work great! Thank you so much!

Toodle-loooooooooooooo
creecode

Hello Vadim,

On Aug 16, 12:52 pm, Vadim Tropashko <vadim... (AT) gmail (DOT) com> wrote:

I've run into a snag. It seems the query doesn't work for a larger
data set. There are duplicate values for some of the order
positions. Here is an example...

message_id a11 a12 a21 a22 materialized_path left right level
order_position
6926 6069 253 4054 169 1.1.84.23 1.497039897 1.49703996 3
14970398968.503
7150 11885 6069 7939 4054 1.1.84.23.1 1.497039897 1.497039929 4
14970398968.503
6917 3572 325 2385 217 1.1.108.10 1.497693726 1.49769392 3
14976937258.5023
7244 6819 3572 4553 2385 1.1.108.10.1 1.497693726 1.497693828 4
14976937258.5023
7873 10066 6819 6721 4553 1.1.108.10.1.1 1.497693726 1.497693795 5
14976937258.5023
11301 1692 565 1129 377 1.1.188.2 1.498670212 1.49867139 3
14986702118.5013
11307 2819 1692 1881 1129 1.1.188.2.1 1.498670212 1.498670919 4
14986702118.5013
14655 1523 763 1016 509 1.1.254.1 1.499013806 1.499015748 3
14990138058.501
14677 2283 1523 1523 1016 1.1.254.1.1 1.499013806 1.499015101 4
14990138058.501

Any thoughts on either what I might have done wrong or a query that
will produce unique order position values?

Toodle-looooooooo............
creecode

On Sep 6, 9:42*am, creecode <creec... (AT) gmail (DOT) com> wrote:
select name, (a11-a12)/(a21-a22)*10000000000-a11/a21 pos from hier;
1.1.84.23 14970398968.901930438437591866304249136
1.1.84.23.1 14970398968.9019304695082500851489389089

Hello Vadim,

On Sep 7, 8:47*am, Vadim Tropashko <vadim... (AT) gmail (DOT) com> wrote:

With your example results I've been able to get the order position
query working. Thanks once again for your help and patience! My
original problem with the query was partly due to not using enough
precision. I had experimented with greater precision before asking
for help but obviously I didn't go far enough! :-)

Here is the query I came up with for MySQL v5.0.x for greater
precision...

SELECT name, materialized_path, ( a11 - a12 + 0.00000000000000000 ) /
( a21 - a22 + 0.00000000000000000 ) * ( 10000000000 +
0.00000000000000000 ) - ( a11 + 0.00000000000000000 ) / ( a21 +
0.00000000000000000 ) AS order_position FROM MatrixTreeNodes;

....and the results...

name materialized_path order_position
KING 1 9999999998.000000000000000000000000000000
JONES 1.1 9999999998.500000000000000000000000000000
SCOTT 1.1.1 9999999998.666666666666666666666666666667
ADAMS 1.1.1.1 9999999998.750000000000000000000000000000
FORD 1.1.2 13333333331.933333333333333333333333333333
SMITH 1.1.2.1 13333333331.958333333333333333333333333333
BLAKE 1.2 14999999998.333333333333333333333333333333
ALLEN 1.2.1 14999999998.400000000000000000000000000000
WARD 1.2.2 15999999998.375000000000000000000000000000
MARTIN 1.2.3 16249999998.363636363636363636363636363636

Toodle-looooooooo..............
creecode

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

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!

Toodle-loooooooooo.............
creecode

On Sep 13, 11:39*am, creecode <creec... (AT) gmail (DOT) com> wrote:
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.

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