Как поддерживать рекурсивный инвариант в базе данных 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 на листовых узлах. Можно предположить, что листовые узлы останутся листовыми узлами, внутренние узлы останутся внутренними узлами, и все останется как правильное дерево.

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

  • Полная инвалидация, после любого обновления пересчитывать все (Эм... Нет)
  • Set a trigger on the items table to update the parent of any row that is updated
    • This would be recursive (updates trigger updates, trigger updates, ...)
    • Не работает, MySQL не может обновить таблицу, которая запустила триггер
  • Set a trigger to schedule an update of the parent of any row that is updated
    • This would be iterative (get an item from the schedule, processing it schedules more items)
    • Что запускает это? Доверять клиентскому коду, чтобы сделать это правильно?
    • Преимущество состоит в том, что при правильном заказе обновлений требуется меньшее количество средств. Но этот порядок сам по себе является осложнением.

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

FWIW Я знаю, что это «немного за борт», но я делаю это для удовольствия (Веселье: глагол, Поиск невозможного, делая это. :-)


person BCS    schedule 21.08.2008    source источник


Ответы (2)


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

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

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

person nlucaroni    schedule 22.08.2008
comment
Интересный подход. Что мне не нравится в этом, так это то, что он использует что-то вроде N*Log(N) пробела. Также у меня есть некоторые ограничения версий, которые потребуют серьезных модов. -- К сожалению, автор никогда не рассказывает, как обновлять агрегированные значения. Я могу придумать несколько подходов, но они будут зависеть от этой реализации. -- Мне придется подумать об этом еще. (перенесено из [очень старого] ответа.) - person BCS; 29.03.2011
comment
Я обновил ссылку на документацию mysql, в которой упоминается формат. - person nlucaroni; 29.03.2011

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

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

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

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

Удачи!

person Grzegorz Gierlik    schedule 21.08.2008