logo标签列表

SQL中递归查询邻接表以进行先序树遍历？

algorithmdata-structuresrdbmsnested-setsrdbms-agnostic
7

我正在将数据从一个数据库架构迁移到另一个。旧的架构基于邻接列表具有分类系统，其中包含id、category和parent_id。如果一个类别在第二个类别下面，那么该类别的父ID为第二个类别的ID。例如：

+-------------+----------------------+--------+
| category_id | name                 | parent |
+-------------+----------------------+--------+
|           1 | ELECTRONICS          |   NULL |
|           2 | TELEVISIONS          |      1 |
|           3 | TUBE                 |      2 |
|           4 | LCD                  |      2 |
|           5 | PLASMA               |      2 |
|           6 | PORTABLE ELECTRONICS |      1 |
|           7 | MP3 PLAYERS          |      6 |
|           8 | FLASH                |      7 |
|           9 | CD PLAYERS           |      6 |
|          10 | 2 WAY RADIOS         |      6 |
+-------------+----------------------+--------+

新模式具有修改后的预排序树遍历算法：
+-------------+----------------------+-----+-----+
| category_id | name                 | lft | rgt |
+-------------+----------------------+-----+-----+
|           1 | ELECTRONICS          |   1 |  20 |
|           2 | TELEVISIONS          |   2 |   9 |
|           3 | TUBE                 |   3 |   4 |
|           4 | LCD                  |   5 |   6 |
|           5 | PLASMA               |   7 |   8 |
|           6 | PORTABLE ELECTRONICS |  10 |  19 |
|           7 | MP3 PLAYERS          |  11 |  14 |
|           8 | FLASH                |  12 |  13 |
|           9 | CD PLAYERS           |  15 |  16 |
|          10 | 2 WAY RADIOS         |  17 |  18 |
+-------------+----------------------+-----+-----+

这些示例源自文章在MySQL中管理分层数据。

总之，我可以编写一个具有递归函数的php脚本，将邻接列表迁移到前序树结构中。对于每一行，它将使用空白的“rgt”值进行插入，查找子级并对其应用递归函数，跟踪计数器，然后更新“rgt”值。

但我想使用纯SQL完成此操作。但是，我不知道足够的知识来掌握它。首先，我不知道是否可以使用递归查询来执行此操作，或者是否有其他方法来执行此操作。

你是否有已知的层级数量 - 这是一个静态数据集，还是需要在“任何”数据集上工作？ - Kirk Broadhurst
在我正在处理的数据集中，它更或多或少是静态的，因此有已知的级别。 - user151841
但我真的正在寻找一个通用算法。 - user151841
1个回答
6
这是我得到的内容；这是一个例子，可以概括或适应您的情况。
首先，我将设置一个邻接表（维基百科上的语言家族数据）：
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);

这里有一个示例查询以便演示：
mysql> SELECT t1.language AS lev1, t2.language as lev2, t3.language as lev3, t4.language as lev4, t5.language AS lev5
    -> FROM language_family_adj_list AS t1
    -> LEFT JOIN language_family_adj_list AS t2 ON t2.parent_id = t1.language_id
    -> LEFT JOIN language_family_adj_list AS t3 ON t3.parent_id = t2.language_id
    -> LEFT JOIN language_family_adj_list AS t4 ON t4.parent_id = t3.language_id
    -> LEFT JOIN language_family_adj_list AS t5 ON t5.parent_id = t4.language_id
    -> WHERE t1.parent_id IS NULL
    -> ORDER BY t1.language, t2.language, t3.language, t4.language, t5.language;
