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

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

2 голосов
/ 21 августа 2008

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

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

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

Ответы [ 2 ]

1 голос
/ 22 августа 2008

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

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

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

1 голос
/ 22 августа 2008

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

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

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

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

Удачи!

...