Сведение иерархии списка смежности к списку всех путей
-
11-09-2019 - |
Вопрос
У меня есть таблица, в которой хранится иерархическая информация с использованием модели списка смежности.(использует самоссылающийся ключ — пример ниже.Эта таблица может выглядеть привычный):
category_id name parent
----------- -------------------- -----------
1 ELECTRONICS NULL
2 TELEVISIONS 1
3 TUBE 2
4 LCD 2
5 PLASMA 2
6 PORTABLE ELECTRONICS 1
7 MP3 PLAYERS 6
8 FLASH 7
9 CD PLAYERS 6
10 2 WAY RADIOS 6
Каков наилучший способ «сгладить» приведенные выше данные во что-то вроде этого?
category_id lvl1 lvl2 lvl3 lvl4
----------- ----------- ----------- ----------- -----------
1 1 NULL NULL NULL
2 1 2 NULL NULL
6 1 6 NULL NULL
3 1 2 3 NULL
4 1 2 4 NULL
5 1 2 5 NULL
7 1 6 7 NULL
9 1 6 9 NULL
10 1 6 10 NULL
8 1 6 7 8
Каждая строка представляет собой один «Путь» в Иерархии, за исключением строки для каждый узел (не только каждый листовой узел).Столбец Category_id представляет текущий узел, а столбцы «lvl» — его предков.Значение текущего узла также должно находиться в крайнем правом столбце уровня.Значение в столбце lvl1 всегда будет представлять корневой узел, значения в lvl2 всегда будут представлять прямых потомков lvl1 и так далее.
Если возможно, метод генерации этих результатов будет использовать SQL и будет работать для n-уровневых иерархий.
Решение
Выполнение многоуровневых запросов к простому списку смежности всегда требует левого соединения.Сделать таблицу с выравниванием по правому краю легко:
SELECT category.category_id,
ancestor4.category_id AS lvl4,
ancestor3.category_id AS lvl3,
ancestor2.category_id AS lvl2,
ancestor1.category_id AS lvl1
FROM categories AS category
LEFT JOIN categories AS ancestor1 ON ancestor1.category_id=category.category_id
LEFT JOIN categories AS ancestor2 ON ancestor2.category_id=ancestor1.parent
LEFT JOIN categories AS ancestor3 ON ancestor3.category_id=ancestor2.parent
LEFT JOIN categories AS ancestor4 ON ancestor4.category_id=ancestor3.parent;
Выровнять его по левому краю, как в вашем примере, немного сложнее.Это приходит на ум:
SELECT category.category_id,
ancestor1.category_id AS lvl1,
ancestor2.category_id AS lvl2,
ancestor3.category_id AS lvl3,
ancestor4.category_id AS lvl4
FROM categories AS category
LEFT JOIN categories AS ancestor1 ON ancestor1.parent IS NULL
LEFT JOIN categories AS ancestor2 ON ancestor1.category_id<>category.category_id AND ancestor2.parent=ancestor1.category_id
LEFT JOIN categories AS ancestor3 ON ancestor2.category_id<>category.category_id AND ancestor3.parent=ancestor2.category_id
LEFT JOIN categories AS ancestor4 ON ancestor3.category_id<>category.category_id AND ancestor4.parent=ancestor3.category_id
WHERE
ancestor1.category_id=category.category_id OR
ancestor2.category_id=category.category_id OR
ancestor3.category_id=category.category_id OR
ancestor4.category_id=category.category_id;
будет работать для n-уровневых иерархий.
К сожалению, запросы произвольной глубины в модели списка смежности невозможны.Если вы часто выполняете запросы такого типа, вам следует изменить свою схему на одну из другие модели хранения иерархической информации:полное отношение смежности (хранение всех отношений «предок-потомок»), материализованный путь или вложенные наборы.
Если категории не сильно меняются (что обычно имеет место для такого магазина, как ваш пример), я бы склонялся к вложенным наборам.
Другие советы
Как уже упоминалось, в SQL нет чистого способа реализации таблиц с динамически изменяющимся количеством столбцов.Единственные два решения, которые я использовал раньше:1.Фиксированное число самостоятельных дел, дающее фиксированное количество столбцов (согласно Bobince) 2.Генерация результатов в виде строки в одном столбце
Второе поначалу звучит гротескно;хранить идентификаторы в виде строки?!Но когда выходные данные форматируются как XML или что-то в этом роде, люди, похоже, не особо возражают.
Точно так же от этого будет очень мало пользы, если вы затем захотите объединить результаты в SQL.Если результат должен быть передан в приложение, он может быть очень подходящим.Однако лично я предпочитаю выполнять выравнивание в приложении, а не в SQL.
Я застрял здесь на 10-дюймовом экране без доступа к SQL, поэтому не могу предоставить протестированный код, но основным методом было бы каким-то образом использовать рекурсию;
- Рекурсивная скалярная функция может это сделать
- MS SQL может сделать это с помощью рекурсивного оператора With (более эффективно).
Скалярная функция (что-то вроде):
CREATE FUNCTION getGraphWalk(@child_id INT)
RETURNS VARCHAR(4000)
AS
BEGIN
DECLARE @graph VARCHAR(4000)
-- This step assumes each child only has one parent
SELECT
@graph = dbo.getGraphWalk(parent_id)
FROM
mapping_table
WHERE
category_id = @child_id
AND parent_id IS NOT NULL
IF (@graph IS NULL)
SET @graph = CAST(@child_id AS VARCHAR(16))
ELSE
SET @graph = @graph + ',' + CAST(@child_id AS VARCHAR(16))
RETURN @graph
END
SELECT
category_id AS [category_id],
dbo.getGraphWalk(category_id) AS [graph_path]
FROM
mapping_table
ORDER BY
category_id
Я давно не использовал рекурсивный оператор With, но попробую синтаксис, хотя у меня здесь нет SQL, чтобы что-либо проверить :)
Рекурсивное СО
WITH
result (
category_id,
graph_path
)
AS
(
SELECT
category_id,
CAST(category_id AS VARCHAR(4000))
FROM
mapping_table
WHERE
parent_id IS NULL
UNION ALL
SELECT
mapping_table.category_id,
CAST(result.graph_path + ',' + CAST(mapping_table.category_id AS VARCHAR(16)) AS VARCHAR(4000))
FROM
result
INNER JOIN
mapping_table
ON result.category_id = mapping_table.parent_id
)
SELECT
*
FROM
result
ORDER BY
category_id
РЕДАКТИРОВАТЬ - ВЫВОД для обоих одинаков:
1 '1'
2 '1,2'
3 '1,2,3'
4 '1,2,4'
5 '1,2,5'
6 '1,6'
7 '1,6,7'
8 '1,6,7,8'
9 '1,6,9'
Обход дерева произвольной глубины обычно включает в себя рекурсивный процедурный код, если только вы не используете специальные возможности некоторых СУБД.
В Oracle предложение CONNECT BY позволит вам пройти по дереву в первом порядке в глубину, если вы используете список смежности, как вы это сделали здесь.
Если вы используете вложенные наборы, левый порядковый номер укажет вам порядок посещения узлов.
На самом деле это можно сделать с помощью динамического SQL внутри процедуры сохранения.Тогда вы будете ограничены тем, что можно сделать с помощью хранимой процедуры.Очевидно, что становится проблемой выполнить EXEC результаты во временную таблицу, не зная, сколько столбцов ожидать.Однако, если целью является вывод на веб-страницу или другой пользовательский интерфейс, возможно, усилия того стоят...