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

Question

У меня есть дерево, закодированное в базе данных 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 не может обновить таблицу, вызвавшую триггер.
• Установите триггер для планирования обновления родительского элемента любой обновляемой строки.
  • Это будет итеративно (получить элемент из расписания, его обработка планирует больше элементов)
  • Что это запускает?Доверять клиентскому коду, чтобы все было правильно?
  • Преимущество состоит в том, что при правильном заказе обновлений потребуется меньше компьютерных сумм.Но этот порядок сам по себе усложнен.

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

Кстати, я знаю, что это «немного переборщило», но я делаю это ради удовольствия (Забава:глагол: Обнаружить невозможное, сделав это.:-)

Answer 1

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

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

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

Answer 2

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

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

С помощью этого метода вы можете легко обновить все узлы, зависящие от измененного узла. К с о Н простые запросы SELECT, где Н расстояние К из корневого узла.

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

Удачи!