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

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

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

• Узел А
  • Узел Б
    • Узел С
  • Узел Д
    • Узел Е
    • Узел 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))

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

---

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

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

Это на SQL Server 2005.

Answer 1

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

Сначала я заполняю таблицу @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 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

Хорошо.Это для 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 4

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

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 и далее (псевдокод):

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

Answer 5

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

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 6

нет конкретного кода sql-сервера, но вы просто ищете:

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