Trovare il pangrattato per i set nidificati
-
03-07-2019 - |
Domanda
Sto usando set nidificati (aka attraversamento albero preordine modificato) per memorizzare un elenco di gruppi e sto cercando di trovare un modo rapido per generare breadcrumb (come una stringa, non una tabella) per TUTTI i gruppi subito. I miei dati vengono inoltre memorizzati utilizzando il modello dell'elenco di adiacenza (ci sono trigger per mantenere i due sincronizzati).
Quindi, per esempio:
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
Che rappresenta l'albero:
- Nodo A
- Nodo B
- Nodo C
- Nodo D
- Nodo E
- Nodo F
- Nodo B
Vorrei poter avere una funzione definita dall'utente che restituisce una tabella:
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
Per renderlo leggermente più complicato (anche se è un po 'fuori dall'ambito della domanda), ho anche delle restrizioni per gli utenti che devono essere rispettate. Ad esempio, se ho accesso solo a id = 3, quando eseguo la query dovrei ottenere:
ID Breadcrumb
3 Node D
4 Node D > Node E
5 Node D > Node F
Ho una funzione definita dall'utente che accetta un userid come parametro e restituisce una tabella con gli ID di tutti i gruppi validi, quindi purché da qualche parte nella query
WHERE group.id IN (SELECT id FROM dbo.getUserGroups(@userid))
funzionerà.
Ho una funzione scalare esistente che può farlo, ma non funziona su un numero ragionevole di gruppi (impiega > 10 secondi su 2000 gruppi). Prende un groupid e userid come parametro e restituisce un nvarchar. Trova i genitori dei gruppi indicati (1 query per catturare i valori left / right, un altro per trovare i parent), limita l'elenco ai gruppi a cui l'utente ha accesso (usando la stessa clausola WHERE di cui sopra, quindi un'altra query), e quindi utilizza un cursore per passare attraverso ciascun gruppo e aggiungerlo a una stringa, prima di restituire infine quel valore.
Ho bisogno di un metodo per farlo che verrà eseguito rapidamente (ad es. < = 1s), al volo.
Questo è su SQL Server 2005.
Soluzione 4
Quello che ho finito per fare è un grande join che lega semplicemente questa tabella a se stessa, ancora e ancora per ogni livello.
Per prima cosa popolo una tabella @topLevelGroups con solo i gruppi di 1 ° livello (se hai solo una radice puoi saltare questo passaggio), e poi @userGroups con i gruppi che l'utente può vedere.
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]
Questo è un trucco piuttosto grande ed è ovviamente limitato a un certo numero di livelli (per la mia app, c'è un limite ragionevole che posso scegliere), con il problema che più livelli sono supportati, aumenta il numero di si unisce in modo esponenziale e quindi è molto più lento.
Farlo nel codice è sicuramente più facile, ma per me questa non è sempre un'opzione - ci sono volte in cui ho bisogno di questo disponibile direttamente da una query SQL.
Accetto questo come risposta, poiché è quello che ho finito e potrebbe funzionare per altre persone - tuttavia, se qualcuno può trovare un metodo più efficiente, lo cambierò con loro.
Altri suggerimenti
ecco l'SQL che ha funzionato per me per ottenere il " breadcrumb " percorso da qualsiasi punto dell'albero. Spero che sia d'aiuto.
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. Questo è per MySQL, non per SQL Server 2005. Utilizza un GROUP_CONCAT con una sottoquery.
Questo dovrebbe restituire l'intero breadcrumb come singola colonna.
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
Se puoi, usa un campo path (o penso di averlo sentito chiamato lignaggio) come:
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,
Per ottenere solo il nodo D e successivi (psuedocode):
path = SELECT Path FROM Nodes WHERE ID = 3
SELECT * FROM Nodes WHERE Path LIKE = path + '%'
Ho modificato la Dichiarazione di Kathy per ottenere il pangrattato per ogni 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
Sentiti libero di aggiungere una condizione WHERE, ad esempio
WHERE ancestor.lft BETWEEN 6 AND 11
nessun codice specifico del server sql, ma stai semplicemente cercando:
SELEZIONA * DA tabella DOVE ha lasciato < (currentid.left) AND right > (Currentid.right)