¿Cómo puedo consulta para todos los nodos entre dos nodos en un árbol?

Question

I tiene un strucutre base de datos jerárquica, por ejemplo, columnas ID y PARENT_ID definen para cada fila, con las filas de nivel superior que tiene una NULL PARENT_ID.

I tienen todas las relaciones de esta tabla aplanado en otra tabla, por ejemplo si hubiera tres registros en una sola jerarquía de abuelo, padre, nieto, no habría 3 registros:

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

En lugar de ejecutar una consulta jerárquica para determinar que el nieto es un descendiente del abuelo simplemente puedo comprobar la existencia de un registro (grandparent, grandchild) en esta tabla aplanada.

Mi pregunta es, el uso de esta tabla aplanado, ¿cómo puedo lo más eficientemente posible devolver todos los registros que son entre dos nodos. Siguiendo con el ejemplo, con grandparent y grandchild como mis parámetros, ¿cómo puedo recuperar el registro (grandparent, parent).

No quiero usar una consulta jerárquica para resolver esto ... Me pregunto si es posible hacer esto sin ningún tipo de uniones.

Answer 1

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

Esto tomará automáticamente de los casos, cuando @ancestor no es realmente un antepasado de @descendant.

Crear un índice en (descendant, hops) para que esto funcione rápido.

Answer 2

Trate:

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
                  )