Рекурсивный SQL для системы меню

Question

У меня есть таблица для системы меню со следующей структурой и некоторыми данными.

ID, Text, ParentID, DestinationID
1, Applications, (null), (null)
2, Games, (null), (null)
3, Office, 1, (null)
4, Text Editing, 1, (null)
5, Media, (null), (null)
6, Word, 3, 1
7, Excel, 3, 2
8, Crysis, 2, 3

Мне нужен запрос, по которому я могу передать идентификатор меню, и он вернет список элементов, которые имеют этот идентификатор как дочерний элемент. НО, мне нужно, чтобы он возвращал только тех детей, у которых есть правильный путь к месту назначения. Таким образом, в приведенном выше примере пользователю изначально будет показано (Приложения, Игры), когда он выберет Приложения, ему будет представлено (Офис). Редактирование текста и мультимедиа должны быть опущены, поскольку под ними нет действительных пунктов назначения.

Самое хитрое в этом то, что нет предопределенной глубины для какого-либо меню.

EDIT

Сегодня проблема возникла для MS SQL 2008, но в последние 2 недели мне нужны были похожие решения для SQLite и SQL CE. Идеальное решение не должно быть привязано к какому-либо конкретному механизму SQL.

Answer 1

Только для SQL-сервера, но это звучит как задание для Общих табличных выражений .

Answer 2

Если иерархия / дерево, которое вы создаете в своей базе данных, меняется не очень часто, я бы рекомендовал использовать модифицированный алгоритм обхода дерева предзаказов (MPTT) . Это потребует другой схемы таблиц, но позволит вам запросить целое поддерево с помощью простого оператора SQL (без рекурсии и т. Д.).

В статье Хранение иерархических данных в базе данных подробно описывается этот метод.

В вашем примере вы получите следующее дерево, где я называю красные числа значением left и значением green right узла.

Теперь, если вы хотите выбрать поддерево Office , вы можете сделать это с помощью:

SELECT * FROM tree WHERE left BETWEEN 10 AND 15 AND destination IS NOT NULL

Если ваша БД не поддерживает оператор BETWEEN, вы, конечно, можете написать влево> 10 И влево <15. </p>

Ваш стол будет выглядеть так:

name         | left | right | destination
------------------------------------------ 
root         | 1    | 17    | NULL
Applications | 7    |  16   |  ...
...

Answer 3

В Oracle:

SELECT m.*, level
FROM my_table m
START WITH
  Id = :startID
CONNECT BY
  ParentID = PRIOR Id
  AND DestinationID IS NOT NULL

Нет способа сделать это в ANSI SQL с помощью одного запроса. Вы можете создать дополнительный столбец AccessPath для вашей таблицы:

ID, Text, ParentID, DestinationID AccessPath
1, Applications, (null), (null), "1"
2, Games, (null), (null), "2"
3, Office, 1, (null), "1.3"
4, Text Editing, 1, (null), "1.4"
5, Media, (null), (null), "5"
6, Word, 3, 1, "1.3.6"
7, Excel, 3, 2, "1.3.7"
8, Crysis, 2, 3, "1.2.8"

и запрос:

SELECT mp.Id, mp.Text
FROM my_table mp, my_table mc
WHERE mp.parentID = @startingParent
 AND mc.Id <> mp.Id
 AND SUBSTR(mc.AccessPath, LENGTH(mp.AccessPath)) = mp.AccessPath
GROUP BY
 mp.Id, mp.Text

Плохо начинать с NULL, так как индекс в ParentID не может быть использован в этом случае. Для начала используйте подделку parentID из 0 вместо NULL.

Answer 4

Как уже отмечали другие, в стандартном ANSI SQL нет способа сделать то, что вы хотите. Для чего-то подобного я однажды реализовал в SQL 2000 систему для отслеживания компонентов продуктов, созданных бывшим работодателем - каждый «продукт» может быть атомарным компонентом, например, винтом A500. Этот компонент может использоваться в «составных» компонентах: некоторые винты A500 плюс 6 деревянных досок B120 соответствовали «стильному ящику для инструментов» C90. Эта коробка, плюс еще винты и мотор "M500" могут соответствовать инструменту для ковров.

Я разработал таблицу «Продукт» так:

ID, PartName, Description
1, A500, "Screw A500"
2, B120, "Wood panel B120"
3, C90, "Stylish tool box C90"
4, M500, "Wood cutter M500"

И таблица «ProductComponent» выглядит следующим образом:

Hierarchy, ComponentID, Amount
0301, 1, 24
0302, 2, 6
0401, 1, 3
0402, 3, 1
0403, 4, 1
040201, 1, 24
040202, 2, 6

