Encontrar migas de pan para conjuntos anidados
-
03-07-2019 - |
Pregunta
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
- Nodo B
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.
Solución 4
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é.
Otros consejos
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
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
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 + '%'
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
no hay código específico de servidor sql, pero simplemente está buscando:
SELECT * FROM table WHERE left < (currentid.left) Y derecha > (currentid.right)