Подтвердить что ты не робот

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

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

4b9b3361

ОТВЕТЫ

Ответ 1

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

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

Ответ 2

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

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

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

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

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

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

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

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

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

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

Классы:

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

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

PEAR:: DB_NestedSet

PEAR:: Дерево

nstrees

Ответ 3

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

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

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 subsuqeries.

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

Ответ 4

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

Этот запрос (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;

Ответ 5

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

Ответ 6

Oracle: SELECT... START WITH... CONNECT BY

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

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

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

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

Ответ 7

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

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

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

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

Ответ 8

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

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

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

Ответ 9

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

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