Geek Answers Handbook

Finding breadcrumbs for nested sets

I use nested sets (the so-called modified pre-order tree traversal) to save the list of groups, and I'm trying to find a quick way to create breadcrumbs (as rows, not tables) for ALL groups once. My data is also stored using the adjacency list model (there are triggers for synchronizing the two).

So for example:

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

What the tree represents:

  • Node a
    • Node B
      • Node C
    • Node D
      • Node e
      • Node F

I would like to have a custom function that returns a table:

 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

To make this a little more complicated (although this goes beyond the scope of the question), I also have user restrictions that must be followed. So, for example, if I only have access to id = 3, when I run the request, I should get:

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

I have a user-defined function that takes a user id as a parameter and returns a table with the identifiers of all valid groups, so until somewhere in the query

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

he will work.

I have an existing scalar function that can do this, but it just doesn't work with any reasonable number of groups (takes> 10 seconds on 2000 groups). It takes the groupid and userid parameters as the parameter and returns nvarchar. It finds the data of the parent group (1 query to grab the values ​​left / right, another to search for parents), restricts the list to groups the user has access to (using the same WHERE clause as above, so another query) , and then uses the cursor to step through each group and adds it to the line before finally returning this value.

I need a way for this to work quickly (e.g.. <= 1s), on the fly.

This is on SQL Server 2005.

+4
source share
6 answers

What I ended up doing is a big join that just ties this table to itself, over and over for each level.

First, I fill the @topLevelGroups table with only 1st level groups (if you have only one root, you can skip this step), and then @userGroups with groups that the user can see.

 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]

This is a pretty big hack and is obviously limited to a certain number of levels (there is a reasonable limit for my application that I can choose), the problem is that the more levels are supported, the more the number connects exponentially and, therefore, much slower.

The execution of this code is certainly simpler, but for me it’s just not always an option - there are times when I need it directly from the SQL query.

I accept this as an answer, as this is what I have finished, and it may work for other people. However, if someone can come up with a more efficient method, I will change it to them.

+1
source

Ok This is for MySQL, not for SQL Server 2005. It uses GROUP_CONCAT with a subquery.

This should return the full palette as a single column.

 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
+3
source

If you can, use a path (or I think I heard that it is referred to as a line), for example:

 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,

To get only node D and forth (psuedocode):

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

here is the SQL that worked for me to get the breadcrumb path from anywhere in the tree. Hope this helps.

 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

Kata

+2
source

I modified Katie's Statement to get breadcrumbs for each item

 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

Feel free to add a WHERE clause, for example

  WHERE ancestor.lft BETWEEN 6 AND 11
+1
source

there is no sql server specific code, but you are just looking for:

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

0
source

More articles:


All Articles