+-------------+---------------+--------------+------------------+------+
| lev1        | lev2          | lev3         | lev4             | lev5 |
+-------------+---------------+--------------+------------------+------+
| Finno-Ugric | Baltic-Finnic | Estonian     | South Estonian   | Voro | 
| Finno-Ugric | Baltic-Finnic | Finnish      | NULL             | NULL | 
| Finno-Ugric | Baltic-Finnic | Ingrian      | NULL             | NULL | 
| Finno-Ugric | Baltic-Finnic | Karelian     | Karelian Proper  | NULL | 
| Finno-Ugric | Baltic-Finnic | Karelian     | Lude             | NULL | 
| Finno-Ugric | Baltic-Finnic | Karelian     | Olonets Karelian | NULL | 
| Finno-Ugric | Baltic-Finnic | Livonian     | NULL             | NULL | 
| Finno-Ugric | Baltic-Finnic | Veps         | NULL             | NULL | 
| Finno-Ugric | Baltic-Finnic | Votic        | NULL             | NULL | 
| Finno-Ugric | Hungarian     | NULL         | NULL             | NULL | 
| Finno-Ugric | Khanty        | NULL         | NULL             | NULL | 
| Finno-Ugric | Mansi         | NULL         | NULL             | NULL | 
| Finno-Ugric | Mari          | NULL         | NULL             | NULL | 
| Finno-Ugric | Mordvinic     | Erzya        | NULL             | NULL | 
| Finno-Ugric | Mordvinic     | Moksha       | NULL             | NULL | 
| Finno-Ugric | Permic        | Komi         | NULL             | NULL | 
| Finno-Ugric | Permic        | Komi-Permyak | NULL             | NULL | 
| Finno-Ugric | Permic        | Udmurt       | NULL             | NULL | 
| Finno-Ugric | Sami          | Eastern Sami | Akkala Sami      | NULL | 
| Finno-Ugric | Sami          | Eastern Sami | Inari Sami       | NULL | 
| Finno-Ugric | Sami          | Eastern Sami | Kemi Sami        | NULL | 
| Finno-Ugric | Sami          | Eastern Sami | Kildin Sami      | NULL | 
| Finno-Ugric | Sami          | Eastern Sami | Skolt Sami       | NULL | 
| Finno-Ugric | Sami          | Eastern Sami | Ter Sami         | NULL | 
| Finno-Ugric | Sami          | Western Sami | Lule Sami        | NULL | 
| Finno-Ugric | Sami          | Western Sami | Northern Sami    | NULL | 
| Finno-Ugric | Sami          | Western Sami | Pite Sami        | NULL | 
| Finno-Ugric | Sami          | Western Sami | Southern Sami    | NULL | 
| Finno-Ugric | Sami          | Western Sami | Umi Sami         | NULL | 
+-------------+---------------+--------------+------------------+------+
29 rows in set (0.00 sec)

所以，这里是修改后的前序遍历树表模式：
CREATE TABLE language_family_mptt (
 language VARCHAR(30) NOT NULL,
 lft INT NOT NULL,
 rgt INT NOT NULL
) COLLATE utf8;

下面是用于迁移数据的递归存储过程：

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 ;

以下是结果：

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;
+---------------------------------+
| name                            |
+---------------------------------+
|    Finno-Ugric                  | 
|        Baltic-Finnic            | 
|            Estonian             | 
|                South Estonian   | 
|                    Voro         | 
|            Finnish              | 
|            Ingrian              | 
|            Karelian             | 
|                Karelian Proper  | 
|                Lude             | 
|                Olonets Karelian | 
|            Livonian             | 
|            Veps                 | 
|            Votic                | 
|        Hungarian                | 
|        Khanty                   | 
|        Mansi                    | 
|        Mari                     | 
|        Mordvinic                | 
|            Erzya                | 
|            Moksha               | 
|        Permic                   | 
|            Komi                 | 
|            Komi-Permyak         | 
|            Udmurt               | 
|        Sami                     | 
|            Eastern Sami         | 
|                Akkala Sami      | 
|                Inari Sami       | 
|                Kemi Sami        | 
|                Kildin Sami      | 
|                Skolt Sami       | 
|                Ter Sami         | 
|            Western Sami         | 
|                Lule Sami        | 
|                Northern Sami    | 
|                Pite Sami        | 
|                Southern Sami    | 
|                Umi Sami         | 
+---------------------------------+
39 rows in set (0.00 sec)

:D

1
递归存储过程...非常好。 - Yzmir Ramirez
我尝试过这个，但“rgt”列没有被填充，lft的值是正确的，但所有行的rgt都是null。 - user1815489
我刚刚在Debian上的mysql 5.1.63-0+squeeze1上尝试了一下复制/粘贴，它可以正常工作。你原来的邻接表是否被正确地填充了？ - user151841
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接