· 9 years ago · Dec 22, 2016, 02:46 AM
1/*
2Adjacency lists and modified preorder trees are two ways of storing nested hierarchies in a relational database.
3
4So the adjacency list is probably one that's intuitive and easy to come up with if you are new to the field. However, once you learn the benefits of the preorder tree, you'll probably want to migrate. But the migration is not so easy as a few queries -- you'll need an algorithm to do so, and a recursive one at that.
5
6Here's a couple stored procedures for MySQL that will migrate data from an adjacency list to a modified preorder traversal tree:
7
8First I'll set up an adjacency list (language family data from wikipedia):
9*/
10 CREATE TABLE IF NOT EXISTS `language_family_adj_list` (
11 `language_id` int(11) NOT NULL auto_increment,
12 `language` varchar(20) NOT NULL,
13 `parent_id` int(11) default NULL,
14 PRIMARY KEY (`language_id`)
15 ) ENGINE=MyISAM DEFAULT CHARSET=utf8 AUTO_INCREMENT=41 ;
16
17
18 INSERT INTO `language_family_adj_list` (`language_id`, `language`, `parent_id`) VALUES
19 (1, 'Finno-Ugric', NULL),
20 (2, 'Hungarian', 1),
21 (3, 'Khanty', 1),
22 (4, 'Mansi', 1),
23 (5, 'Permic', 1),
24 (6, 'Mari', 1),
25 (7, 'Mordvinic', 1),
26 (8, 'Sami', 1),
27 (9, 'Baltic-Finnic', 1),
28 (10, 'Komi', 5),
29 (11, 'Komi-Permyak', 5),
30 (12, 'Udmurt', 5),
31 (13, 'Erzya', 7),
32 (14, 'Moksha', 7),
33 (15, 'Western Sami', 8),
34 (16, 'Eastern Sami', 8),
35 (17, 'Southern Sami', 15),
36 (18, 'Umi Sami', 15),
37 (19, 'Lule Sami', 15),
38 (20, 'Pite Sami', 15),
39 (22, 'Northern Sami', 15),
40 (23, 'Kemi Sami', 16),
41 (24, 'Inari Sami', 16),
42 (25, 'Akkala Sami', 16),
43 (26, 'Kildin Sami', 16),
44 (27, 'Skolt Sami', 16),
45 (28, 'Ter Sami', 16),
46 (29, 'Estonian', 9),
47 (30, 'Finnish', 9),
48 (31, 'Ingrian', 9),
49 (32, 'Karelian', 9),
50 (33, 'Livonian', 9),
51 (34, 'Veps', 9),
52 (35, 'Votic', 9),
53 (36, 'South Estonian', 29),
54 (37, 'Voro', 36),
55 (38, 'Karelian Proper', 32),
56 (39, 'Lude', 32),
57 (40, 'Olonets Karelian', 32);
58
59
60/*
61Here's a query to demonstrate:
62
63
64 mysql> SELECT t1.language AS lev1, t2.language as lev2, t3.language as lev3, t4.language as lev4, t5.language AS lev5
65 -> FROM language_family_adj_list AS t1
66 -> LEFT JOIN language_family_adj_list AS t2 ON t2.parent_id = t1.language_id
67 -> LEFT JOIN language_family_adj_list AS t3 ON t3.parent_id = t2.language_id
68 -> LEFT JOIN language_family_adj_list AS t4 ON t4.parent_id = t3.language_id
69 -> LEFT JOIN language_family_adj_list AS t5 ON t5.parent_id = t4.language_id
70 -> WHERE t1.parent_id IS NULL
71 -> ORDER BY t1.language, t2.language, t3.language, t4.language, t5.language;
72 +-------------+---------------+--------------+------------------+------+
73 | lev1 | lev2 | lev3 | lev4 | lev5 |
74 +-------------+---------------+--------------+------------------+------+
75 | Finno-Ugric | Baltic-Finnic | Estonian | South Estonian | Voro |
76 | Finno-Ugric | Baltic-Finnic | Finnish | NULL | NULL |
77 | Finno-Ugric | Baltic-Finnic | Ingrian | NULL | NULL |
78 | Finno-Ugric | Baltic-Finnic | Karelian | Karelian Proper | NULL |
79 | Finno-Ugric | Baltic-Finnic | Karelian | Lude | NULL |
80 | Finno-Ugric | Baltic-Finnic | Karelian | Olonets Karelian | NULL |
81 | Finno-Ugric | Baltic-Finnic | Livonian | NULL | NULL |
82 | Finno-Ugric | Baltic-Finnic | Veps | NULL | NULL |
83 | Finno-Ugric | Baltic-Finnic | Votic | NULL | NULL |
84 | Finno-Ugric | Hungarian | NULL | NULL | NULL |
85 | Finno-Ugric | Khanty | NULL | NULL | NULL |
86 | Finno-Ugric | Mansi | NULL | NULL | NULL |
87 | Finno-Ugric | Mari | NULL | NULL | NULL |
88 | Finno-Ugric | Mordvinic | Erzya | NULL | NULL |
89 | Finno-Ugric | Mordvinic | Moksha | NULL | NULL |
90 | Finno-Ugric | Permic | Komi | NULL | NULL |
91 | Finno-Ugric | Permic | Komi-Permyak | NULL | NULL |
92 | Finno-Ugric | Permic | Udmurt | NULL | NULL |
93 | Finno-Ugric | Sami | Eastern Sami | Akkala Sami | NULL |
94 | Finno-Ugric | Sami | Eastern Sami | Inari Sami | NULL |
95 | Finno-Ugric | Sami | Eastern Sami | Kemi Sami | NULL |
96 | Finno-Ugric | Sami | Eastern Sami | Kildin Sami | NULL |
97 | Finno-Ugric | Sami | Eastern Sami | Skolt Sami | NULL |
98 | Finno-Ugric | Sami | Eastern Sami | Ter Sami | NULL |
99 | Finno-Ugric | Sami | Western Sami | Lule Sami | NULL |
100 | Finno-Ugric | Sami | Western Sami | Northern Sami | NULL |
101 | Finno-Ugric | Sami | Western Sami | Pite Sami | NULL |
102 | Finno-Ugric | Sami | Western Sami | Southern Sami | NULL |
103 | Finno-Ugric | Sami | Western Sami | Umi Sami | NULL |
104 +-------------+---------------+--------------+------------------+------+
105 29 rows in set (0.00 sec)
106
107
108
109So here's the modified preorder traversal tree table schema:
110
111*/
112 CREATE TABLE language_family_mptt (
113 language VARCHAR(30) NOT NULL,
114 lft INT NOT NULL,
115 rgt INT NOT NULL
116 ) COLLATE utf8;
117
118
119/*
120And then here's the recursive stored procedure to migrate the data:
121
122*/
123
124 TRUNCATE TABLE language_family_mptt;
125 SET max_sp_recursion_depth = 255;
126 DROP PROCEDURE IF EXISTS insert_branches;
127 DROP PROCEDURE IF EXISTS start_tree;
128 DELIMITER ~~
129
130 CREATE PROCEDURE start_tree()
131 BEGIN
132 DECLARE language_field VARCHAR(100);
133 DECLARE done INT DEFAULT 0;
134 DECLARE insert_id INT;
135 DECLARE source_id INT;
136
137 DECLARE cursor1 CURSOR FOR SELECT language, language_id FROM language_family_adj_list WHERE parent_id IS NULL ORDER BY language;
138
139 DECLARE CONTINUE HANDLER FOR NOT FOUND SET done = 1;
140
141 OPEN cursor1;
142 read_loop: LOOP
143
144 SET @my_left = 1;
145
146 FETCH cursor1 INTO language_field, source_id;
147 INSERT INTO language_family_mptt ( language, lft ) VALUES ( language_field, 1 );
148
149 CALL insert_branches( source_id );
150
151 UPDATE language_family_mptt SET rgt = @my_left + 1 WHERE lft = 1 AND rgt = 0;
152
153 IF done THEN
154 LEAVE read_loop;
155 END IF;
156
157 END LOOP;
158 CLOSE cursor1;
159
160 END; ~~
161
162 CREATE PROCEDURE insert_branches( IN source_parent_id INT )
163 BEGIN
164 DECLARE done INT DEFAULT 0;
165 DECLARE next_source_parent_id INT DEFAULT NULL;
166 DECLARE orig_left INT DEFAULT NULL;
167 DECLARE language_field VARCHAR(100);
168 DECLARE cursor1 CURSOR FOR SELECT language_id, language FROM language_family_adj_list WHERE parent_id = source_parent_id ORDER BY language;
169 DECLARE CONTINUE HANDLER FOR NOT FOUND SET done = 1;
170
171 OPEN cursor1;
172
173 read_loop: LOOP
174
175 FETCH cursor1 INTO next_source_parent_id, language_field;
176
177 IF done THEN
178 LEAVE read_loop;
179 END IF;
180
181 SET @my_left = @my_left + 1;
182
183 INSERT INTO language_family_mptt ( language, lft ) VALUES ( language_field, @my_left );
184
185 SET orig_left = @my_left;
186
187 CALL insert_branches( next_source_parent_id );
188
189 UPDATE language_family_mptt SET rgt = @my_left + 1 WHERE lft = orig_left AND rgt = 0 ;
190
191 SET @my_left = @my_left + 1;
192
193 END LOOP;
194 CLOSE cursor1;
195 END; ~~
196
197 DELIMITER ;
198
199
200/*
201And here's the results:
202
203
204 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;
205 +---------------------------------+
206 | name |
207 +---------------------------------+
208 | Finno-Ugric |
209 | Baltic-Finnic |
210 | Estonian |
211 | South Estonian |
212 | Voro |
213 | Finnish |
214 | Ingrian |
215 | Karelian |
216 | Karelian Proper |
217 | Lude |
218 | Olonets Karelian |
219 | Livonian |
220 | Veps |
221 | Votic |
222 | Hungarian |
223 | Khanty |
224 | Mansi |
225 | Mari |
226 | Mordvinic |
227 | Erzya |
228 | Moksha |
229 | Permic |
230 | Komi |
231 | Komi-Permyak |
232 | Udmurt |
233 | Sami |
234 | Eastern Sami |
235 | Akkala Sami |
236 | Inari Sami |
237 | Kemi Sami |
238 | Kildin Sami |
239 | Skolt Sami |
240 | Ter Sami |
241 | Western Sami |
242 | Lule Sami |
243 | Northern Sami |
244 | Pite Sami |
245 | Southern Sami |
246 | Umi Sami |
247 +---------------------------------+
248 39 rows in set (0.00 sec)
249
250:D
251
252*/