Aplanar jerarquía de lista de adyacencia a una lista de todas las rutas

Question

Tengo una tabla que almacena información jerárquica utilizando el modelo de lista de adyacencia. (. Utiliza una clave de auto referencial - Este ejemplo siguiente tabla puede ser familiar):

category_id name     parent 
----------- -------------------- ----------- 
1   ELECTRONICS   NULL 
2   TELEVISIONS   1 
3   TUBE     2 
4   LCD     2 
5   PLASMA    2 
6   PORTABLE ELECTRONICS 1 
7   MP3 PLAYERS   6 
8   FLASH    7 
9   CD PLAYERS   6 
10   2 WAY RADIOS   6 

---

¿Cuál es el mejor método para "aplanar" los datos anteriores en algo como esto?

category_id lvl1  lvl2  lvl3  lvl4 
----------- ----------- ----------- ----------- ----------- 
1   1   NULL  NULL  NULL 
2   1   2   NULL  NULL 
6   1   6   NULL  NULL 
3   1   2   3   NULL 
4   1   2   4   NULL 
5   1   2   5   NULL 
7   1   6   7   NULL 
9   1   6   9   NULL 
10   1   6   10   NULL 
8   1   6   7   8 

---

Cada fila es una "trayectoria" a través de la Jerarquía, excepto que hay una fila para cada nodo (no sólo cada nodo hoja). La columna category_id representa el nodo actual y las columnas "lvl" son sus antepasados. El valor para el nodo actual también debe estar en la columna más lejana de la derecha. El valor en la columna lvl1 siempre representará el nodo raíz, los valores en lvl2 siempre representarán descendientes directos de lvl1, y así sucesivamente.

Si es posible, el método para generar esta salida sería en SQL, y funcionaría para las jerarquías de n niveles.

Answer 1

Para realizar consultas multinivel a través de una lista de adyacencia simple invariablemente implica uniones de izquierda a izquierda. Es fácil hacer una tabla alineada a la derecha:

SELECT category.category_id, 
    ancestor4.category_id AS lvl4, 
    ancestor3.category_id AS lvl3, 
    ancestor2.category_id AS lvl2, 
    ancestor1.category_id AS lvl1 
FROM categories AS category 
    LEFT JOIN categories AS ancestor1 ON ancestor1.category_id=category.category_id 
    LEFT JOIN categories AS ancestor2 ON ancestor2.category_id=ancestor1.parent 
    LEFT JOIN categories AS ancestor3 ON ancestor3.category_id=ancestor2.parent 
    LEFT JOIN categories AS ancestor4 ON ancestor4.category_id=ancestor3.parent; 

A izquierda-align que al igual que su ejemplo es un poco más complejo. Esto viene a la mente:

SELECT category.category_id, 
    ancestor1.category_id AS lvl1, 
    ancestor2.category_id AS lvl2, 
    ancestor3.category_id AS lvl3, 
    ancestor4.category_id AS lvl4 
FROM categories AS category 
    LEFT JOIN categories AS ancestor1 ON ancestor1.parent IS NULL 
    LEFT JOIN categories AS ancestor2 ON ancestor1.category_id<>category.category_id AND ancestor2.parent=ancestor1.category_id 
    LEFT JOIN categories AS ancestor3 ON ancestor2.category_id<>category.category_id AND ancestor3.parent=ancestor2.category_id 
    LEFT JOIN categories AS ancestor4 ON ancestor3.category_id<>category.category_id AND ancestor4.parent=ancestor3.category_id 
WHERE 
    ancestor1.category_id=category.category_id OR 
    ancestor2.category_id=category.category_id OR 
    ancestor3.category_id=category.category_id OR 
    ancestor4.category_id=category.category_id; 

funcionaría para las jerarquías de n-capas.

Lo sentimos, las consultas de profundidad arbitraria no son posibles en el modelo de lista de adyacencia. Si realiza este tipo de consultas mucho, debe cambiar su esquema a uno de other models of storing hierarchical information: relación de adyacencia completa (almacenamiento de todas las relaciones ancestro-descendiente), ruta materializada o conjuntos anidados.

