¿Es posible consultar una tabla de estructura de árbol en MySQL en una sola consulta, a cualquier profundidad?

Question

Estoy pensando que la respuesta es no, pero me encantaría que alguien tuviera alguna idea de cómo rastrear una estructura de árbol a cualquier profundidad en SQL (MySQL), pero con una sola consulta

Más específicamente, dada una tabla estructurada por árbol (id, data, data, parent_id) y una fila en la tabla, es posible obtener todos los descendientes (child/grandchild/etc), o para el caso todos los antepasados ​​(parent/grandparent/etc.) sin saber cuán abajo o hacia abajo funcionará, utilizando una única consulta.

¿O está usando algún tipo de recurrencia, donde sigo consultando más profundamente hasta que no hay nuevos resultados?

Específicamente, estoy usando Ruby and Rails, pero supongo que no es muy relevante.

Answer 1

Definitivamente va a querer emplear alguna recursividad para eso. Y si estás haciendo eso, entonces sería trivial (de hecho más fácil) obtener todo el árbol en lugar de bits hasta una profundidad fija.

En realidad áspera pseudo-código que quieren algo en este sentido:

getChildren(parent){ 
    children = query(SELECT * FROM table WHERE parent_id = parent.id) 
    return children 
} 

printTree(root){ 
    print root 
    children = getChildren(root) 
    for child in children { 
     printTree(child) 
    } 
} 

Aunque en la práctica rara vez que le quiere hacer algo como esto. Será bastante ineficiente ya que está haciendo una solicitud para cada fila en la tabla, por lo que solo será sensata para tablas pequeñas o árboles que no estén anidados demasiado profundamente. Para ser honesto, en cualquier caso, probablemente quieras limitar la profundidad.

Sin embargo, dada la popularidad de este tipo de estructura de datos, es muy posible que haya algunas cosas de MySQL para ayudarlo con esto, específicamente para reducir el número de consultas que necesita realizar.

Editar: Habiendo pensado en ello, tiene muy poco sentido hacer todas estas consultas. Si de todos modos lees toda la tabla, puedes sorber todo en RAM, ¡suponiendo que sea lo suficientemente pequeño!

Answer 2

Aquí hay varios recursos:

• http://forums.mysql.com/read.php?10,32818,32818#msg-32818
• Managing Hierarchical Data in MySQL
• http://lists.mysql.com/mysql/201896

Básicamente, usted tiene que hacer algún tipo de cursor en un procedimiento almacenado o una consulta o construir una mesa de adyacencia. Evitaría la recursión fuera del DB: dependiendo de cuán profundo sea tu árbol, podría ser realmente lento/incompleto.

Answer 3

SQL no es un lenguaje Turing completo, lo que significa que no podrá realizar este tipo de bucle. Puede hacer algunas cosas muy inteligentes con SQL y estructuras de árbol, pero no puedo pensar en una manera de describir una fila que tiene una determinada identificación "en su jerarquía" para una jerarquía de profundidad arbitraria.

Su mejor apuesta es algo en la línea de lo que @Dan sugirió, que es simplemente abrirse paso en el árbol en otro lenguaje más capaz. En realidad, puede generar una cadena de consulta en un lenguaje de uso general mediante un bucle, donde la consulta es solo una serie complicada de uniones (o subconsultas) que refleja la profundidad de la jerarquía que está buscando. Eso sería más eficiente que el bucle y las consultas múltiples.

Answer 4

Me encontré con este problema antes y tuve una idea loca. Puede almacenar un campo en cada registro que sea cadena concatenada de sus identidades de antepasados ​​directos desde la raíz.

Imagine que tiene registros de este tipo (sangrado implica jerarquía y los números son la identificación, antepasados.

• 1, "1"
  • 2, "2,1"
    • 5, "5,2,1"
    • 6, "6,2,1"
      • 7, " 7,6,2,1"
      • 11, "11,6,2,1"
  • 3, "3,1"
    • 8 ", 8,3, 1"
    • 9, "9,3,1"
    • 10, "10,3,1"

Luego de seleccionar los descendientes de Identificación: 6, a hacer esto

SELECT FROM table WHERE ancestors LIKE "%6,2,1" 

Mantener la columna de antepasados ​​hasta la fecha podría ser más problemático de lo que vale para ti, pero es una solución factible en cualquier base de datos.

Answer 5

Sí, esto es posible, es un llamado Modificado Preordenes Árbol de recorrido, como se describe mejor aquí

Joe Celko's Trees and Hierarchies in SQL for Smarties

Un ejemplo de trabajo (en PHP) se proporciona aquí

http://www.sitepoint.com/article/hierarchical-data-database/2/

Answer 6

La técnica de Celko (conjuntos anidados) es bastante buena. También utilicé una tabla de adyacencia con los campos "ancestro" y "descendiente" y "distancia" (por ejemplo, los hijos/padres directos tienen una distancia de 1, los nietos/abuelos tienen una distancia de 2, etc.).

Esto debe mantenerse, pero es bastante fácil de hacer para inserciones: utiliza una transacción, luego coloque el enlace directo (padre, hijo, distancia = 1) en la tabla, luego INSERTAR IGNORAR una SELECCIÓN del padre existente & niños agregando distancias (puedo extraer el SQL cuando tengo oportunidad), que quiere un índice en cada uno de los 3 campos para el rendimiento. Donde este enfoque se pone feo es para eliminaciones ... básicamente tienes que marcar todos los elementos que han sido afectados y luego reconstruirlos. Pero una ventaja de esto es que puede manejar gráficos acíclicos arbitrarios, mientras que el modelo de conjuntos anidados solo puede hacer jerarquías rectas (por ejemplo, cada elemento, excepto que la raíz tiene uno y solo uno principal).

Answer 7

La respuesta de Daniel Beardsley no es para nada una solución cuando las preguntas principales que hace son "¿qué son todos mis hijos?" Y "¿qué son todos mis padres?".

En respuesta a Alex Weinstein, este método realmente da como resultado menos actualizaciones de nodos en un movimiento parental que en la técnica de Celko. En la técnica de Celko, si un nodo de nivel 2 en el extremo izquierdo se mueve debajo de un nodo de nivel 1 en el extremo derecho, entonces casi todos los nodos en el árbol necesitan actualización, en lugar de solo los hijos del nodo.

Lo que yo diría sin embargo es que Daniel posiblemente almacena el camino de regreso para rootear el camino equivocado.

me las guardo para que la consulta sería

SELECT FROM table WHERE ancestors LIKE "1,2,6%" 

Esto significa que MySQL puede hacer uso de un índice en la columna 'antepasados', que no sería capaz de hacer con un destacado% .

Answer 8

Esto definitivamente se puede hacer y no es tan complicado para SQL. He contestado a esta pregunta y proporcionó un ejemplo de trabajo utilizando el código de procedimiento MySQL aquí:

MySQL: How to find leaves in specific node

stand: Si no está satisfecho, usted debe marcar una de las respuestas aceptadas.

Answer 9

Utilicé la rutina "Con emulador" descrita en https://stackoverflow.com/questions/27013093/recursive-query-emulation-in-mysql (proporcionada por https://stackoverflow.com/users/1726419/yossico). Hasta ahora, he obtenido muy buenos resultados (en cuanto a rendimiento), pero no tengo una gran cantidad de datos o un gran número de descendientes para buscar a través de/for.