SQL - Как хранить и перемещаться по иерархиям?

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

Источник

9 ответов

Решение

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

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

Источник

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

Но вот список ссылок на эту тему, которые я скопировал с веб-страницы разработчиков Zend Framework (PHP) (размещено там Автором: Laurent Melmoux, 05 июня 2007 г., 15:52).

Многие из ссылок не зависят от языка:

Существует 2 основных представления и алгоритмы для представления иерархических структур с базами данных:

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

Это хорошо объяснено здесь:

Вот еще несколько ссылок, которые я собрал:

модель списка смежности

вложенный набор

в виде графиков

Классы:

Вложенные множества DB Tree Adodb

Модель посещения ADOdb

PEAR:: DB_NestedSet

PEAR:: Дерево

nstrees

Источник

Каков наилучший способ представить иерархию в базе данных SQL? Общая портативная техника?

Давайте предположим, что иерархия в основном читается, но не полностью статична. Допустим, это семейное древо.

Вот как этого не сделать:

create table person (
person_id integer autoincrement primary key,
name      varchar(255) not null,
dob       date,
mother    integer,
father    integer
);

И вставляя данные так:

person_id   name      dob       mother father  
1           Pops      1900/1/1   null   null  
2           Grandma   1903/2/4   null   null  
3           Dad       1925/4/2   2      1  
4           Uncle Kev 1927/3/3   2      1
5           Cuz Dave  1953/7/8   null   4
6           Billy     1954/8/1   null   3

Вместо этого разделите ваши узлы и ваши отношения на две таблицы.

create table person (
person_id integer autoincrement primary key,
name      varchar(255) not null,
dob       date
);

create table ancestor (
ancestor_id   integer,
descendant_id integer,
distance      integer
);

Данные создаются так:

person_id   name      dob       
1           Pops      1900/1/1  
2           Grandma   1903/2/4   
3           Dad       1925/4/2   
4           Uncle Kev 1927/3/3
5           Cuz Dave  1953/7/8   
6           Billy     1954/8/1   

ancestor_id  descendant_id  distance
1            1              0
2            2              0
3            3              0
4            4              0
5            5              0
6            6              0
1            3              1
2            3              1
1            4              1
2            4              1
1            5              2
2            5              2
4            5              1
1            6              2
2            6              2
3            6              1

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

У кого есть бабушка и дедушка?

select * from person where person_id in 
    (select descendant_id from ancestor where distance=2);

Все ваши потомки:

select * from person where person_id in 
    (select descendant_id from ancestor 
    where ancestor_id=1 and distance>0);

Кто такие дяди?

select decendant_id uncle from ancestor 
    where distance=1 and ancestor_id in 
    (select ancestor_id from ancestor 
        where distance=2 and not exists
        (select ancestor_id from ancestor 
        where distance=1 and ancestor_id=uncle)
    )

Вы избегаете всех проблем присоединения таблицы к себе через подзапросы, общее ограничение - 16 подзапросов.

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

Источник

Я должен не согласиться с Джошем. Что произойдет, если вы используете огромную иерархическую структуру, такую ​​как организация компании. Люди могут присоединиться к компании или покинуть ее, изменить линии отчетности и т. Д. Поддержание "расстояния" будет большой проблемой, и вам придется вести две таблицы данных.

Этот запрос (SQL Server 2005 и более поздние версии) позволит вам увидеть полную строку любого человека И рассчитать их место в иерархии, и для него требуется только одна таблица информации о пользователе. Его можно изменить, чтобы найти любые дочерние отношения.

--Create table of dummy data
create table #person (
personID integer IDENTITY(1,1) NOT NULL,
name      varchar(255) not null,
dob       date,
father    integer
);

INSERT INTO #person(name,dob,father)Values('Pops','1900/1/1',NULL);  
INSERT INTO #person(name,dob,father)Values('Grandma','1903/2/4',null);
INSERT INTO #person(name,dob,father)Values('Dad','1925/4/2',1);
INSERT INTO #person(name,dob,father)Values('Uncle Kev','1927/3/3',1);
INSERT INTO #person(name,dob,father)Values('Cuz Dave','1953/7/8',4);
INSERT INTO #person(name,dob,father)Values('Billy','1954/8/1',3);

DECLARE @OldestPerson INT; 
SET @OldestPerson = 1; -- Set this value to the ID of the oldest person in the family

WITH PersonHierarchy (personID,Name,dob,father, HierarchyLevel) AS
(
   SELECT
      personID
      ,Name
      ,dob
      ,father,
      1 as HierarchyLevel
   FROM #person
   WHERE personID = @OldestPerson

   UNION ALL

   SELECT
    e.personID,
      e.Name,
      e.dob,
      e.father,
      eh.HierarchyLevel + 1 AS HierarchyLevel
   FROM #person e
      INNER JOIN PersonHierarchy eh ON
         e.father = eh.personID
)

SELECT *
FROM PersonHierarchy
ORDER BY HierarchyLevel, father;

DROP TABLE #person;
Источник

К сведению: SQL Server 2008 вводит новый тип данных HierarchyID для такого рода ситуаций. Дает вам контроль над тем, где в "дереве" сидит ваш ряд, как горизонтально, так и вертикально.

Источник

Oracle: ВЫБРАТЬ... НАЧАТЬ С... ПОДКЛЮЧИТЬ ПО

Oracle имеет расширение SELECT, которое позволяет легко извлекать данные на основе дерева. Возможно, SQL Server имеет какое-то подобное расширение?

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

select * from my_table
    start with parent = :TOP
    connect by prior child = parent;

http://www.adp-gmbh.ch/ora/sql/connect_by.html

Источник

Я предпочитаю сочетание техник, используемых Джошем и Марком Харрисоном:

Две таблицы, одна с данными Person и другая с иерархической информацией (person_id, parent_id [, mother_id]), если PK этой таблицы - person_id, у вас есть простое дерево только с одним родителем по узлу (что имеет смысл в в этом случае, но не в других случаях, как бухгалтерские счета)

Эта таблица hiarchy может быть пересечена с помощью рекурсивных процедур или если ваша БД поддерживает ее предложениями типа SELECT... BY PRIOR (Oracle).

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

Источник

У нас возникла та же проблема, когда мы реализовали компонент дерева для [fleXive] и использовали подход модели дерева вложенных множеств, упомянутый tharkun из документации MySQL.

В дополнение к ускорению (значительно) мы использовали расширенный подход, который просто означает, что мы использовали максимальное значение Long для правых границ верхнего уровня, что позволяет нам вставлять и перемещать узлы без пересчета всех левых и правых значений. Значения для левого и правого каналов рассчитываются путем деления диапазона для узла на 3 и использования внутренней трети в качестве границ для нового узла.

Пример кода Java можно увидеть здесь.

Источник

Если вы используете SQL Server 2005, то по этой ссылке объясняется, как получить иерархические данные.

Common Table Expressions (CTE) могут стать вашими друзьями, когда вы освоитесь с ними.

Источник
Другие вопросы по тегам