Getting a grip on nested intervals and matrix encoding
creecode
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.
I thought I was making some progress but I ran into a snag when I
tried a descendants query. In the book there is some confusion
( printing errors or typos ) which I found some corrections for on
Vadim's weblog < http://vadimtropashko.wordpress.com/%E2%80%9Csql-design-patterns%E2%80%9D-book/errata/
>. So I don't know if I've run into an error in the book or I've made
an error somewhere along the line. The later is more likely! :-)
Math is not my strong point so the heavy ( to me ) math explanations
don't work well for me. I do better with step by step examples that I
can tinker with. I realize that the book is "not suitable for
beginners" but I'm forging ahead trying to get some working routines
figured out.
I have a good sized discussion group in a database table that has over
243,000 entries. If I can get Vadim's technique working I'd like to
try and apply it to my discussion group.
What I have so far could be all wrong so hopefully folks can set me in
the right direction.
I'm using MySQL v5.0.45. Here is what I have so far...
/* create table */
CREATE TABLE `MatrixTreeNodes` (
`name` varchar(32) default NULL,
`materialized_path` varchar(32) default NULL,
`a11` int(11) default NULL,
`a12` int(11) default NULL,
`a21` int(11) default NULL,
`a22` int(11) default NULL,
UNIQUE KEY `uk_node` (`a11`,`a21`),
KEY `fk_adjacency` (`a12`,`a22`)
) ENGINE=MyISAM DEFAULT CHARSET=utf8;
** The materialized_path column is for reference only. I don't plan
to use a materialized path column in my final table. **
/* create insert node procedure */
DELIMITER //
CREATE PROCEDURE insert_node ( IN parent_name VARCHAR ( 32 ), IN
child_name VARCHAR ( 32 ), child_materialized_path VARCHAR ( 32 ) )
BEGIN
SELECT a11, a12, a21, a22 INTO @parent_a11, @parent_a12,
@parent_a21, @parent_a22 FROM MatrixTreeNodes WHERE name =
parent_name;
SELECT CASE WHEN COUNT( * ) = 0 THEN 0 ELSE MAX( FLOOR( a11 /
a12 ) ) END + 1 FROM MatrixTreeNodes WHERE a12 = @parent_a11 AND a22 =
@parent_a21 INTO @N;
INSERT INTO MatrixTreeNodes ( name, materialized_path, a11,
a12, a21, a22 ) VALUES ( child_name, child_materialized_path,
@parent_a11 * ( @N + 1 ) - @parent_a12, @parent_a11, @parent_a21 *
( @N + 1 ) - @parent_a22, @parent_a21 );
END;
//
DELIMITER ;
/* initialize the table with root node */
INSERT INTO `MatrixTreeNodes`
(`name`,`materialized_path`,`a11`,`a12`,`a21`,`a22`) VALUES
('KING','1','2','1','1','0');
** This could be my first big problem. Did I use the wrong numbers
for the root node? **
Now lets do some inserts to fill in the table...
/* insert JONES */
CALL insert_node ( 'KING', 'JONES', '1.1' );
/* insert SCOTT */
CALL insert_node ( 'JONES', 'SCOTT', '1.1.1' );
/* insert ADAMS */
CALL insert_node ( 'SCOTT', 'ADAMS', '1.1.1.1' );
/* insert FORD */
CALL insert_node ( 'JONES', 'FORD', '1.1.2' );
/* insert SMITH */
CALL insert_node ( 'FORD', 'SMITH', '1.1.2.1' );
/* insert BLAKE */
CALL insert_node ( 'KING', 'BLAKE', '1.2' );
/* insert ALLEN */
CALL insert_node ( 'BLAKE', 'ALLEN', '1.2.1' );
/* insert WARD */
CALL insert_node ( 'BLAKE', 'WARD', '1.2.2' );
/* insert MARTIN */
CALL insert_node ( 'BLAKE', 'MARTIN', '1.2.3' );
/* select the data */
SELECT * FROM MatrixTreeNodes;
And we get back...
name materialized_path a11 a12 a21 a22
KING 1 2 1 1 0
JONES 1.1 3 2 2 1
SCOTT 1.1.1 4 3 3 2
ADAMS 1.1.1.1 5 4 4 3
FORD 1.1.2 7 3 5 2
SMITH 1.1.2.1 11 7 8 5
BLAKE 1.2 5 2 3 1
ALLEN 1.2.1 8 5 5 3
WARD 1.2.2 13 5 8 3
MARTIN 1.2.3 18 5 11 3
** Hopefully the formatting doesn't get too messed up. If it does I
could follow up with a CSV version. **
Now let's try some direct descendant queries...
/* direct descendants JONES */
SELECT child.name FROM MatrixTreeNodes AS parent, MatrixTreeNodes AS
child WHERE parent.name = 'JONES' AND child.a12 = parent.a11 AND
child.a22 = parent.a21;
name
SCOTT
FORD
/* direct descendants BLAKE */
SELECT child.name FROM MatrixTreeNodes AS parent, MatrixTreeNodes AS
child WHERE parent.name = 'BLAKE' AND child.a12 = parent.a11 AND
child.a22 = parent.a21;
name
ALLEN
WARD
MARTIN
/* direct descendants ADAMS */
SELECT child.name FROM MatrixTreeNodes AS parent, MatrixTreeNodes AS
child WHERE parent.name = 'ADAMS' AND child.a12 = parent.a11 AND
child.a22 = parent.a21;
** no results, as expected **
/* direct descendants KING */
SELECT child.name FROM MatrixTreeNodes AS parent, MatrixTreeNodes AS
child WHERE parent.name = 'KING' AND child.a12 = parent.a11 AND
child.a22 = parent.a21;
name
JONES
BLAKE
Those queries seem to have gone well. Now lets try some parent
queries.
/* parent JONES */
SELECT parent.name FROM MatrixTreeNodes AS parent, MatrixTreeNodes AS
child WHERE child.name = 'JONES' AND child.a12 = parent.a11 AND
child.a22 = parent.a21;
name
KING
/* parent KING */
SELECT parent.name FROM MatrixTreeNodes AS parent, MatrixTreeNodes AS
child WHERE child.name = 'KING' AND child.a12 = parent.a11 AND
child.a22 = parent.a21;
** no results, as expected **
/* parent BLAKE */
SELECT parent.name FROM MatrixTreeNodes AS parent, MatrixTreeNodes AS
child WHERE child.name = 'BLAKE' AND child.a12 = parent.a11 AND
child.a22 = parent.a21;
name
KING
/* parent MARTIN */
SELECT parent.name FROM MatrixTreeNodes AS parent, MatrixTreeNodes AS
child WHERE child.name = 'MARTIN' AND child.a12 = parent.a11 AND
child.a22 = parent.a21;
name
BLAKE
Those seem to have gone OK as well. Now let's try that pesky
descendants query...
/* descendants JONES */
SELECT descendant.name FROM MatrixTreeNodes AS descendant,
MatrixTreeNodes AS node WHERE descendant.a11 * node.a21 >=
descendant.a21 * node.a11 AND descendant.a11 * node.a22 >=
descendant.a21 * node.a12 AND node.name = 'JONES';
name
KING
** that isn't right **
So I tried a version from the comment section of above errata page
that Vadim made.
SELECT descendant.name FROM MatrixTreeNodes descendant,
MatrixTreeNodes node
WHERE descendant.a11 * node.a21 >= descendant.a21 * node.a11
AND descendant.a11 * node.a21 - descendant.a11 * node.a22 <=
node.a11 * descendant.a21 - node.a12 * descendant.a21
AND node.name = 'JONES';
** no results, that isn't right **
Any help much appreciated!
Toodle-loooooooo..........
creecode
Tegiri Nenashi
> Hello all,
>
> 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.
>
> I thought I was making some progress but I ran into a snag when I
> tried a descendants query. In the book there is some confusion
> ( printing errors or typos ) which I found some corrections for on
create table hierarchy (
name varchar2(10),
a11 integer,
a12 integer,
a21 integer,
a22 integer
);
insert into hierarchy values ('KING', 2, 1, 1, 0);
insert into hierarchy values('JONES', 3, 2, 2, 1);
insert into hierarchy values('SCOTT', 4, 3, 3, 2);
insert into hierarchy values('ADAMS', 5, 4, 4, 3);
insert into hierarchy values('FORD', 7, 3, 5, 2);
insert into hierarchy values('SMITH', 11, 7, 8, 5);
insert into hierarchy values('BLAKE', 5, 2, 3, 1);
insert into hierarchy values('ALLEN', 8, 5, 5, 3);
insert into hierarchy values('WARD', 13, 5, 8, 3);
insert into hierarchy values('MARTIN', 18, 5, 11, 3);
commit;
select descendant.name
from hierarchy node, hierarchy descendant
where node.name = 'JONES'
and descendant.a11*node.a21-descendant.a11*node.a22 >=
node.a11*descendant.a21-node.a12*descendant.a21
and descendant.a11 * node.a21 <= descendant.a21 * node.a11;
NAME
----------
JONES
SCOTT
ADAMS
FORD
SMITH
creecode
> select descendant.name
> from hierarchy node, hierarchy descendant
> where node.name = 'JONES'
> and descendant.a11*node.a21-descendant.a11*node.a22 >=
> node.a11*descendant.a21-node.a12*descendant.a21
> and descendant.a11 * node.a21 <= descendant.a21 * node.a11;
Hello Tegiri,
Thank you for your response. Unfortunately your query doesn't work
for me. Perhaps I've made an error somewhere.
SELECT descendant.name FROM MatrixTreeNodes AS descendant,
MatrixTreeNodes AS node WHERE descendant.a11 * node.a21 -
descendant.a11 * node.a22 >=
node.a11 * descendant.a21 - node.a12 * descendant.a21 AND
descendant.a11 * node.a21 <= descendant.a21 * node.a11 AND node.name =
'FORD';
name
SCOTT
FORD
SMITH
** that isn't right **
Toodle-loooooooooo.............
creecode
Vadim Tropashko
creecode
> http://vadimtropashko.wordpress.com/2010/07/03/more-errata-ancestor-q...
Hello Vadim,
Thank you so much for the updated query. It seems to work fine!
Have a blast on the 4TH!
Toodle-loooooooooo.............
creecode
creecode
> 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.
Hello again,
I'm now onto the ancestors portion of the chapter starting on page 177
and the formula for calculating ancestor matrices seems to work OK
except for the the root node. Is the root node a special case that I
should detect and then just insert it manually?
Let's use our friend FORD from my MatrixTreeNodes table shown
previously and run the formula.
name materialized_path a11 a12 a21 a22
FORD 1.1.2 7 3 5 2
SELECT 3 AS a11, 3 - MOD ( 7, 3 ) AS a12, 2 AS a21, 2 - MOD ( 5, 2 )
AS a22;
a11 a12 a21 a22
3 2 2 1
SELECT 2 AS a11, 2 - MOD ( 3, 2 ) AS a12, 1 AS a21, 1 - MOD ( 2, 1 )
AS a22;
a11 a12 a21 a22
2 1 1 1
** that isn't what we want **
Toodle-loooooooo..........
creecode
Vadim Tropashko
select MOD(2,1) from dual;
MOD(2,1)
----------------------
0
Fire your database vendor:-)
creecode
> > SELECT 2 AS a11, 2 - MOD ( 3, 2 ) AS a12, 1 AS a21, 1 - MOD ( 2, 1 )
> > AS a22;
>
> > a11 a12 a21 a22
> > 2 1 1 1
> select MOD(2,1) from dual;
> MOD(2,1)
> ----------------------
> 0
Hello Vadim,
In MySql...
SELECT MOD ( 2, 1 );
MOD ( 2, 1 )
----------------
0
So MOD works OK.
My question was about the calculation of the last node in the ancestor
chain...
SELECT 2 AS a11, 2 - MOD ( 3, 2 ) AS a12, 1 AS a21, 1 - MOD ( 2, 1 )
AS a22;
a11 a12 a21 a22
--------------------------------
2 1 1 1
SELECT 1 - MOD ( 2, 1 );
1 - MOD ( 2, 1 )
---------------------
1
Since I want zero and not one for a22 of the root node I am assuming I
need to special case the root node in my loop.
I'm not clear whether the formula in your book was intended to
calculate the root node matrix or not.
I'm just looking for validation that my assumption is correct and that
I haven't screwed up somewhere.
Thank you,
Toodle-loooooooooooooo.................
creecode
Vadim Tropashko
Oops. Actually, your question is buried in the discussion on the
Errata page:
#
David Brusowankin Says:
November 8, 2007 at 4:46 am e
On page 179: finding the parent of
[7 -2]
[ ]
[4 -1]
1 – mod (4, 1) = 1 – 0 = 1
Not 0 so the root matrix is not obtained.
Is the root a special case somehow ?
Thanks,
David
Reply
#
Vadim Tropashko Says:
November 8, 2007 at 10:08 pm e
Consider the matrix equation from the top of page 178 adapted to the
matrix from your example
[2..x]…[n.-1]…[7.-2]
[....].*.[....].=.[....]
[1..y]…[1..0]…[4.-1]
(dots are used as spacers). Due to matrix multiplication law, the 3
unknowns x,y and n should satisfy the following equations:
2n + x = 7
n + y = 4
It is a system of two equations with three variable that we are
solving, and modulo function is just a handy tool. In the first
equation the n is multiplied by a number greater than 1. There is no
ambiguity, and we get a single integer solution n=4, x=-1. The second
equation, however, admits two solutions n=4, y=0 and n=5, y=-1 and the
modulo function finds the wrong one (that is the one inconsistent with
the first equation)!
To summarize, you are right, the modulo function is the robust means
to find the parent matrix upper right element, but the lower right
element is better calculated some other way. You can use linear
equation as above, or even more simple, leverage the determinant
constraint.
creecode
> Oops. Actually, your question is buried in the discussion on the
> Errata page:
My bad. It was right there in front of me and I missed it! :-)
Thanks!
Toodle-looooooooo......
creecode
creecode
On Jul 1, 2:05 pm, creecode <creec...@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.
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
Vadim Tropashko
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)
creecode
Sorry for delayed reply.
On Aug 16, 12:52 pm, Vadim Tropashko <vadim...@gmail.com> wrote:
> The records ordered by idx_left, idx_right desc. I assume you want a
> query that when given a node in a hierarchy fetches the next node
> according to the ordering. I found that this query is a mess due to
> composite ordering key. Therefore, it makes sense 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)
Excellent! Seems to work great! Thank you so much!
Toodle-loooooooooooooo
creecode
creecode
On Aug 16, 12:52 pm, Vadim Tropashko <vadim...@gmail.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)
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
Vadim Tropashko
>
> - Show quoted text -
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
creecode
On Sep 7, 8:47 am, Vadim Tropashko <vadim...@gmail.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
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
creecode
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!
> On Jul 1, 2:05 pm, creecode <creec...@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
Vadim Tropashko
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,
> ( @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.