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
Vadim's weblog < http://vadimtropashko.wordpress.com/...D-book/errata/

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

On Jul 1, 2:05*pm, creecode <creec... (AT) gmail (DOT) com> wrote:
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

On Jul 2, 10:21*am, Tegiri Nenashi <tegirinena... (AT) gmail (DOT) com> wrote:

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

On Jul 2, 2:45*pm, creecode <creec... (AT) gmail (DOT) com> wrote:
http://vadimtropashko.wordpress.com/...trix-encoding/

On Jul 2, 6:03*pm, Vadim Tropashko <vadim... (AT) gmail (DOT) com> wrote:

Hello Vadim,

Thank you so much for the updated query. It seems to work fine!

Have a blast on the 4TH!

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

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

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

On Jul 3, 12:09*pm, creecode <creec... (AT) gmail (DOT) com> wrote:
select MOD(2,1) from dual;
MOD(2,1)
----------------------
0

Fire your database vendor:-)

On Jul 5, 12:25*pm, Vadim Tropashko <vadim... (AT) gmail (DOT) com> wrote:

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

On Jul 5, 1:38*pm, creecode <creec... (AT) gmail (DOT) com> wrote:
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.

On Jul 6, 10:28*am, Vadim Tropashko <vadim... (AT) gmail (DOT) com> wrote:

My bad. It was right there in front of me and I missed it! :-)
Thanks!

Toodle-looooooooo......
creecode