¿Cómo encontrar todos los nodos en un subárbol en una consulta SQL recursiva?

Question

Tengo una tabla que define una relación padre-hijo entre los nodos:

CREATE TABLE node (       ' pseudo code alert 
    id  INTEGER PRIMARY KEY, 
    parentID INTEGER, ' should be a valid id. 
) 

Si parentID siempre apunta a un nodo existente válida, entonces esto va a definir de forma natural una estructura de árbol.

Si el parentID es , podemos suponer que el nodo es un nodo raíz.

¿Cómo I:

1. Buscar todos los nodos que son decendientes de un nodo dado?
2. ¿Encontrar todos los nodos bajo un nodo dado a una profundidad específica?

Me gustaría hacer cada uno de estos como un solo SQL (supongo que sería necesariamente recursivo) o dos consultas mutuamente recursivas.

Estoy haciendo esto en un contexto ODBC, por lo que no puedo confiar en las características específicas del proveedor.

Editar

• No hay tablas se escriben sin embargo, por lo que añadir columnas adicionales/mesas es perfectamente aceptable.
• El árbol será potencialmente actualizado y agregado con bastante frecuencia; las estructuras/tablas/columnas de datos auxiliares serían posibles, aunque deben mantenerse actualizadas. Si tiene algún libro mágico al que recurra para este tipo de consulta, me gustaría saberlo.

Muchas gracias.

Answer 1

This link proporciona un tutorial tanto en la Lista Modelo de Adyacencia (como se describe en la pregunta), y el conjunto de modelos anidados. Está escrito como parte de la documentación de MySQL.

Lo que no se trata en ese artículo es el tiempo de inserción/delección, y el costo de mantenimiento de los dos enfoques. Por ejemplo:

• un árbol dinámicamente crecido usando el Conjunto Modelo anidada parecería a necesitar un poco de mantenimiento para mantener la anidación (por ejemplo, volver a numerar todos los números de los conjuntos izquierdo y derecho)
• eliminación de un nodo en el modelo de lista de adyacencia requeriría actualizaciones en al menos otra fila.

Answer 2

Algunos métodos fueron cubiertos previamente en este artículo:

SQL - how to store and navigate hierarchies

Answer 3

Si tiene alguna libros de magia se trata de alcanzar para este tipo de consulta, me gustaría saber.

de Celko árboles y jerarquías en SQL Para Smarties

Answer 4

Almacene toda la "ruta" desde la ID del nodo raíz en una columna separada, asegurándose de usar un separador al principio y al final también. P.ej. digamos que 1 es el padre de 5, que es el padre de 17, y su carácter separador es el guión, usted almacenaría el valor -1-5-17- en su columna de ruta.

ahora para encontrar todos los niños de 5 sólo tiene que seleccionar los registros en la ruta incluye -5-

Los separadores en los extremos son necesarios para que usted no tiene que preocuparse acerca de la identificación que se encuentran en el extremo izquierdo o el extremo derecho del campo cuando usas LIKE.

En cuanto a su problema de profundidad, si agrega una columna de profundidad a su tabla indicando la profundidad de anidación actual, esto también se vuelve fácil. Busca la profundidad de su nodo inicial y luego le agrega x donde x es el número de niveles profundos que desea buscar, y filtra los registros con mayor profundidad.