Модель вложенного набора в SQL - как найти самых глубоких родителей (не конечных узлов) каждой ветви - PullRequest
Новая
       3

Модель вложенного набора в SQL - как найти самых глубоких родителей (не конечных узлов) каждой ветви

2 голосов
/ 10 февраля 2011

Учитывая дерево, как это: 

A----B---------C----D
     |         |
     E----F    G
     |
     H

Мне нужно найти C и E (два самых глубоких узла каждой уникальной ветви; A-C и A-E)

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

Я могу исключить все листовые узлы (rgt = lft + 1) и корневой узел (lft = 1) что оставляет меня с B E C. Как вы можете себе представить, это очень упрощенный пример, некоторые из наших деревьев имеют более 100 узлов. Как я могу избавиться от этого шума в моих данных?

Вот данные для примера выше, если они были сохранены в нашей базе данных. 

 node | parent | lft | rgt |
------+--------+-----+-----+
   A  |  NULL  |    1|   16|
   B  |    A   |    2|   15|
   E  |    B   |    3|    8|
   F  |    E   |    4|    5|
   H  |    E   |    6|    7|
   C  |    B   |    9|   14|
   D  |    C   |   10|   11|
   G  |    C   |   12|   13|

Спасибо за вашу помощь!

1 Ответ

0 голосов
/ 28 сентября 2017

Вы правы, первый шаг состоит в том, чтобы идентифицировать конечные узлы через их свойство right, равное left + 1. Следующий шаг - найти все родительские узлы для этих конечных узлов: у них слева меньше, чем у листа прямо больше, чем у листа. И последний шаг - исключить всех родителей, кроме того, который имеет наибольшее левое значение (т. Е. Находится ближе всего к конечному узлу).

Пример в T-SQL, где l - это листовой узел, p1 - прямой родитель, которого мы ищем, а p2 используется для отсеивания всех непрямых родителей.

Сначала создайте тестовую таблицу с данными вашего примера: 

if object_id('tempdb..#nsm') is not null
    drop table #nsm;

select v.node, v.parent, v.lft, v.rgt
into #nsm
from (
    values 
       ('A'  ,     NULL,     1,   16),
       ('B'  ,    'A'   ,    2,   15),
       ('E'  ,    'B'   ,    3,    8),
       ('F'  ,    'E'   ,    4,    5),
       ('H'  ,    'E'   ,    6,    7),
       ('C'  ,    'B'   ,    9,   14),
       ('D'  ,    'C'   ,   10,   11),
       ('G'  ,    'C'   ,   12,   13)
   ) v (node, parent, lft, rgt)

А вот запрос, который возвращает оба запрошенных узла C и E: 

select p1.node, p1.parent, p1.lft, p1.rgt
from #nsm p1
where exists (
            select *
            from #nsm l
            where l.rgt = l.lft + 1
                and p1.lft < l.lft
                and p1.rgt > l.rgt
                and not exists (
                        select *
                        from #nsm p2
                        where p2.lft < l.lft
                            and p2.rgt > l.rgt
                            and p2.lft > p1.lft
                    )
        )
...