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

StackOverflow https://stackoverflow.com/questions/38801

Вопрос

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

Это было полезно?

Решение

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

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

Другие советы

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

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

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

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

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

Здесь это хорошо объяснено:

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

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

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

Графики

Классы :

Вложенные наборы дерева базы данных Adodb

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

ГРУША::DB_NestedSet

ГРУША::Дерево

улицы

Как лучше всего представлять иерархию в базе данных 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] и использовал подход модели дерева вложенных множеств, упомянутый Таркуном из MySQL docs.

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

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

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

Общие табличные выражения (CTE) могут стать вашими друзьями, когда вы освоитесь с ними.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top