Найдите уровень узла в дереве

У меня есть дерево (вложенные категории) сохраненный следующим образом:

CREATE TABLE `category` (
  `category_id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `category_name` varchar(100) NOT NULL,
  `parent_id` int(10) unsigned DEFAULT NULL,
  PRIMARY KEY (`category_id`),
  UNIQUE KEY `category_name_UNIQUE` (`category_name`,`parent_id`),
  KEY `fk_category_category1` (`parent_id`,`category_id`),
  CONSTRAINT `fk_category_category1` FOREIGN KEY (`parent_id`) REFERENCES `category` (`category_id`) ON DELETE SET NULL ON UPDATE CASCADE
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COLLATE=utf8_spanish_ci

Я должен подать свой клиентский язык (PHP) с информацией об узле (child+parent), таким образом, это может создать дерево в памяти. Я могу настроить свой код PHP, но я думаю, что операция была бы путем, более простым, если я мог бы просто получить строки в таком порядке, что все родители прибывают перед своими детьми. Я мог сделать это, если бы я знал уровень для каждого узла:

SELECT category_id, category_name, parent_id
FROM category
ORDER BY level -- No `level` column so far :(

Можно ли думать о пути (представление, сохраненная стандартная программа или безотносительно...) для вычисления уровня узла? Я предполагаю, что это хорошо, если это не в реальном времени, и я должен повторно вычислить его на модификацию узла.

Первое обновление: прогресс до сих пор

Я записал эти триггеры на основе обратной связи Amarghosh:

DROP TRIGGER IF EXISTS `category_before_insert`;

DELIMITER //

CREATE TRIGGER `category_before_insert` BEFORE INSERT ON `category` FOR EACH ROW BEGIN
    IF NEW.parent_id IS NULL THEN
        SET @parent_level = 0;
    ELSE
        SELECT level INTO @parent_level
        FROM category
        WHERE category_id = NEW.parent_id;
    END IF;

    SET NEW.level = @parent_level+1;
END//

DELIMITER ;


DROP TRIGGER IF EXISTS `category_before_update`;

DELIMITER //

CREATE TRIGGER `category_before_update` BEFORE UPDATE ON `category` FOR EACH ROW BEGIN
    IF NEW.parent_id IS NULL THEN
        SET @parent_level = 0;
    ELSE
        SELECT level INTO @parent_level
        FROM category
        WHERE category_id = NEW.parent_id;
    END IF;

    SET NEW.level = @parent_level+1;
END//

DELIMITER ;

Это, кажется, хорошо работает для вставок и модификаций. Но это не работает на удаления: MySQL Server не запускает триггеры, когда строки обновляются от ON UPDATE CASCADE внешние ключи.

Первая очевидная идея состоит в том, чтобы записать новый триггер для удаления; однако, триггер на таблице categories не позволяется изменить другие строки на этой той же таблице:

DROP TRIGGER IF EXISTS `category_after_delete`;

DELIMITER //

CREATE TRIGGER `category_after_delete` AFTER DELETE ON `category` FOR EACH ROW BEGIN
    /*
     * Raises an error, see below
     */
    UPDATE category SET parent_id=NULL
    WHERE parent_id = OLD.category_id;
END//

DELIMITER ;

Ошибка:

Ошибка редактирования сетки: ошибка SQL (1442): не Может обновить таблицу 'категория' в сохраненной функции/триггере, потому что она уже используется оператором, который вызвал эту сохраненную функцию/триггер.

Второе обновление: рабочее решение (если не доказано неправильно)

Моя первая попытка была довольно разумна, но я нашел проблему, которую мне не могло удаться решить: при запуске ряда операций от триггера MySQL не позволит изменять другие строки от той же таблицы. Так как удаления узла требуют для корректировки уровня всех потомков, я врезался в стену.

В конце я изменил подход с помощью кода отсюда: вместо того, чтобы исправлять индивидуальные уровни, когда изменение узла, у меня есть код для вычисления всех уровней и я инициировал его на каждом редактировании. Так как это - медленное вычисление, и выбирающие данные требуют очень сложного запроса, я кэширую его в таблицу. В моем случае это - приемлемое решение, так как выпуски должны быть редкими.

1. Новая таблица для кэшируемых уровней:

CREATE TABLE `category_level` (
  `category_id` int(10) NOT NULL,
  `parent_id` int(10) DEFAULT NULL, -- Not really necesary
  `level` int(10) NOT NULL,
  PRIMARY KEY (`category_id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COLLATE=utf8_spanish_ci

2. Функция помощника для вычисления уровней

Если я действительно надел схватывание, как оно работает, оно действительно не возвращает ничего полезного отдельно. Вместо этого это хранит материал в переменных сеанса.

CREATE FUNCTION `category_connect_by_parent_eq_prior_id`(`value` INT) RETURNS int(10)
    READS SQL DATA
BEGIN
    DECLARE _id INT;
    DECLARE _parent INT;
    DECLARE _next INT;
    DECLARE CONTINUE HANDLER FOR NOT FOUND SET @category_id = NULL;

    SET _parent = @category_id;
    SET _id = -1;

    IF @category_id IS NULL THEN
        RETURN NULL;
    END IF;

    LOOP
        SELECT  MIN(category_id)
        INTO    @category_id
        FROM    category
        WHERE   COALESCE(parent_id, 0) = _parent
            AND category_id > _id;
        IF @category_id IS NOT NULL OR _parent = @start_with THEN
            SET @level = @level + 1;
            RETURN @category_id;
        END IF;
        SET @level := @level - 1;
        SELECT  category_id, COALESCE(parent_id, 0)
        INTO    _id, _parent
        FROM    category
        WHERE   category_id = _parent;
    END LOOP;
END

3. Процедура для запуска процесса перерасчета

Это в основном инкапсулирует сложный запрос, который получает уровни, которым помогает функция помощника.

CREATE PROCEDURE `update_category_level`()
    SQL SECURITY INVOKER
BEGIN
    DELETE FROM category_level;

    INSERT INTO category_level (category_id, parent_id, level)
    SELECT hi.category_id, parent_id, level
    FROM (
        SELECT category_connect_by_parent_eq_prior_id(category_id) AS category_id, @level AS level
        FROM (
            SELECT  @start_with := 0,
                @category_id := @start_with,
                @level := 0
            ) vars, category
        WHERE @category_id IS NOT NULL
        ) ho
    JOIN category hi ON hi.category_id = ho.category_id;
END

4. Триггеры для хранения таблицы кэша актуальной

CREATE TRIGGER `category_after_insert` AFTER INSERT ON `category` FOR EACH ROW BEGIN
    call update_category_level();
END

CREATE TRIGGER `category_after_update` AFTER UPDATE ON `category` FOR EACH ROW BEGIN
    call update_category_level();
END

CREATE TRIGGER `category_after_delete` AFTER DELETE ON `category` FOR EACH ROW BEGIN
    call update_category_level();
END

5. Известные проблемы

• Это является довольно субоптимальным, если узлы часто изменяются.
• MySQL не позволяет транзакции или триггеры привязки таблицы и процедуры. Необходимо заботиться об этих деталях, где Вы редактируете узлы.