Сведения о вопросе

Codeliver

12:03, 15th August, 2020

Теги

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

Просмотров: 447   Ответов: 2

У меня есть дерево, закодированное в базе данных 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)

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

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

Вопрос в том:

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

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

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

Идеальное решение было бы обобщить на другие "aggregating invariants"

FWIW я знаю, что это "немного за бортом", но я делаю это для удовольствия (Fun: verb, находя невозможное, делая это. :-)



  Сведения об ответе

P_S_S

05:28, 29th August, 2020

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

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

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

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

Удачи Вам!


  Сведения об ответе

+-*/

15:43, 5th August, 2020

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

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

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


Ответить на вопрос

Чтобы ответить на вопрос вам нужно войти в систему или зарегистрироваться