Acoplar Adyacencia lista Jerarquía a una lista de todos los caminos

Question

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

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 de la más lejana lvl derecha. El valor en la columna de la lvl1 siempre representar el nodo raíz, los valores en LVL2 siempre representará descendientes directos de LVL1, y así sucesivamente.

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

Answer 1

Para hacer consultas de varios niveles a través de un simple adyacencia lista invariablemente implica auto-izquierda se une. 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 la izquierda-alinearlo 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;

  

trabajaría para jerarquías de n niveles.

Lo sentimos, consultas arbitraria de profundidad no son posibles en el modelo de adyacencia-list. Si usted está haciendo este tipo de consulta mucho, usted debe cambiar su esquema a uno de los otros modelos de almacenamiento de información jerárquica :. relación de adyacencia completa (el almacenamiento de todas las relaciones ancestro-descendientes), ruta o conjuntos anidados materializó

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

Answer 2

Como se ha mencionado, SQL no tiene forma limpia para implementar tablas con dinámicamente un número variable 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 suena grotesca inicialmente; almacenar identificadores como cadena ?! Pero cuando la salida tiene el formato XML o algo así, la gente no parece a la mente tanto.

Del mismo modo, esto es de muy poca utilidad si luego desea unirse en los resultados en SQL. Si el resultado es que se suministra a una aplicación, que puede ser muy adecuado. Sin embargo, personalmente prefiero hacer el aplanamiento de la aplicación en lugar de SQL

Estoy atrapado aquí en una pantalla de 10 pulgadas que no tienen acceso a SQL así que no puedo dar el código probado, pero el método básico sería utilizar la repetición 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 utilizado un recursivo CON desde hace tiempo, pero voy a dar a la sintaxis de un ir a pesar de que no tengo SQL aquí para probar cualquier cosa:)

recursiva con un

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 3

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

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

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

Answer 4

En realidad se puede hacer con SQL dinámico dentro de un procedimiento tiendas. A continuación, se convierte en limitada a lo que se puede hacer sith el procedimiento almacenado. Obviamente se convierte en un desafío a exec los resultados en una tabla temporal sin saber cuántas columnas esperar. Sin embargo, si el objetivo es dar salida a una página web u otra interfaz de usuario, entonces puede ser vale la pena el esfuerzo ...