sql создание - Каковы варианты хранения иерархических данных в реляционной базе данных?




бд основе (7)

Хорошие обзоры

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

Опции

Я знаю и общие особенности:

  1. Список аджанс :
    • Столбцы: ID, ParentID
    • Легко реализуется.
    • Дешевые узлы перемещаются, вставляются и удаляются.
    • Дорого, чтобы найти уровень, родословную и потомки, путь
    • Избегайте N + 1 через общие табличные выражения в базах данных, которые их поддерживают
  2. Вложенный набор (также измененный обход дерева предзаказов )
    • Столбцы: влево, вправо
    • Дешевая родословная, потомки
    • Очень дорогое O(n/2) перемещает, вставляет, удаляет из-за изменчивого кодирования
  3. Таблица моста (aka Closure Table / w триггеры )
    • Использует отдельную таблицу соединений с: предком, потомком, глубиной (необязательно)
    • Дешевая родословная и потомки
    • Записывает затраты O(log n) (размер поддерева) для вставки, обновления, удаления
    • Нормализованное кодирование: полезно для статистики РСУБД и планировщика запросов в соединениях
    • Требует несколько строк на узел
  4. Столбец Lineage (также называемый Materialized Path , Path Enumeration)
    • Колонка: lineage (например, / parent / child / grandchild / etc ...)
    • Дешевые потомки через префиксный запрос (например, LEFT(lineage, #) = '/enumerated/path' )
    • Записывает затраты O(log n) (размер поддерева) для вставки, обновления, удаления
    • Non-relational: полагается на тип данных Array или последовательный формат строки
  5. Вложенные интервалы
    • Как вложенный набор, но с real / float / decimal, чтобы кодировка не была изменчивой (недорогой move / insert / delete)
    • Имеет реальные / плавающие / десятичные представления / точность
    • Матричный вариант кодирования добавляет кодирование предка (материализованный путь) для «свободного», но с добавленной хитростью линейной алгебры.
  6. Плоский стол
    • Измененный список смежности, который добавляет столбец уровня и ранга (например, упорядочение) к каждой записи.
    • Дешево для итерации / paginate
    • Дорогой ход и удаление
    • Хорошее использование: обсуждение темы - форумы / комментарии в блоге
  7. Несколько столбцов линии
    • Столбцы: по одному для каждого уровня линии, относятся ко всем родителям до корня, уровни вниз от уровня элемента равны NULL
    • Дешевые предки, потомки, уровень
    • Дешевая вставка, удаление, перемещение листьев
    • Дорогое вставка, удаление, перемещение внутренних узлов
    • Жесткий предел того, насколько глубока иерархия

Специфические примечания к базе данных

MySQL

оракул

  • Используйте CONNECT BY для перемещения списков Adjacency

PostgreSQL

SQL Server

  • Общее резюме
  • 2008 предлагает тип данных HierarchyId , который помогает с помощью подхода Lineage Column и расширяет глубину, которая может быть представлена.

Answers

Я использую PostgreSQL с закрытыми таблицами для своих иерархий. У меня есть одна универсальная хранимая процедура для всей базы данных:

CREATE FUNCTION nomen_tree() RETURNS trigger
    LANGUAGE plpgsql
    AS $_$
DECLARE
  old_parent INTEGER;
  new_parent INTEGER;
  id_nom INTEGER;
  txt_name TEXT;
BEGIN
-- TG_ARGV[0] = name of table with entities with PARENT-CHILD relationships (TBL_ORIG)
-- TG_ARGV[1] = name of helper table with ANCESTOR, CHILD, DEPTH information (TBL_TREE)
-- TG_ARGV[2] = name of the field in TBL_ORIG which is used for the PARENT-CHILD relationship (FLD_PARENT)
    IF TG_OP = 'INSERT' THEN
    EXECUTE 'INSERT INTO ' || TG_ARGV[1] || ' (child_id,ancestor_id,depth) 
        SELECT $1.id,$1.id,0 UNION ALL
      SELECT $1.id,ancestor_id,depth+1 FROM ' || TG_ARGV[1] || ' WHERE child_id=$1.' || TG_ARGV[2] USING NEW;
    ELSE                                                           
    -- EXECUTE does not support conditional statements inside
    EXECUTE 'SELECT $1.' || TG_ARGV[2] || ',$2.' || TG_ARGV[2] INTO old_parent,new_parent USING OLD,NEW;
    IF COALESCE(old_parent,0) <> COALESCE(new_parent,0) THEN
      EXECUTE '
      -- prevent cycles in the tree
      UPDATE ' || TG_ARGV[0] || ' SET ' || TG_ARGV[2] || ' = $1.' || TG_ARGV[2]
        || ' WHERE id=$2.' || TG_ARGV[2] || ' AND EXISTS(SELECT 1 FROM '
        || TG_ARGV[1] || ' WHERE child_id=$2.' || TG_ARGV[2] || ' AND ancestor_id=$2.id);
      -- first remove edges between all old parents of node and its descendants
      DELETE FROM ' || TG_ARGV[1] || ' WHERE child_id IN
        (SELECT child_id FROM ' || TG_ARGV[1] || ' WHERE ancestor_id = $1.id)
        AND ancestor_id IN
        (SELECT ancestor_id FROM ' || TG_ARGV[1] || ' WHERE child_id = $1.id AND ancestor_id <> $1.id);
      -- then add edges for all new parents ...
      INSERT INTO ' || TG_ARGV[1] || ' (child_id,ancestor_id,depth) 
        SELECT child_id,ancestor_id,d_c+d_a FROM
        (SELECT child_id,depth AS d_c FROM ' || TG_ARGV[1] || ' WHERE ancestor_id=$2.id) AS child
        CROSS JOIN
        (SELECT ancestor_id,depth+1 AS d_a FROM ' || TG_ARGV[1] || ' WHERE child_id=$2.' 
        || TG_ARGV[2] || ') AS parent;' USING OLD, NEW;
    END IF;
  END IF;
  RETURN NULL;
END;
$_$;

Тогда для каждой таблицы, где у меня есть иерархия, я создаю триггер

CREATE TRIGGER nomenclature_tree_tr AFTER INSERT OR UPDATE ON nomenclature FOR EACH ROW EXECUTE PROCEDURE nomen_tree('my_db.nomenclature', 'my_db.nom_helper', 'parent_id');

Для заполнения таблицы закрытия из существующей иерархии я использую эту хранимую процедуру:

CREATE FUNCTION rebuild_tree(tbl_base text, tbl_closure text, fld_parent text) RETURNS void
    LANGUAGE plpgsql
    AS $$
BEGIN
    EXECUTE 'TRUNCATE ' || tbl_closure || ';
    INSERT INTO ' || tbl_closure || ' (child_id,ancestor_id,depth) 
        WITH RECURSIVE tree AS
      (
        SELECT id AS child_id,id AS ancestor_id,0 AS depth FROM ' || tbl_base || '
        UNION ALL 
        SELECT t.id,ancestor_id,depth+1 FROM ' || tbl_base || ' AS t
        JOIN tree ON child_id = ' || fld_parent || '
      )
      SELECT * FROM tree;';
END;
$$;

Таблицы закрытия определяются тремя столбцами: ANCESTOR_ID, DESCENDANT_ID, DEPTH. Возможно (и я даже совет) хранить записи с одинаковым значением для ANCESTOR и DESCENDANT, а также значение нуля для DEPTH. Это упростит запросы для поиска иерархии. И они очень просты:

-- get all descendants
SELECT tbl_orig.*,depth FROM tbl_closure LEFT JOIN tbl_orig ON descendant_id = tbl_orig.id WHERE ancestor_id = XXX AND depth <> 0;
-- get only direct descendants
SELECT tbl_orig.* FROM tbl_closure LEFT JOIN tbl_orig ON descendant_id = tbl_orig.id WHERE ancestor_id = XXX AND depth = 1;
-- get all ancestors
SELECT tbl_orig.* FROM tbl_closure LEFT JOIN tbl_orig ON ancestor_id = tbl_orig.id WHERE descendant_id = XXX AND depth <> 0;
-- find the deepest level of children
SELECT MAX(depth) FROM tbl_closure WHERE ancestor_id = XXX;

Если ваша база данных поддерживает массивы, вы также можете реализовать столбец строки или материализованный путь как массив идентификаторов родительских элементов.

В частности, с помощью Postgres вы можете использовать операторы set для запроса иерархии и получить отличную производительность с индексами GIN. Это позволяет найти родителей, детей и глубину довольно тривиально в одном запросе. Обновления довольно управляемы.

У меня есть полная запись использования массивов для материализованных путей, если вам интересно.


Модель Adjacency Model + Вложенные модели

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

+-------------+----------------------+--------+-----+-----+
| category_id | name                 | parent | lft | rgt |
+-------------+----------------------+--------+-----+-----+
|           1 | ELECTRONICS          |   NULL |   1 |  20 |
|           2 | TELEVISIONS          |      1 |   2 |   9 |
|           3 | TUBE                 |      2 |   3 |   4 |
|           4 | LCD                  |      2 |   5 |   6 |
|           5 | PLASMA               |      2 |   7 |   8 |
|           6 | PORTABLE ELECTRONICS |      1 |  10 |  19 |
|           7 | MP3 PLAYERS          |      6 |  11 |  14 |
|           8 | FLASH                |      7 |  12 |  13 |
|           9 | CD PLAYERS           |      6 |  15 |  16 |
|          10 | 2 WAY RADIOS         |      6 |  17 |  18 |
+-------------+----------------------+--------+-----+-----+
  • Каждый раз, когда вам нужны все дети любого родителя, вы просто запрашиваете parent столбец.
  • Если вам нужны все потомки любого родителя, вы запрашиваете элементы, у которых их lft между rgt и rgt родителя.
  • Если вам нужны все родители любого узла до корня дерева, вы запрашиваете для элементов, имеющих на lft меньше, чем rgt узла и rgt больше, чем rgt узла, и rgt их по parent .

Мне нужно было делать доступ и запрашивать дерево быстрее, чем вставки, поэтому я выбрал это

Единственная проблема - исправить left и right столбцы при вставке новых элементов. я создал для него хранимую процедуру и вызвал ее каждый раз, когда я вставил новый элемент, который был редок в моем случае, но он очень быстро. Я получил идею из книги Джо Селко, а хранимая процедура и то, как я ее придумал, объясняется здесь в DBA SE https://dba.stackexchange.com/q/89051/41481


Это очень частый ответ на ваш вопрос, но я надеюсь, что он еще полезен.

Microsoft SQL Server 2008 реализует две функции, которые чрезвычайно полезны для управления иерархическими данными:

  • тип данных HierarchyId .
  • общие выражения таблицы, используя ключевое слово.

Взгляните на «Моделировать свои иерархии данных с SQL Server 2008» от Kent Tegels на MSDN для запуска. См. Также мой собственный вопрос: рекурсивный запрос с одной таблицей в SQL Server 2008


Этот дизайн еще не упоминался:

Несколько столбцов линии

Хотя у этого есть ограничения, если вы можете их вынести, это очень просто и очень эффективно. Особенности:

  • Столбцы: по одному для каждого уровня линии относятся все родители до корня, уровни ниже уровня текущих предметов установлены в NULL
  • Ограничьте, насколько глубока иерархия
  • Дешевые предки, потомки, уровень
  • Дешевая вставка, удаление, перемещение листьев
  • Дорогое вставка, удаление, перемещение внутренних узлов

Вот пример - таксономическое дерево птиц, поэтому иерархия - это класс / порядок / семья / род / вид - вид - самый низкий уровень, 1 ряд = 1 таксон (что соответствует видам в случае листовых узлов):

CREATE TABLE `taxons` (
  `TaxonId` smallint(6) NOT NULL default '0',
  `ClassId` smallint(6) default NULL,
  `OrderId` smallint(6) default NULL,
  `FamilyId` smallint(6) default NULL,
  `GenusId` smallint(6) default NULL,
  `Name` varchar(150) NOT NULL default ''
);

и пример данных:

+---------+---------+---------+----------+---------+-------------------------------+
| TaxonId | ClassId | OrderId | FamilyId | GenusId | Name                          |
+---------+---------+---------+----------+---------+-------------------------------+
|     254 |       0 |       0 |        0 |       0 | Aves                          |
|     255 |     254 |       0 |        0 |       0 | Gaviiformes                   |
|     256 |     254 |     255 |        0 |       0 | Gaviidae                      |
|     257 |     254 |     255 |      256 |       0 | Gavia                         |
|     258 |     254 |     255 |      256 |     257 | Gavia stellata                |
|     259 |     254 |     255 |      256 |     257 | Gavia arctica                 |
|     260 |     254 |     255 |      256 |     257 | Gavia immer                   |
|     261 |     254 |     255 |      256 |     257 | Gavia adamsii                 |
|     262 |     254 |       0 |        0 |       0 | Podicipediformes              |
|     263 |     254 |     262 |        0 |       0 | Podicipedidae                 |
|     264 |     254 |     262 |      263 |       0 | Tachybaptus                   |

Это здорово, потому что таким образом вы выполняете все необходимые операции очень просто, если внутренние категории не меняют свой уровень в дереве.


Это действительно квадратный вопрос, круглый вопрос.

Если реляционные базы данных и SQL - единственный молот, который у вас есть или который готов, то ответы, которые были опубликованы до сих пор, являются адекватными. Однако почему бы не использовать инструмент, предназначенный для обработки иерархических данных? Графическая база данных идеально подходит для сложных иерархических данных.

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

Рассмотрите Билль материалов как общую иерархическую структуру данных.

class Component extends Vertex {
    long assetId;
    long partNumber;
    long material;
    long amount;
};

class PartOf extends Edge {
};

class AdjacentTo extends Edge {
};

Самый короткий путь между двумя подсборками : простой алгоритм обхода графика. Допустимые пути могут быть квалифицированы на основе критериев.

Сходство : Какова степень сходства между двумя сборками? Выполните обход на обоих поддеревах, вычисляя пересечение и объединение двух поддеревьев. Процент подобный - это пересечение, разделенное союзом.

Transitive Closure : Пройдите подэлемент и суммируйте интересующее поле (например): «Сколько алюминия в сборе?»

Да, вы можете решить проблему с SQL и реляционной базой данных. Тем не менее, есть намного лучшие подходы, если вы готовы использовать правильный инструмент для работы.


Вы можете сделать это, добавив псевдо-столбец с именем rank к каждому элементу, который вы можете сортировать сначала, прежде чем сортировать по другим критериям, например:

select *
from (
    select 1 as Rank, id, add_date from Table 
    union all
    select 2 as Rank, id, add_date from Table where distance < 5
    union all
    select 3 as Rank, id, add_date from Table where distance between 5 and 15
) a
order by rank, id, add_date desc




sql database tree relational-database hierarchical-data