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

Ответ 1

Это вопрос, который по-прежнему интересен даже после того, как все крупные три поставщика внедрили рекурсивное предложение WITH. Я бы предположил, что разные читатели будут довольны разными ответами.

• Полный список ссылок Troels Arvin.
• Из-за отсутствия конкуренции вступительный учебник Джо Селко "Деревья и иерархии в SQL для Smarties" действительно можно считать классикой.
• Обзор различных кодировок деревьев с акцентом на вложенные интервалы.

Ответ 2

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

Проблема до сих пор заключалась в том, что метод coversion из списка Adjacecy для вложенных наборов был ужасно медленным, потому что большинство людей используют экстремальный метод RBAR, известный как "Push Stack", чтобы сделать преобразование и считалось путь к дорогому достижению Nirvana простоты обслуживания в списке Adjacency и потрясающей производительности вложенных наборов. В результате большинство людей вынуждены довольствоваться тем или иным, особенно если есть более чем, скажем, паршивые 100 000 узлов или около того. Использование метода push-стека может занять целый день, чтобы сделать преобразование на то, что MLM'ers считают небольшой миллионом иерархии node.

Я думал, что дам Celko немного конкуренции, придумав метод преобразования списка Adjacency List в Nested на скорости, которые просто кажутся невозможными. Здесь производительность метода 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'ers и люди, делающие законопроекты, будут особенно заинтересованы в этой статье. http://www.sqlservercentral.com/articles/T-SQL/94570/

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

Ответ 3

Некоторые статьи из моего блога по теме:

• Список привязанностей к вложенным наборам: MySQL
• Список привязанностей к вложенным наборам: PostgreSQL
• Список привязанностей к вложенным наборам: Oracle

• Список привязанностей к вложенным наборам: SQL Server

• Иерархические запросы в MySQL (запрос списков смежности в MySQL)

Ответ 4

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

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

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

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

Ответ 5

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

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

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

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

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

Ответ 6

Джо Целько написал книгу о деревьях SQL и Hiearichies

Это первое издание. Посмотрите на второе издание в комментарии Боба.

Ответ 7

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

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

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

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

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

Ответ 8

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

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

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

Ответ 9

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

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

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

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

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

class PartOf extends Edge {
};

class AdjacentTo extends Edge {
};

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

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

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

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

Ответ 10

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

Ответ 11

Для более сложных иерархий, таких как дерево LDAP, архитектура кластера OpenLDAP-MySQL была представлена ​​на пользовательской конференции MySQL в 2009 году.

http://en.oreilly.com/mysql2009/public/schedule/detail/6219

Это очень похоже на схему "Несколько столбцов линии", показанную выше.

Ответ 12

Вот отличный пример моего личного фаворита, таблицы Bridge (или таблицы закрытия).