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

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

Несколько столбцов происхождения

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

• Столбцы: по одному для каждого уровня происхождения, относится ко всем родителям до корня, уровни ниже текущего уровня элементов устанавливаются на 0 (или 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                   |

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

Модель смежности + модель вложенных наборов

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

+-------------+----------------------+--------+-----+-----+
| 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 между lft и rgt родительского элемента.
• Если вам нужны все родители любого узла до корня дерева, вы запрашиваете элементы, имеющие lft ниже, чем lft узла и rgt, больше, чем узел rgt и сортируете по parent.

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

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

Я использую 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;
$$;

Таблицы замыкания определены с 3 столбцами - 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;

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

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

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

Рассматривайте спецификацию материалов как общую иерархическую структуру данных.

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

class PartOf extends Edge {
};

class AdjacentTo extends Edge {
};

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

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

Переходное замыкание : пройдитесь по поддереву и просуммируйте интересующие поля, например «Сколько алюминия в узле?»

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

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

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

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

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

Проблема до сих пор заключалась в том, что метод прикрытия из списка смежности во вложенные наборы был ужасно медленным, потому что большинство людей использовали экстремальный метод RBAR, известный как «Push Stack», для преобразования и считался Дорогое удовольствие достичь Нирваны простоты обслуживания с помощью списка смежности и потрясающей производительности вложенных наборов. В результате большинству людей приходится довольствоваться тем или другим, особенно если количество узлов превышает, скажем, 100 000 паршивых узлов или около того. Использование метода push-стека может занять целый день, чтобы выполнить преобразование того, что MLM-специалисты считают иерархией из нескольких миллионов узлов.

Я подумал, что дам Celko немного посоревноваться, придумав метод преобразования списка смежности во вложенные наборы на скоростях, которые просто кажутся невозможными. Вот производительность метода push-стека на моем ноутбуке i5.

Duration for     1,000 Nodes = 00:00:00:870 
Duration for    10,000 Nodes = 00:01:01:783 (70 times slower instead of just 10)
Duration for   100,000 Nodes = 00:49:59:730 (3,446 times slower instead of just 100) 
Duration for 1,000,000 Nodes = 'Didn't even try this'

А вот продолжительность нового метода (с методом push stack в скобках).

Duration for     1,000 Nodes = 00:00:00:053 (compared to 00:00:00:870)
Duration for    10,000 Nodes = 00:00:00:323 (compared to 00:01:01:783)
Duration for   100,000 Nodes = 00:00:03:867 (compared to 00:49:59:730)
Duration for 1,000,000 Nodes = 00:00:54:283 (compared to something like 2 days!!!)

Да, верно. 1 миллион узлов преобразован менее чем за минуту и ​​100 000 узлов менее чем за 4 секунды.

Вы можете прочитать о новом методе и получить копию кода по следующему URL-адресу. http://www.sqlservercentral.com/articles/Hierarchy/94040/

Я также разработал «предварительно агрегированную» иерархию, используя аналогичные методы. Эта статья особенно заинтересует пользователей MLM и тех, кто составляет ведомости материалов. http://www.sqlservercentral.com/articles/T-SQL/94570/

Если вы все же зайдете, чтобы взглянуть на любую статью, перейдите по ссылке «Присоединиться к обсуждению» и дайте мне знать, что вы думаете.

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

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

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

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