Хитрость в том, что иерархия полей - это VARCHAR с первыми 2 символами, представляющими ID каждого продукта, каждая следующая пара символов идентифицирует узел в дереве. Итак, мы видим, что продукт 3 зависит от 2 других продуктов. Продукт 4 зависит также от двух других, один из которых зависит от его части от двух других.

В этой модели много избыточности, но она позволяет легко рассчитать, сколько винтов вам нужно для конкретного продукта, быстро определить, для каких деталей требуются деревянные панели, или получить список всех компонентов, от которых в конечном итоге зависит продукт (включая косвенные зависимости) и т. д. А сканирование дерева ниже определенного уровня - это простой запрос LIKE!

Используя 2 символа в шестнадцатеричном представлении, я ограничил продукт прямой зависимостью максимум от 256 других продуктов (что, в свою очередь, может зависеть от чего-то другого). Вы можете изменить это, чтобы использовать базу 36 (26 букв плюс 10 цифр) или базу 64, если вам нужно больше.

Кроме того, эта табличная модель очень хорошо работает на Access и mySQL. Чего вы не можете иметь, так это циклических зависимостей.

Answer 5

Если это проблема, которая вас интересует (или беспокоит), вы можете проверить: Деревья и иерархии Джо Селко в SQL для умных людей .

Answer 6

https://geeks.ms/jirigoyen/2009/05/22/recursividad-con-sql-server/

ALTER PROCEDURE [dbo].[Usuarios_seguridad_seleccionar]
AS
BEGIN    

    DECLARE @minClave int
    SELECT @minClave = MIN(Clave) FROM dbo.Usuarios_seguridad;

    WITH UsuariosAccesos AS(

        SELECT top 1 us1.Padre,us1.Clave,us1.Variable,us1.Modulo,us1.Contenido,us1.Acceso,us1.Imagen 
        FROM dbo.Usuarios_seguridad us1 
        WHERE us1.Clave = @minClave
        UNION ALL
        SELECT top 100 percent us2.Padre,us2.Clave,us2.Variable,us2.Modulo,us2.Contenido,us2.Acceso,us2.Imagen 
        FROM dbo.Usuarios_seguridad us2 
        INNER JOIN UsuariosAccesos AS us3 ON us3.Clave = us2.Padre  
        WHERE us2.Clave <> @minClave 
    )

    SELECT TOP 100 PERCENT ia.Padre,ia.Clave,ia.Variable,ia.Modulo,ia.Contenido,ia.Acceso,ia.Imagen 
    FROM UsuariosAccesos ia
    ORDER BY padre, clave
END
GO

Answer 7

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

это даст

ID, Item, parentID
1, Applications, (null)
2, Games, (null)
3, Office, 1
4, Text Editing, 1
5, Media, (null)
6, Word, 3
7, Excel, 3
8, Crysis, 2

например ...

слово> офис> приложения и ...

excel> офис> приложения

... предположительно должен находиться в том же пункте меню (родительский идентификатор 3)

Я не уверен, как вы выбираете меню, но я буду работать по принципу, что есть начальная кнопка меню, установленная с (нулевым) в качестве ее параметра, и каждый последующий щелчок динамически удерживает следующий параметр в последовательности (что похоже соответствует вашим комментариям)

например.

щелкните меню верхнего уровня: - значение равно (null)

нажмите приложения: - значение 1

нажмите Офис: - значение 3

и т.д.

Если предположить, что destinationID ничего не делает, кроме показа активной дочерней ссылки (позволяющей удалить ее), код будет выглядеть следующим образом:

with items (nodeID, PID, list) as
  (select id, ParentID, item
    from menu
    where id = 9
    union all
  select id, ParentID, item
    from menu
    inner join items on nodeID = menu.ParentID
  )
select *
from items 
where (pid = 9)
and nodeID in (select parentid from menu) 

Это работает в MSSQL 2005 +

Если вам нужен идентификатор назначения по какой-либо другой причине, вы можете изменить код следующим образом (например, если вам нужно вернуть самый низкий уровень, где идентификатор узла не был установлен в качестве родительского идентификатора, например):

with items (nodeID, PID, list, dest) as
  (select id, ParentID, item, destinationID
    from menu
    where id = 9
    union all
  select id, ParentID, item, destinationID
    from menu
    inner join items on nodeID = menu.ParentID
)
select *
from items 
where (pid = 9)
and (nodeID in (select parentid from menu) 
  or dest is not null)

Answer 8

SQL не очень хорош для обхода произвольных иерархий глубины.

Если таких записей меньше 1000, я бы взял их все в приложении и построил там график.

Если существует более 1000 таких записей, я бы сгруппировал их в необработанные поддеревья примерно по 1000 (добавив внешний ключ SubtreeID) и извлек каждое из поддеревьев ... затем построил график поддерева в приложении.