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

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

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

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

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

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

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


sql hierarchical-data hierarchical-trees hierarchical-query transitive-closure-table
person aw crud    schedule 03.11.2010    source источник
comment
Предположительно ваши реальные иерархии не ограничиваются тремя уровнями?   -  person Ed Harper    schedule 03.11.2010
comment
@Renderln, включает ли ваша плоская таблица только столбцы Ancestor и Descendant, или есть другие столбцы (например, количество поколений/уровней)? Кроме того, может ли быть несколько способов связать одного потомка с одним и тем же предком?   -  person    schedule 03.11.2010
comment
@Ed Harper: Да, эта таблица содержит несколько иерархий разных уровней.   -  person aw crud    schedule 03.11.2010
comment
@Mark Bannister: каждая запись содержит количество прыжков, на которых узлы-предки и потомки отделены друг от друга. Он также указывает корневой узел для этой иерархии. Он не содержит общей высоты иерархии. У каждого предка может быть несколько потомков, но у потомка может быть только один родитель.   -  person aw crud    schedule 03.11.2010

Ответы (2)


arrow_upward
2
arrow_downward 

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

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

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

person Quassnoi    schedule 03.11.2010

arrow_upward
1
arrow_downward

Пытаться:

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
person Community    schedule 03.11.2010