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

Question

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

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

Мне нужен найти С и Е (две глубоких узлов каждая уникальная ветвь, AC и AE)

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

можно исключить все узлы листьев (RGT = LFT + 1) и корневой узел (LFT = 1) , который оставляет меня с BE 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| 

Благодарим за помощь!

Answer 1

Вы правы, первый шаг состоит в том, чтобы идентифицировать узлы листа через их право собственности равным слева + 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 
        ) 
     )