Die Suche nach Brotkrumen für verschachtelte Sätze

Question

Ich bin mit verschachtelten Sätzen (auch bekannt als modifizierte Preorder Baum-Traversal) eine Liste der Gruppen zu speichern, und ich versuche, einen schnellen Weg zu finden Paniermehl zu erzeugen (als String, keine Tabelle) für alle Gruppen auf einmal. Meine Daten werden ebenfalls gespeichert unter Verwendung des Adjazenzliste Modell (es gibt Trigger die beiden synchron zu halten).

So zum Beispiel:

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

Welche stellt den Baum:

• Knoten A
  • Node B
    • Der Knoten C
  • Knoten D
    • Knoten E
    • Knoten F

Ich möchte in der Lage sein, eine benutzerdefinierte Funktion zu haben, die eine Tabelle zurückgibt:

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

---

Diese kompliziertere leicht zu machen (obwohl sie aus dem Anwendungsbereich der Frage Art ist), habe ich auch Benutzer Einschränkungen haben, die respektiert werden müssen. So zum Beispiel, wenn ich nur den Zugriff auf id = 3 haben, wenn ich die Abfrage ausführen sollte ich:

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

Ich habe eine benutzerdefinierte Funktion, die einen Benutzer-ID als Parameter annimmt, und gibt eine Tabelle mit dem IDs aller Gruppen, die gültig sind, so lange, wie irgendwo in der Abfrage

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

es wird funktionieren.

---

Ich habe eine vorhandene Skalar-Funktion, die dies tun können, aber es funktioniert einfach nicht auf einer angemessenen Anzahl von Gruppen (dauert> 10 Sekunden auf 2000 Gruppen). Es dauert eine groupid und Benutzer-ID als Parameter und gibt einen nvarchar. Er findet die gegebenen Gruppen Eltern (1 Abfrage der linken / rechten Werte zu ergreifen, eine andere, die Eltern zu finden), um die Liste der Gruppen beschränkt die Benutzer Zugriff auf (mit der gleichen WHERE-Klausel wie oben, so eine weitere Abfrage) hat, und verwendet dann einen Cursor durch jede Gruppe zu gehen und hängen sie ihn an einer Schnur, bevor sie schließlich diesen Wert zurück.

Ich brauche eine Methode, dies zu tun, die schnell ausgeführt werden (z. B. <= 1 s), on the fly.

Dies ist auf SQL Server 2005.

Answer 1

Was ich am Ende eine große tun up macht verbinden, dass einfach bindet diese Tabelle mit sich selbst, immer und immer wieder für jedes Niveau.

Zuerst fülle ich eine Tabelle @topLevelGroups mit nur den ersten Level-Gruppen (wenn Sie nur eine Wurzel haben Sie diesen Schritt überspringen), und dann @userGroups mit den Gruppen, die Benutzer sehen können.

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]

Das ist eine ziemlich große Hack ist, und ist offenbar auf eine bestimmte Anzahl von Ebenen begrenzt (für meine app, gibt es eine vernünftige Grenze ich wählen kann), mit dem Problem, dass die mehr Ebenen unterstützt werden, erhöht sich die Zahl der schließt sich exponentiell, und somit ist viel langsamer.

Doing es im Code ist sicherlich einfacher, aber das ist für mich einfach nicht immer eine Option - es gibt Zeiten, wenn ich direkt aus einer SQL-Abfrage diese verfügbar benötigen

.

---

Ich nehme dies als Antwort, denn es ist das, was ich tun beendet und es kann für andere Menschen arbeiten -. Aber, wenn jemand mit einem effizienteren Verfahren kommen kann ich es ihnen ändern werde

Answer 2

Hier ist die SQL, die für mich gearbeitet, um den „Brotkrumen“ Weg von einem beliebigen Punkt im Baum zu erhalten. Hoffe, es hilft.

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. Dies ist für MySQL, SQL Server 2005. Es verwendet eine GROUP_CONCAT mit einer Unterabfrage.

Dies sollte die volle Brotkrümel als einzelne Spalte zurück.

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

Wenn Sie können, verwenden Sie einen Pfad (oder ich glaube, ich habe gehört, dass es als Linie bezeichnet) Feld wie:

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,

nur Knoten D zu erhalten und weiter (psuedocode):

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

Answer 5

modifizierte ich die Erklärung von Kathy zu bekommen Paniermehl für jedes Element

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

Sie können ferner eine WHERE-Bedingung z hinzuzufügen.

 WHERE ancestor.lft BETWEEN 6 AND 11

Answer 6

keine SQL Server-spezifischen Code, aber suchen Sie einfach nach:

* FROM Tabelle SELECT WHERE links <(currentid.left) und rechts> (currentid.right)