Recherche de chapelure pour les ensembles imbriqués

Question

J'utilise des ensembles imbriqués (c.-à-d. traversée d'arborescence de pré-ordre modifiée) pour stocker une liste de groupes, et j'essaie de trouver un moyen rapide de générer un fil d'Ariane (sous forme de chaîne, pas de table) pour TOUS les groupes. immediatement. Mes données sont également stockées à l'aide du modèle de liste de contiguïté (des déclencheurs permettent de garder les deux synchronisés).

Ainsi, par exemple:

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

Qui représente l'arbre:

• Nœud A
  • Nœud B
    • nœud C
  • nœud D
    • nœud E
    • nœud F

J'aimerais pouvoir disposer d'une fonction définie par l'utilisateur qui renvoie un tableau:

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

Pour rendre cela un peu plus compliqué (bien que ce soit en quelque sorte hors du champ de la question), j'ai également des restrictions d'utilisateurs à respecter. Ainsi, par exemple, si je n’ai accès qu’à id = 3, lors de l’exécution de la requête, j’obtiens:

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

J'ai une fonction définie par l'utilisateur qui prend un ID utilisateur en tant que paramètre et renvoie une table avec les identifiants de tous les groupes valides, de sorte que quelque part dans la requête

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

cela fonctionnera.

J'ai une fonction scalaire existante qui peut le faire, mais cela ne fonctionne tout simplement pas avec un nombre raisonnable de groupes (prend > 10 secondes sur 2 000 groupes). Il prend un identifiant de groupe et un identifiant d'utilisateur en tant que paramètre et renvoie un nvarchar. Il trouve les groupes de parents donnés (1 requête pour saisir les valeurs gauche / droite, une autre pour trouver les parents), limite la liste aux groupes auxquels l'utilisateur a accès (en utilisant la même clause WHERE que ci-dessus, donc une autre requête), et utilise ensuite un curseur pour parcourir chaque groupe et l'ajouter à une chaîne, avant de renvoyer cette valeur.

J'ai besoin d'une méthode pour ce faire qui fonctionnera rapidement (par exemple. < = 1s), à la volée.

C’est sur SQL Server 2005.

Answer 1

Ce que j'ai fini par faire est de créer une grande jointure qui lie simplement cette table à elle-même, encore et encore pour chaque niveau.

Je remplis d'abord une table @topLevelGroups avec uniquement les groupes de premier niveau (si vous ne possédez qu'une seule racine, vous pouvez ignorer cette étape), puis @userGroups avec les groupes que l'utilisateur peut voir.

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]

Ceci est un assez gros bidouillage, et est évidemment limité à un certain nombre de niveaux (pour mon application, il y a une limite raisonnable que je peux choisir), avec le problème que plus le nombre de niveaux est pris en charge, plus le nombre de rejoint exponentiellement, et est donc beaucoup plus lent.

Le faire dans le code est certes plus simple, mais pour moi, ce n’est tout simplement pas une option - j’ai parfois besoin de cette information directement à partir d’une requête SQL.

J'accepte cela comme une solution, car c'est ce que j'ai finalement fait et que cela pourrait fonctionner pour d'autres personnes. Cependant, si quelqu'un peut trouver une méthode plus efficace, je le lui changerai.

Answer 2

voici le code SQL qui a fonctionné pour moi pour obtenir le & "fil d'Ariane &"; chemin depuis n’importe quel point de l’arbre. J'espère que ça aide.

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. Ceci concerne MySQL et non SQL Server 2005. Il utilise GROUP_CONCAT avec une sous-requête.

Ceci devrait renvoyer le fil d'Ariane complet sous forme de colonne unique.

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 vous le pouvez, utilisez un chemin (ou je pense l'avoir entendu parler de lignage) comme:

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,

Pour obtenir uniquement le noeud D et les suivants (psuedocode):

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

Answer 5

J'ai modifié la déclaration de Kathy pour obtenir la chapelure pour chaque élément

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

N'hésitez pas à ajouter une condition WHERE, par exemple

.

 WHERE ancestor.lft BETWEEN 6 AND 11

Answer 6

pas de code spécifique au serveur SQL, mais cherchez-vous simplement:

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