Как сохранить рекурсивный инвариант в базе данных MySQL?

У меня есть дерево, закодированное в базе данных MySQL как ребра:

CREATE TABLE items (
    num INT,
    tot INT,
    PRIMARY KEY (num)
    );
CREATE TABLE tree (
    orig INT,
    term INT
    FOREIGN KEY (orig,term) REFERENCES items (num,num)
    )

Для каждого листа в дереве, items.totкто-то задан. Для внутренних узлов, items.totдолжна быть сумма его детей. Повторный запуск следующего запроса приведет к желаемому результату.

UPDATE items SET tot = (
    SELECT SUM(b.tot) FROM
        tree JOIN items AS b
        ON tree.term = b.num 
        WHERE tree.orig=items.num)
    WHERE EXISTS 
        (SELECT * FROM tree WHERE orig=items.num)

(обратите внимание, что это на самом деле не работает, но это не относится к делу)

Предположим, что база данных существует и инвариант уже выполнен.

Вопрос в том:

Каков наиболее практичный способ обновления БД при сохранении этого требования? Обновления могут перемещать узлы вокруг или изменять значение totна конечных узлах. Можно предположить, что листовые узлы останутся как листовые узлы, внутренние узлы останутся как внутренние узлы, и все это останется как правильное дерево.

Некоторые мысли у меня были:

  • Полная недействительность, после любого обновления, пересчитать все (Гм ... Нет)
  • Установите триггер в таблице элементов для обновления родительского элемента любой строки, которая обновляется
    • Это было бы рекурсивно (обновления запускают обновления, запускают обновления, ...)
    • Не работает, MySQL не может обновить таблицу, которая сработала
  • Установите триггер, чтобы запланировать обновление родительского элемента любой строки, которая обновляется
    • Это было бы итеративно (получить элемент из расписания, обрабатывая его по расписанию больше элементов)
    • От чего это началось? Доверьтесь клиентскому коду, чтобы получить его правильно?
    • Преимущество состоит в том, что, если обновления упорядочены правильно, на компьютере должно быть меньше сумм. Но это упорядочение само по себе является осложнением.

Идеальное решение будет обобщать на другие «агрегирующие инварианты»

Я знаю, что это «немного за бортом», но я делаю это для развлечения (Fun: глагол, найти невозможное, делая это. :-)

21.08.2008 16:20:12
2 ОТВЕТА
РЕШЕНИЕ

Проблема у вас ясна, рекурсия в SQL. Вам нужно получить родительский элемент родительского ... листа и обновить его общее количество (либо вычесть старое и добавить новое, либо пересчитать). Вам нужна некоторая форма идентификатора, чтобы увидеть структуру дерева, и взять все дочерние узлы и список родителей / пути к листу для обновления.

Этот метод добавляет постоянное пространство (2 столбца к вашей таблице - но вам нужна только одна таблица, иначе вы можете сделать соединение позже). Некоторое время назад я поиграл со структурой, в которой использовался иерархический формат, в котором использовались столбцы «влево» и «вправо» (очевидно, не в этих именах), рассчитанные путем обхода до и после заказа соответственно - не волнуйтесь их не нужно пересчитывать каждый раз.

Я позволю вам взглянуть на страницу с использованием этого метода в mysql вместо продолжения этого обсуждения на тот случай, если вам не понравится этот метод в качестве ответа. Но если вам это нравится, напишите / отредактируйте, и я найду время и уточню.

1
29.03.2011 03:28:02
Интересный подход. Что мне не нравится в этом, так это то, что он использует что-то вроде N*Log(N)пространства. Также у меня есть некоторые ограничения версий, которые требуют основных модов. - К сожалению, автор никогда не понимает, как обновить совокупные значения. Я могу придумать несколько подходов, но они будут зависеть от этой реализации. - Я должен подумать об этом больше. (перенесено из [очень старого] ответа.)
BCS 29.03.2011 00:59:24
Я обновил ссылку на документацию mysql, в которой упоминается формат.
nlucaroni 29.03.2011 03:28:35

Я не уверен, что правильно понимаю ваш вопрос, но это может сработать. Мой подход к деревьям в SQL .

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

С помощью этого метода вы можете легко обновить все узлы, зависящие от модифицированного узла K, с помощью N простых запросов SELECT, где N - это расстояние от K до корневого узла.

Я надеюсь, что ваше дерево не очень глубоко :).

Удачи!

1
21.08.2008 21:36:29