Si las categorías no se mueven mucho (lo que suele ser el caso de una tienda como su ejemplo), tendería hacia conjuntos anidados.

Answer 2

Atravesar un árbol de profundidad arbitraria generalmente implica un código de procedimiento recursivo, a menos que utilice las características especiales de algunos DBMS.

En Oracle, la cláusula CONNECT BY le permitirá recorrer el árbol en primer orden si utiliza la lista de adyacencia, como lo hizo aquí.

Si utiliza conjuntos anidados, el número de secuencia izquierdo le proporcionará la orden de visitar los nodos.

Answer 3

Como se mencionó, SQL no tiene una forma clara de implementar tablas con números dinámicamente variables de columnas. Las dos únicas soluciones que he utilizado antes son: 1. Un número fijo autocombinaciones, dando un número fijo de columnas (AS por bobince) 2. Generar los resultados como una cadena en una sola columna

El segundo uno suena grotesco inicialmente; almacenando identificadores como una cadena ?! Pero cuando la salida se formatea como XML o algo, a la gente no parece importarle mucho.

Igualmente, esto es de muy poca utilidad si quiere unirse a los resultados en SQL. Si el resultado se debe suministrar a una aplicación, puede ser muy adecuado. Personalmente, sin embargo, prefiero hacer el aplanamiento en la Aplicación en lugar de SQL

Estoy atascado aquí en una pantalla de 10 pulgadas sin acceso a SQL, así que no puedo dar el código probado, pero el método básico sería utilizar recursividad de alguna manera;
- Una función escalar recursivo puede hacer esto
- MS SQL puede hacer esto utilizando una recursiva con un comunicado (más eficiente)

función escalar (algo así):

CREATE FUNCTION getGraphWalk(@child_id INT) 
RETURNS VARCHAR(4000) 
AS 
BEGIN 

    DECLARE @graph VARCHAR(4000) 

    -- This step assumes each child only has one parent 
    SELECT 
    @graph = dbo.getGraphWalk(parent_id) 
    FROM 
    mapping_table 
    WHERE 
    category_id = @child_id 
    AND parent_id IS NOT NULL 

    IF (@graph IS NULL) 
    SET @graph = CAST(@child_id AS VARCHAR(16)) 
    ELSE 
    SET @graph = @graph + ',' + CAST(@child_id AS VARCHAR(16)) 

    RETURN @graph 

END 


SELECT 
    category_id       AS [category_id], 
    dbo.getGraphWalk(category_id)  AS [graph_path] 
FROM 
    mapping_table 
ORDER BY 
    category_id 

no he T usé un recursivo WITH en un momento, pero voy a dar una sintaxis a pesar de que no tengo SQL aquí para probar nada :)

Recursive WITH

WITH 
    result (
    category_id, 
    graph_path 
) 
AS 
(
    SELECT 
    category_id, 
    CAST(category_id AS VARCHAR(4000)) 
    FROM 
    mapping_table 
    WHERE 
    parent_id IS NULL 

    UNION ALL 

    SELECT 
    mapping_table.category_id, 
    CAST(result.graph_path + ',' + CAST(mapping_table.category_id AS VARCHAR(16)) AS VARCHAR(4000)) 
    FROM 
    result 
    INNER JOIN 
    mapping_table 
     ON result.category_id = mapping_table.parent_id 
) 

SELECT 
    * 
FROM 
    result 
ORDER BY 
    category_id 

EDITAR - SALIDA para ambos es el mismo:

1 '1' 
2 '1,2' 
3 '1,2,3' 
4 '1,2,4' 
5 '1,2,5' 
6 '1,6' 
7 '1,6,7' 
8 '1,6,7,8' 
9 '1,6,9' 

Answer 4

En realidad se puede hacer con SQL dinámico dentro de un procedimiento tiendas. Entonces se limita a lo que se puede hacer con el procedimiento almacenado. Obviamente se convierte en un desafío para EXEC los resultados en una tabla temporal sin saber cuántas columnas esperar. Sin embargo, si el objetivo es generar una salida a una página web u otra IU, entonces puede valer la pena el esfuerzo ...