I am migrating data from one database schema to another. The old
schema has a categorization system based on an adjacency list, with
id, category, and parent_id. If one category is under a second, that
category has the second's id as its parent id. For example:
+-------------+----------------------+--------+

The new schema has a modified preorder tree traversal algorithm:
+-------------+----------------------+-----+-----+

Examples taken from this page:
http://dev.mysql.com/tech-resources/...ical-data.html

Anywho, I'm capable or writing a php script with a recursive function
that will migrate the adjancency list to the preoder tree structure.
Basically for each row, it inserts it with a blank 'rgt' value, looks
for children, applies the function recursively to them, keeping track
of the counter, and then updates the 'rgt' value.

But I want to do this in pure sql. However, I don't know enough to get
a foothold on it. For starters, I don't know if you can do this with a
recursive query, or if there are other ways of doing it.

Can someone help get me started or pointed in the right direction?

On Mar 31, 11:46*pm, Steven Lefevre <steven.m.lefe... (AT) gmail (DOT) com>
wrote:

based on what I see, this is going to be a nightmare to administer.
Every time you add a new category you must potentially shift your lft/
rht min and max values or spend time trying to "redo" what you already
have. What happens when you overrun your allotment? Do you then re-
order your entire database. Hierarchical databases can be Extremely
fast (the db that was (maybe still is) used for Intel's manufacturing
sites was a database called Oracle DBMS - formerly DEC/DBMS. It was
blazing fast - however, once the schema hierarchy in these databases
are set YOU DO NOT CHANGE THEM because it is so painful.

It appears that you are trying to solve a problem that does not
exist. Take a step back and ask yourself exactly what problem are you
trying to solve? Any time a table must self-reference itself, it is
most often a disaster in the making. Over the 20+ years, I have had
to re-engineer databases because of someone doing something just
because they could or thought it would solve a problem that did not
exist. Making a hierarchical model out of a relational database, in
my experience never results in anything good.

The link you referenced is as good a start as any... and having been
a consultant for many years, it is my experience that you do not go
down a particular path until you completely understand the limitations
and strengths of that path. You don't try to set a land speed record
on a back country road. (bad metaphor, but it's late...)

On 04/01/2011 05:46 AM, Steven Lefevre wrote:
I have some notes on an alternative to nested sets up at:

http://www.dustbite.se/tree

The main benefit is that small changes in the tree have a relative low
impact compared to nested sets. On the other hand it is more difficult
to do - for example - in-order traversal.


/Lennart

On Apr 1, 11:13*pm, onedbguru <onedbg... (AT) yahoo (DOT) com> wrote:


'You' meaning the program here. And this is the kind of things we
write programs for

No -- only nodes with a left value higher than the right of the
insert. Isn't this much preferred to an adjacency list?

My client is migrating from one listing web app to another. The
original Listings web app uses and adjanceny list. The new one uses a
preorder traversal algorithm. In what sense does this problem not
exist?

Migrating from one web app to the other.

Isn't this exactly the reason that you use modified preorder traversal
tree?

Here's what I've got; it's an example and can be generalized or
adapted to your situation.

First I'll set up an adjacency list (language family data from
wikipedia):

CREATE TABLE IF NOT EXISTS `language_family_adj_list` (
`language_id` int(11) NOT NULL auto_increment,
`language` varchar(20) NOT NULL,
`parent_id` int(11) default NULL,
PRIMARY KEY (`language_id`)
) ENGINE=MyISAM DEFAULT CHARSET=utf8 AUTO_INCREMENT=41 ;


INSERT INTO `language_family_adj_list` (`language_id`, `language`,
`parent_id`) VALUES
(1, 'Finno-Ugric', NULL),
(2, 'Hungarian', 1),
(3, 'Khanty', 1),
(4, 'Mansi', 1),
(5, 'Permic', 1),
(6, 'Mari', 1),
(7, 'Mordvinic', 1),
(8, 'Sami', 1),
(9, 'Baltic-Finnic', 1),
(10, 'Komi', 5),
(11, 'Komi-Permyak', 5),
(12, 'Udmurt', 5),
(13, 'Erzya', 7),
(14, 'Moksha', 7),
(15, 'Western Sami', 8),
(16, 'Eastern Sami', 8),
(17, 'Southern Sami', 15),
(18, 'Umi Sami', 15),
(19, 'Lule Sami', 15),
(20, 'Pite Sami', 15),
(22, 'Northern Sami', 15),
(23, 'Kemi Sami', 16),
(24, 'Inari Sami', 16),
(25, 'Akkala Sami', 16),
(26, 'Kildin Sami', 16),
(27, 'Skolt Sami', 16),
(28, 'Ter Sami', 16),
(29, 'Estonian', 9),
(30, 'Finnish', 9),
(31, 'Ingrian', 9),
(32, 'Karelian', 9),
(33, 'Livonian', 9),
(34, 'Veps', 9),
(35, 'Votic', 9),
(36, 'South Estonian', 29),
(37, 'Voro', 36),
(38, 'Karelian Proper', 32),
(39, 'Lude', 32),
(40, 'Olonets Karelian', 32);


Here's a query to demonstrate:

mysql> SELECT t1.language AS lev1, t2.language as lev2,
t3.language as lev3, t4.language as lev4, t5.language AS lev5
+-------------+---------------+--------------+------------------+------
+
+
+
29 rows in set (0.00 sec)

So here's the modified preorder traversal tree table schema:

CREATE TABLE language_family_mptt (
language VARCHAR(30) NOT NULL,
lft INT NOT NULL,
rgt INT NOT NULL
) COLLATE utf8;


And then here's the recursive stored procedure to migrate the data:

TRUNCATE TABLE language_family_mptt;
SET max_sp_recursion_depth = 255;
DROP PROCEDURE IF EXISTS insert_branches;
DROP PROCEDURE IF EXISTS start_tree;
DELIMITER ~~

CREATE PROCEDURE start_tree()
BEGIN
DECLARE language_field VARCHAR(100);
DECLARE done INT DEFAULT 0;
DECLARE insert_id INT;
DECLARE source_id INT;

DECLARE cursor1 CURSOR FOR SELECT language, language_id FROM
language_family_adj_list WHERE parent_id IS NULL ORDER BY language;

DECLARE CONTINUE HANDLER FOR NOT FOUND SET done = 1;

OPEN cursor1;
read_loop: LOOP

SET @my_left = 1;

FETCH cursor1 INTO language_field, source_id;
INSERT INTO language_family_mptt ( language, lft ) VALUES
( language_field, 1 );

CALL insert_branches( source_id );

UPDATE language_family_mptt SET rgt = @my_left + 1 WHERE lft =
1 AND rgt = 0;

IF done THEN
LEAVE read_loop;
END IF;

END LOOP;
CLOSE cursor1;

END; ~~

CREATE PROCEDURE insert_branches( IN source_parent_id INT )
BEGIN
DECLARE done INT DEFAULT 0;
DECLARE next_source_parent_id INT DEFAULT NULL;
DECLARE orig_left INT DEFAULT NULL;
DECLARE language_field VARCHAR(100);
DECLARE cursor1 CURSOR FOR SELECT language_id, language FROM
language_family_adj_list WHERE parent_id = source_parent_id ORDER BY
language;
DECLARE CONTINUE HANDLER FOR NOT FOUND SET done = 1;

OPEN cursor1;

read_loop: LOOP

FETCH cursor1 INTO next_source_parent_id, language_field;

IF done THEN
LEAVE read_loop;
END IF;

SET @my_left = @my_left + 1;

INSERT INTO language_family_mptt ( language, lft ) VALUES
( language_field, @my_left );

SET orig_left = @my_left;

CALL insert_branches( next_source_parent_id );

UPDATE language_family_mptt SET rgt = @my_left + 1 WHERE lft =
orig_left AND rgt = 0 ;

SET @my_left = @my_left + 1;

END LOOP;
CLOSE cursor1;
END; ~~

DELIMITER ;


And here's the results:

mysql> SELECT CONCAT( REPEAT( ' ', (COUNT(parent.language) - 1) ),
node.language) AS name FROM language_family_mptt AS node,
language_family_mptt AS parent WHERE node.lft BETWEEN parent.lft AND
parent.rgt GROUP BY node.language ORDER BY node.lft;
+---------------------------------+
39 rows in set (0.00 sec)