Как выполнить запрос для всех узлов между двумя узлами в дереве?

Question

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

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

**ANCESTOR, DESCENDANT** 
grantparent, parent 
grandparent, grandchild 
parent, grandchild 

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

Мой вопрос заключается в том, что, используя эту плоскую таблицу, как я могу наиболее эффективно возвращать все записи, которые находятся между двумя узлами. Используя пример, с grandparent и grandchild в качестве моих параметров, как я могу вернуть запись (grandparent, parent).

Я не хочу использовать иерархический запрос для решения этой проблемы ... Мне интересно, можно ли сделать это без каких-либо объединений.

Answer 1

SELECT * 
FROM mytable 
WHERE descendant = @descendant 
     AND hops < 
     (
     SELECT hops 
     FROM mytable 
     WHERE descendant = @descendant 
       AND ancestor = @ancestor 
     ) 

Это будет автоматически заботиться о тех случаях, когда @ancestor это на самом деле не предок @descendant «s.

Создайте индекс на (descendant, hops), чтобы работать быстро.

Answer 2

Try:

select h1.descendant intermediate_node 
from hierarchy h0 
join hierarchy h1 
    on h0.ancestor = h1.ancestor 
and h0.hops > h1.hops -- redundant condition, but may improve performance 
join hierarchy h2 
    on h1.ancestor = h2.ancestor 
and h0.descendant = h2.descendant 
where h0.ancestor = :ancestor and h0.descendant = :descendant 

Answer 3

SELECT 
    distinct ancestor 
FROM 
    hierarchy 
WHERE descendant = :1 AND 
     ancestor IN (
        SELECT 
         distinct descendant 
        FROM 
         hierarchy WHERE ancestor = :2 
       )