SQL - Как хранить иерархии и перемещаться по ним?
-
09-06-2019 - |
Вопрос
Какие способы вы используете для моделирования и извлечения иерархической информации в базе данных?
Решение
Окончательные материалы на эту тему были написаны Джо Селко, и он превратил ряд из них в книгу под названием «Деревья и иерархии Джо Селко в SQL для умных людей».
Он предпочитает технику, называемую ориентированными графами. Введение в его работу на эту тему можно найти здесь
Другие советы
Мне нравится Модифицированный Алгоритм обхода дерева предварительных заказов.Этот метод позволяет очень легко запрашивать дерево.
Но вот список ссылок по теме, который я скопировал с веб-страницы участников Zend Framework (PHP) (размещен там автором Laurent Melmoux в Jun 05, 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.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 (applet java montrant le fonctionnement )
Графики
Классы :
Вложенные наборы дерева базы данных Adodb
Модель посещения ADOdb
ГРУША::DB_NestedSet
- http://pear.php.net/package/DB_NestedSet
- utilisation : 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
улицы
Как лучше всего представлять иерархию в базе данных 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;
Я предпочитаю сочетание техничек, используемых Джошем и Марком Харрисоном:
Две таблицы, одна с данными 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) могут стать вашими друзьями, когда вы освоитесь с ними.