Поиск крошек для вложенных наборов

Question

Я использую вложенные наборы (или измененный обход дерева предзаказа) для хранения списка групп, и я пытаюсь найти быстрый способ создания хлебных крошек (в виде строки, а не таблицы) для ВСЕХ групп однажды. Мои данные также хранятся с использованием модели списка смежности (есть триггеры для синхронизации двух).

Так, например:

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

Что представляет собой дерево:

• Узел А
  • Узел Б
    • Узел C
  • Узел D
    • Узел E
    • Узел F

Я бы хотел иметь функцию, определяемую пользователем, которая возвращает таблицу:

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

---

Чтобы сделать это немного сложнее (хотя это и выходит за рамки вопроса), у меня также есть ограничения пользователей, которые необходимо соблюдать. Так, например, если у меня есть доступ только к id = 3, при выполнении запроса я должен получить:

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

У меня есть определенная пользователем функция, которая принимает идентификатор пользователя в качестве параметра и возвращает таблицу с идентификаторами всех групп, которые являются действительными, так что до тех пор, пока где-то в запросе

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

это будет работать.

---

У меня есть существующая скалярная функция, которая может это сделать, но она просто не работает с любым разумным количеством групп (на 2000 групп уходит> 10 секунд). Он принимает groupid и userid в качестве параметра и возвращает nvarchar. Он находит родителей заданных групп (1 запрос для захвата левых / правых значений, другой - для поиска родителей), ограничивает список группами, к которым у пользователя есть доступ (используя то же предложение WHERE, что и выше, поэтому еще один запрос) и затем использует курсор, чтобы пройти каждую группу и добавить ее в строку, прежде чем, наконец, вернуть это значение.

Мне нужен метод для этого, который будет работать быстро (например, <= 1 с) на лету. </p>

Это на SQL Server 2005.

Answer 1

Хорошо. Это для MySQL, а не SQL Server 2005. Он использует GROUP_CONCAT с подзапросом.

Это должно вернуть всю крошку в виде одного столбца.

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 2

вот SQL, который сработал для меня, чтобы получить путь крошки из любой точки дерева. Надеюсь, это поможет.

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

Кат

Answer 3

Если вы можете, используйте поле пути (или, я думаю, я слышал, что это называется линией), например:

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,

Чтобы получить только узел D и далее (psuedocode):

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

Answer 4

Я изменил Заявление Кэти, чтобы получать панировочные сухари для каждого элемента

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

Не стесняйтесь добавлять условие WHERE, например,

 WHERE ancestor.lft BETWEEN 6 AND 11

Answer 5

В итоге я сделал большое соединение, которое просто привязывает эту таблицу к себе снова и снова для каждого уровня.

Сначала я заполняю таблицу @topLevelGroups только группами 1-го уровня (если у вас есть только один корень, вы можете пропустить этот шаг), а затем @userGroups группами, которые может видеть пользователь.

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]

Это довольно большой взлом, и он, очевидно, ограничен определенным количеством уровней (для моего приложения есть разумный предел, который я могу выбрать), с проблемой того, что чем больше уровней поддерживается, тем больше количество присоединяется по экспоненте, и, следовательно, намного медленнее.

Делать это в коде, безусловно, проще, но для меня это просто не всегда вариант - бывают случаи, когда мне нужно, чтобы это было доступно непосредственно из SQL-запроса.

---

Я принимаю это как ответ, так как это то, что я в итоге сделал, и это может сработать для других людей - однако, если кто-то может придумать более эффективный метод, я его заменю.

Answer 6

нет специфичного для sql сервера кода, но вы просто ищете:

ВЫБРАТЬ * ИЗ таблицы ГДЕ слева <(currenttid.left) И справа> (currenttid.right)