Создание шаблона дерева в SQL

Question

Я работаю с базой данных, используемой для хранения информации об объектах в виде дерева компонентов. Например, у него может быть объект camry с детским кондиционером и двигателем. У двигателя могут быть поршни в качестве детей, а в воздухе есть вентиляционные отверстия в качестве детей.

Идея состоит в том, что пользователь создавал бы что-то вроде этого как «шаблон», который затем будет использоваться для создания экземпляра дерева «камни» по мере необходимости. Таким образом, пользователь может сначала создать шаблон, а затем использовать его, чтобы добавить десять из этих камрейских деревьев в мастерскую, сохраняя уникальные данные по каждому из них, выбрав «добавить новый автомобиль», выбрав camry, а затем выберите имя.

Как вы храните такую ​​конструкцию в базе данных, и есть ли простой способ создать такое дерево?

Answer 1

Я сделал первую половину этого раньше, поэтому мы начнем там (удобно, нет?). Не зная много о ваших потребностях, я бы рекомендовал следующее в качестве основы (можно регулировать ширину столбцов в случае необходимости):

CREATE TABLE tree (
    id INT UNSIGNED NOT NULL AUTO_INCREMENT, 
    parent_id INT UNSIGNED NOT NULL DEFAULT 0, 
    type VARCHAR(20) NOT NULL, 
    name VARCHAR(32) NOT NULL, 
    PRIMARY KEY (id), 
    UNIQUE KEY (parent_id, type, name), 
    KEY (parent_id) 
); 

Почему я это так? Ну, давайте пройдем через каждое поле. id - глобально уникальное значение, которое мы можем использовать для идентификации этого элемента и всех элементов, которые непосредственно зависят от него. parent_id позволяет нам вернуться через дерево, пока мы не достигнем parent_id == 0, который является вершиной дерева. type будут вашими описаниями «автомобиль» или «впуск». name дал бы вам право на получение type, поэтому такие вещи, как «Camry» и «Driver Left» (для «vent» явно).

данные будут сохранены со значениями, как эти:

INSERT INTO tree (parent_id, type, name) VALUES 
    (0, 'car', 'Camry'), 
    (1, 'hvac', 'HVAC'), 
    (2, 'vent', 'Driver Front Footwell'), 
    (2, 'vent', 'Passenger Front Footwell'), 
    (2, 'vent', 'Driver Rear Footwell'), 
    (2, 'vent', 'Passenger Rear Footwell'), 
    (1, 'glass', 'Glass'), 
    (7, 'window', 'Windshield'), 
    (7, 'window', 'Rear Window'), 
    (7, 'window', 'Driver Front Window'), 
    (7, 'window', 'Passenger Front Window'), 
    (7, 'window', 'Driver Rear Window'), 
    (7, 'window', 'Passenger Rear Window'), 
    (1, 'mirrors', 'Mirrors'), 
    (14, 'mirror', 'Rearview Mirror'), 
    (14, 'mirror', 'Driver Mirror'), 
    (14, 'mirror', 'Passenger Mirror'); 

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

(1, 0, 'car', 'Camry') 
    | (2, 1, 'hvac', 'HVAC') 
    | +- (3, 2, 'vent', 'Driver Front Footwell') 
    | +- (4, 2, 'vent', 'Passenger Front Footwell') 
    | +- (5, 2, 'vent', 'Driver Rear Footwell') 
    | +- (6, 2, 'vent', 'Passenger Rear Footwell') 
    +- (7, 1, 'glass', 'Glass') 
    | +- (8, 7, 'window', 'Windshield') 
    | +- (9, 7, 'window', 'Rear Window') 
    | +- (10, 7, 'window', 'Driver Front Window') 
    | +- (11, 7, 'window', 'Passenger Front Window') 
    | +- (12, 7, 'window', 'Driver Rear Window') 
    | +- (13, 7, 'window', 'Passenger Rear Window') 
    +- (14, 1, 'mirrors', 'Mirrors') 
     +- (15, 14, 'mirror', 'Rearview Mirror') 
     +- (16, 14, 'mirror', 'Driver Mirror') 
     +- (17, 14, 'mirror', 'Passenger Mirror') 

Итак, твердая часть: копирование дерева. Из-за ссылок parent_id мы не можем делать что-то вроде INSERT INTO ... SELECT; мы сводимся к необходимости использовать рекурсивную функцию. Я знаю, мы входим в грязное место. Я собираюсь использовать псевдокод, так как вы не заметили, с каким языком вы работаете.

FUNCTION copyTreeByID (INTEGER id, INTEGER max_depth = 10, INTEGER parent_id = 0) 
    row = MYSQL_QUERY_ROW ("SELECT * FROM tree WHERE id=?", id) 
    IF NOT row 
    THEN 
     RETURN NULL 
    END IF 

    IF ! MYSQL_QUERY ("INSERT INTO trees (parent_id, type, name) VALUES (?, ?, ?)", parent_id, row["type"], row["name"]) 
    THEN 
     RETURN NULL 
    END IF 
    parent_id = MYSQL_LAST_INSERT_ID() 

    IF max_depth LESSTHAN 0 
    THEN 
     RETURN 
    END IF 

    rows = MYSQL_QUERY_ROWS ("SELECT id FROM trees WHERE parent_id=?", id) 
    FOR rows AS row 
     copyTreeByID (row["id"], max_depth - 1, parent_id) 
    END FOR 

    RETURN parent_id 
END FUNCTION 

FUNCTION copyTreeByTypeName (STRING type, STRING name) 
    row = MYSQL_QUERY_ROW ("SELECT id FROM tree WHERE parent_id=0 AND type=? AND name=?", type, name) 
    IF NOT ARRAY_LENGTH (row) 
    THEN 
     RETURN 
    END IF 
    RETURN copyTreeByID (row["id"]) 
END FUNCTION 

copyTreeByTypeName смотрит на дерево ID для сопоставления type и name и передает его copyTreeByID. Это главным образом функция утилиты, которая поможет вам скопировать материал по типу/имени.

copyTreeByID - настоящий зверь. Бойтесь этого, потому что он рекурсивный и злой. Почему он рекурсивный? Потому что ваши деревья не предсказуемы и могут быть любой глубиной. Но все в порядке, у нас есть переменная, чтобы отслеживать глубину и ограничивать ее (max_depth). Итак, давайте пройдем через это.

Начните с захвата всех данных для элемента. Если мы не получили никаких данных, просто вернитесь. Повторно вставьте данные с элементами type и name и переданными parent_id. Если запрос завершился неудачно, вернитесь. Установите parent_id на последний идентификатор вставки, чтобы мы могли передать его позже. Проверьте, что max_depth меньше нуля, что указывает на то, что мы достигли максимальной глубины; если мы вернемся. Возьмите все элементы из дерева, у которых есть родительский элемент id.Затем для каждого из этих элементов возвращайтесь в copyTreeByID, проезжая элемент id, max_depth минус 1 и новый parent_id. В конце возвращаем parent_id, чтобы вы могли получить доступ к новой копии элементов.

Имеют смысл? (Я прочитал его, и это имело смысл, а не то, что это значит).