Encontrar migas de pan para conjuntos anidados

Question

Estoy usando conjuntos anidados (también conocido como recorrido de árbol de pedido anticipado modificado) para almacenar una lista de grupos, y estoy tratando de encontrar una forma rápida de generar migas de pan (como una cadena, no una tabla) para TODOS los grupos En seguida. Mis datos también se almacenan utilizando el modelo de lista de adyacencia (hay activadores para mantener los dos sincronizados).

Entonces, por ejemplo:

ID   Name    ParentId  Left   Right
0    Node A  0         1      12
1    Node B  0         2      5
2    Node C  1         3      4
3    Node D  0         6      11
4    Node E  3         7      8
5    Node F  4         9      9

Que representa el árbol:

• Nodo A
  • Nodo B
    • Nodo C
  • Nodo D
    • Nodo E
    • Nodo F

Me gustaría poder tener una función definida por el usuario que devuelva una tabla:

ID  Breadcrumb
0   Node A
1   Node A > Node B
2   Node A > Node B > Node C
3   Node A > Node D
4   Node A > Node D > Node E
5   Node A > Node D > Node F

---

Para hacer esto un poco más complicado (aunque está fuera del alcance de la pregunta), también tengo restricciones de usuario que deben respetarse. Entonces, por ejemplo, si solo tengo acceso a id = 3, cuando ejecuto la consulta debería obtener:

ID  Breadcrumb
3   Node D
4   Node D > Node E
5   Node D > Node F

Tengo una función definida por el usuario que toma un ID de usuario como parámetro y devuelve una tabla con los ID de todos los grupos que son válidos, siempre y cuando en algún lugar de la consulta

WHERE group.id IN (SELECT id FROM dbo.getUserGroups(@userid))

funcionará.

---

Tengo una función escalar existente que puede hacer esto, pero simplemente no funciona en ningún número razonable de grupos (toma > 10 segundos en 2000 grupos). Toma un groupid y userid como parámetro, y devuelve un nvarchar. Encuentra los grupos de padres dados (1 consulta para tomar los valores izquierdo / derecho, otra para encontrar los padres), restringe la lista a los grupos a los que el usuario tiene acceso (usando la misma cláusula WHERE que la anterior, por lo que otra consulta), y luego usa un cursor para pasar por cada grupo y agregarlo a una cadena, antes de finalmente devolver ese valor.

Necesito un método para hacer esto que se ejecute rápidamente (por ejemplo, < = 1s), sobre la marcha.

Esto está en SQL Server 2005.

Answer 1

Lo que terminé haciendo es hacer una gran unión que simplemente vincula esta tabla consigo misma, una y otra vez para cada nivel.

Primero lleno una tabla @topLevelGroups con solo los grupos de primer nivel (si solo tiene una raíz puede omitir este paso), y luego @userGroups con los grupos que el usuario puede ver.

SELECT groupid,
   (level1 
    + CASE WHEN level2 IS NOT NULL THEN ' > ' + level2 ELSE '' END
    + CASE WHEN level3 IS NOT NULL THEN ' > ' + level3 ELSE '' END
   )as [breadcrumb]
FROM (
  SELECT g3.*
    ,g1.name as level1
    ,g2.name as level2
    ,g3.name as level3
  FROM @topLevelGroups g1
  INNER JOIN @userGroups g2 ON g2.parentid = g1.groupid and g2.groupid <> g1.groupid
  INNER JOIN @userGroups g3 ON g3.parentid = g2.groupid 

  UNION

  SELECT g2.*
    ,g1.name as level1
    ,g2.name as level2
    ,NULL as level3
  FROM @topLevelGroups g1 
  INNER JOIN @userGroups g2 ON g2.parentid = g1.groupid and g2.groupid <> g1.groupid

  UNION

  SELECT g1.*
    ,g1.name as level1
    ,NULL as level2
    ,NULL as level3 
  FROM @topLevelGroups g1

) a
ORDER BY [breadcrumb]

Este es un truco bastante grande, y obviamente está limitado a un cierto número de niveles (para mi aplicación, hay un límite razonable que puedo elegir), con el problema de que a medida que se admiten más niveles, aumenta el número de se une exponencialmente y, por lo tanto, es mucho más lento.

Hacerlo en código es ciertamente más fácil, pero para mí eso no siempre es una opción: hay momentos en los que necesito que esté disponible directamente desde una consulta SQL.

---

Estoy aceptando esto como la respuesta, ya que es lo que terminé haciendo y puede funcionar para otras personas; sin embargo, si alguien puede encontrar un método más eficiente, se lo cambiaré.

Answer 2

aquí está el SQL que me funcionó para obtener " breadcrumb " camino desde cualquier punto del árbol. Espero que ayude.

SELECT ancestor.id, ancestor.title, ancestor.alias 
FROM `categories` child, `categories` ancestor 
WHERE child.lft >= ancestor.lft AND child.lft <= ancestor.rgt 
AND child.id = MY_CURRENT_ID 
ORDER BY ancestor.lft

Kath

Answer 3

Ok. Esto es para MySQL, no para SQL Server 2005. Utiliza un GROUP_CONCAT con una subconsulta.

Esto debería devolver la ruta de exploración completa como una sola columna.

SELECT 
 (SELECT GROUP_CONCAT(parent.name SEPARATOR ' > ')
 FROM category parent
 WHERE node.Left >= parent.Left
 AND node.Right <= parent.Right
 ORDER BY Left
 ) as breadcrumb
FROM category node
ORDER BY Left

Answer 4

Si puede, use un campo de ruta (o creo que lo he escuchado referido como un linaje) como:

ID   Name    ParentId  Left   Right   Path
0    Node A  0         1      12      0,
1    Node B  0         2      5       0,1,
2    Node C  1         3      4       0,1,2,
3    Node D  0         6      11      0,3,
4    Node E  3         7      8       0,3,4,
5    Node F  4         9      9       0,3,4,

Para obtener solo el nodo D y hacia adelante (psuedocode):

path = SELECT Path FROM Nodes WHERE ID = 3
SELECT * FROM Nodes WHERE Path LIKE = path + '%'

Answer 5

Modifiqué la Declaración de Kathy para obtener migas de pan para cada elemento

SELECT
    GROUP_CONCAT(
        ancestor.name
        ORDER BY ancestor.lft ASC
        SEPARATOR ' > '
    ),
    child.*
FROM `categories` child
JOIN `categories` ancestor
ON child.lft >= ancestor.lft
AND child.lft <= ancestor.rgt
GROUP BY child.lft
ORDER BY child.lft

Siéntase libre de agregar una condición WHERE, por ejemplo

 WHERE ancestor.lft BETWEEN 6 AND 11

Answer 6

no hay código específico de servidor sql, pero simplemente está buscando:

SELECT * FROM table WHERE left < (currentid.left) Y derecha > (currentid.right)