Структура SQL дерева

Question

Я новичок в этой теме (я древовидная структура) в SQL. Я прошел через разные источники, но все еще не ясно.

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

Теперь вот первое, что я должен получить полное дерево для «OFFICE».

Также я должен найти все листовые узлы (без детей) в прикрепленных иерархических данных.

Просьба дать ответы с подробным объяснением. Спасибо заранее.

Answer 1

вы не указали свой СУБД, но со стандартным SQL (поддерживается всеми modern DBMS) вы можете легко сделать рекурсивный запрос, чтобы получить полное дерево:

with recursive full_tree as (
    select id, name, parent, 1 as level 
    from departments 
    where parent is null 
    union all 
    select c.id, c.name, c.parent, p.level + 1 
    from departments c 
    join full_tree p on c.parent = p.id 
) 
select * 
from full_tree; 

Если вам нужен поддерево, просто изменить начальное условие в общем выражении таблицы. Чтобы получить, например, все "категории":

with recursive all_categories as (
    select id, name, parent, 1 as level 
    from departments 
    where id = 2 --- << start with a different node 
    union all 
    select c.id, c.name, c.parent, p.level + 1 
    from departments c 
    join all_categories p on c.parent = p.id 
) 
select * 
from all_categories; 

Получение всех лаврового листа прост: это все узлы, где их ID не появляется как parent:

select * 
from departments 
where id not in (select parent 
       from departments 
       where parent is not null); 

SQLFiddle Например: http://sqlfiddle.com/#!15/414c9/1

---

Редактировать после того, как была определена СУБД.

Oracle поддерживает рекурсивные CTE (хотя для этого вам нужно 11.2.x) вам просто нужно оставить ключевое слово recursive.Но вы также можете использовать CONNECT BY оператор:

select id, name, parent, level 
from departments 
start with parent is null 
connect by prior id = parent; 

select id, name, parent, level 
from departments 
start with id = 2 
connect by prior id = parent; 

SQLFiddle для Oracle: http://sqlfiddle.com/#!4/6774ee/3

Смотрите детали в руководстве: https://docs.oracle.com/database/121/SQLRF/queries003.htm#i2053935

Answer 2

Теперь, во-первых, мне нужно получить полное дерево для «ОФИСА».

Как вы хотите представлять свое дерево? То, что вы опубликовали, уже может считаться деревом.

Также я должен найти все листовые узлы (без детей) в прикрепленных иерархических данных.

TSQL:

select * 
from table outer 
where id not in (select id 
       from table inner 
       where inner.parent = outer.id) 

Внутренний выбор даст вам все идентификаторы, указывающие на определенный родителя. Внешний выбор даст вам все узлы, для которых внутренний выбор не дает никаких результатов.

Answer 3

Существует шаблон, называемый «жестко закодированные деревья», который может быть полезен для этой цели.

Затем вы можете использовать этот запрос для поиска родителей для каждого ребенка

SELECT level1ID FROM Level2entity as L2 WHERE level2ID = :aLevel2ID 

Или этот для поиска детей для каждого родителя:

SELECT level1ID FROM Level2entity as L2 WHERE level2ID = :aLevel2ID 

Answer 4

Если вы можете позволить себе немного бит времени предварительной обработки, тогда классическим решением этой проблемы будет использование nested sets.

CREATE TABLE node (
    id INTEGER NOT NULL PRIMARY KEY, 
    name VARCHAR(255) NOT NULL, 
    parent_id INTEGER DEFAULT NULL, 
    seq_min INTEGER NOT NULL, 
    seq_max INTEGER NOT NULL 
); 

Предполагая, что вы используете какой-то структуры данных в памяти, как

class Node: 
    def __init__(self, id, name, children=()): 
     self.id = id 
     self.name = name 
     self.children = list(children) 

представляют узлы дерева в памяти, мы можем определить

def assign_sequence_numbers(root_node): 
    def recurse(counter, node): 
     node.seq_min = counter 
     node.seq_max = reduce(recurse, node.children, 1 + counter) 
     return node.seq_max 
    return recurse(1, root_node) 

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

seq_min Значение становится альтернативным уникальным целым ключом для каждого узла. Кроме того, все прямые дочерние элементы (и непрямые потомки) узла будут иметь значение seq_min, которое больше, чем значение, присвоенное самому узлу.

Значение seq_max - это просто верхняя граница для значений seq_min всех узлов-потомков.

Пример: Рассмотрим следующее дерево

Root 
| 
+--- Category1 
|  | 
|  +--- Category1.1 
|  | 
|  `--- Category1.2 
| 
`--- Category2 

Используя функцию, определенную выше, мы получаем

Root [min=1, max=6] 
| 
+--- Category1 [min=2, max=5] 
|  | 
|  +--- Category1.1 [min=3, max=4] 
|  | 
|  `--- Category1.2 [min=4, max=5] 
| 
`--- Category2 [min=5, max=6] 

Заметим, что для каждого узла, значение min всегда < = значение min все потомки и значение max всегда > максимальное значение всех потомков. Таким образом, чтобы найти потомок Root и что сами (то есть, получить все дерево) узел, мы делаем:

SELECT * FROM node 
WHERE seq_min >= 1 /* i.e., seq_min(Root) */ 
AND seq_min < 6 /* i.e., seq_max(Root) */ 

Чтобы получить потомок category1 (и что сам узел)

SELECT * FROM node 
WHERE seq_min >= 2 /* i.e., seq_min(Category1) */ 
AND seq_min < 5 /* i.e., seq_max(Category2) */ 

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

Поскольку ITGenius уже связан с that answer: если ваша база данных поддерживает его, использование общих табличных выражений - это еще одна возможность, которая позволяет избежать этапа предварительной обработки и также более устойчива перед изменениями в древовидной структуре.

(я не проверял какого-либо кода, приведенной в этом ответе Вы, возможно, потребуется применить несколько исправлений здесь и там;., В частности, если язык вашего проекта выбора является не питон ...)