Hi,

this is my first post to this group, so a 'Hello' to all of you.

I think some have encountered the need to map a tree to a relational
model and weren't especially happy on what is available. Nested sets
are fast to lookup but messy when it comes to maintaining. Other
approaches use recursive calls with Procedures and - while doing their
job - are limited to a certain recursion level due to database server
setting. Moving the recursion and queries from the dabase to the
client wont push the speed.

I've searched and read a couple of things and came up with the
following solution. I'd happy to get some feedback - especially
regarding the usability and speed where I don't have any hints on
right now.

Best regards, --- Jan.



CREATE TABLE trees (
child_id INT NOT NULL,
parent_id INT NOT NULL,
sib_idx SMALLINT NOT NULL
);

CREATE TABLE nodes (
id INT PRIMARY KEY AUTO_INCREMENT,
title VARCHAR(20)
);


delimiter //

CREATE PROCEDURE addNode( nodeId INT, parentId INT, siblingIdx INT)
BEGIN
DECLARE curChildren INT;
SELECT count(parent_id) into curChildren FROM trees WHERE parent_id
= parentId;
IF siblingIdx <= 0 OR siblingIdx > curChildren THEN
INSERT INTO trees(child_id, parent_id, sib_idx) VALUES(nodeId,
parentId, curChildren+1 );
ELSE
UPDATE trees SET sib_idx = sib_idx+1 WHERE parent_id = parentId
AND sib_idx >= siblingIdx ORDER BY sib_idx DESC;
INSERT INTO trees(child_id, parent_id, sib) VALUES(nodeId,
parentId, siblingIdx );
END IF;
END//


CREATE PROCEDURE getTree( parentId INT )
BEGIN
DECLARE curIdx, curCid, curPid, curLevel, flag INT;

SET curLevel = 1;
SET flag = 0;

DROP TABLE IF EXISTS descendants;
CREATE TEMPORARY TABLE descendants( id INT NOT NULL PRIMARY KEY
AUTO_INCREMENT, depth INT, child_id INT, parent_id INT, sib_idx INT,
INDEX(depth) ) ENGINE=MEMORY;

INSERT INTO descendants values( 0, 0, parentId, -1, -1 );
INSERT INTO descendants SELECT 0, 1, child_id, parent_id, sib_idx
FROM trees WHERE parent_id=parentId AND sib_idx=1;

IF ROW_COUNT() > 0 THEN
this: LOOP
SELECT sib_idx, parent_id, child_id INTO curIdx, curPid, curCid
FROM descendants WHERE depth=curLevel ORDER BY id DESC LIMIT 1;

IF flag = 0 THEN
INSERT INTO descendants SELECT 0, curLevel+1, child_id,
parent_id, sib_idx FROM trees WHERE parent_id=curCid AND sib_idx=1;
END IF;

IF flag = 0 AND ROW_COUNT() > 0 THEN
SET curLevel = curLevel + 1;
ELSE
INSERT INTO descendants SELECT 0, curLevel, child_id,
parent_id, sib_idx FROM trees WHERE parent_id=curPid AND sib_idx=curIdx
+1;
IF ROW_COUNT() = 0 THEN
SET curLevel = curLevel - 1;
SET flag = 1;
ELSE
SET flag = 0;
END IF;
END IF;

IF curLevel = 0 THEN
LEAVE this;
END IF;

END LOOP;
END IF;
SELECT d.depth, CONCAT(REPEAT( ' ', d.depth), n.title ) FROM
descendants d, nodes n where d.child_id=n.id order by d.id;
DROP TABLE descendants;
END//

delimiter ;

--- Example:

INSERT INTO nodes(title) VALUES
('Animals'),
('Mammals'),
('Fish'),
('Carnivores'),
('Herbivores'),
('Tuna'),
('Salmon'),
('Cat'),
('Dog'),
('Horse')
;

call addNode(1,0,0);
call addNode(2,1,0);
call addNode(3,1,0);
call addNode(4,2,0);
call addNode(5,2,0);
call addNode(6,3,0);
call addNode(7,3,0);
call addNode(8,4,0);
call addNode(9,5,0);
call addNode(10,5,0);

call getTree(1);

On Wed, 12 Mar 2008 08:16:01 -0700, jan.kriesten wrote:

> Hi,
>
> this is my first post to this group, so a 'Hello' to all of you.
>
> I think some have encountered the need to map a tree to a relational
> model and weren't especially happy on what is available. Nested sets are
> fast to lookup but messy when it comes to maintaining. Other approaches
> use recursive calls with Procedures and - while doing their job - are
> limited to a certain recursion level due to database server setting.
> Moving the recursion and queries from the dabase to the client wont push
> the speed....

I'm fiddling, half-heartedly, with a relational model based on two
separate tables. And I'll be saying a big thanx to the GEDCOM format for
the inspiration.

The first table sets up a genetic breeding pair, taking no note of social
or legal norms,regarding marriage, divorce, or other such frippery - that
comes elsewhere - thusly;

create table family family_id AUTO_INCREMENT, father INT, mother INT;

The other table sets up individuals, and relates them to their parents
breeding pair - again taking no note of social or legal norms regarding
the matter, thusly;

create table individual indiv_id AUTO_INCREMENT, family_id INT, f_name
VARCHAR(), l_name VARCHAR();

This allows me to parse the tree in either direction. Ex. assume I have
an individual, and I want to find his/her ancestors. I put in that
person's ID and search the family he/she came from, then pull mother/
father - again taking note that this is strictly in the genetic sense -
and calling the same look-up, sequentially this time, father, mother. I'm
working with a known geometric progression, so I can set up a memory
table as part of my procedure and populate it from the results of the
query.

Going the other direction, I would take an individual, parse the family
structures for their ID in either the father or mother roles, and search
all individuals for the family ID(s) that turned up in the first search,
then basically reversing the process described in the ancestor search to
give a list of all (known) descendants of that individual.

Maybe consider something like that?