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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• http://www.sitepoint.com/article/hierarchical-data-database
• Управление иерархическими данными в MySQL
• http://www.evolt.org/article/Four_ways_to_work_with_hierarchical_data/17/4047/index.html

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

• http://en.wikipedia.org/wiki/Tree_%28data_structure%29
• http://en.wikipedia.org/wiki/Category:Trees_%28structure%29

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

• http://www.sqlteam.com/item.asp?ItemID=8866

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

• http://www.sqlsummit.com/AdjacencyList.htm
• http://www.edutech.ch/contribution/nstrees/index.php
• http://www.phpriot.com/d/articles/php/application-design/nested-trees-1/
• http://www.dbmsmag.com/9604d06.html
• http://en.wikipedia.org/wiki/Tree_traversal
• http://www.cosc.canterbury.ac.nz/mukundan/dsal/BTree.html (приложение java montrant le fonctionnement)

Графики

• http://www.artfulsoftware.com/mysqlbook/sampler/mysqled1ch20.html

Классы:

Вложенные наборы DB Tree Adodb

• http://www.phpclasses.org/browse/package/2547.html

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

• http://www.phpclasses.org/browse/package/2919.html

PEAR :: DB_NestedSet

• http://pear.php.net/package/DB_NestedSet
• использование: https://www.entwickler.com/itr/kolumnen/psecom,id,26,nodeid,207.html

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

• http://pear.php.net/package/Tree/download/0.3.0/
• http://www.phpkitchen.com/index.php?/archives/337-PEARTree-Tutorial.html

деревья

• http://www.edutech.ch/contribution/nstrees/index.php

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

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

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