Trovare il pangrattato per i set nidificati

Question

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

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.

Answer 1

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.

Answer 2

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

Answer 3

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

Answer 4

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 + '%'

Answer 5

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

Answer 6

nessun codice specifico del server sql, ma stai semplicemente cercando:

SELEZIONA * DA tabella DOVE ha lasciato < (currentid.left) AND right > (Currentid.right)