Свести иерархию списка смежности к списку всех путей - PullRequest
8 голосов
/ 19 апреля 2009

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

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" - его предки. Значение для текущего узла также должно быть в самом дальнем правом столбце lvl. Значение в столбце lvl1 всегда будет представлять корневой узел, значения в lvl2 всегда будут представлять прямых потомков lvl1 и т. Д.

Если возможно, метод генерации этого вывода будет в SQL и будет работать для n-уровневых иерархий.

Ответы [ 4 ]

11 голосов
/ 19 апреля 2009

Для выполнения многоуровневых запросов по простому списку смежности всегда требуются самостоятельные соединения слева. Создать таблицу с выравниванием по правому краю легко:

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-уровневых иерархий.

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

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

8 голосов
/ 19 апреля 2009

Как уже упоминалось, в SQL нет чистого способа реализации таблиц с динамически изменяющимся числом столбцов. Единственные два решения, которые я использовал ранее: 1. Фиксированное число Self-Joins, дающее фиксированное количество столбцов (AS на 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'
1 голос
/ 19 апреля 2009

Обход дерева произвольной глубины обычно включает рекурсивный процедурный код, если только вы не используете специальные функции некоторых СУБД.

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

Если вы используете вложенные наборы, левый порядковый номер предоставит вам порядок посещения узлов.

0 голосов
/ 22 июля 2012

На самом деле это можно сделать с помощью динамического SQL в рамках процедуры хранилища. Затем вы ограничиваетесь тем, что можно сделать с помощью хранимой процедуры. Очевидно, что становится проблемой ВЫПОЛНИТЬ результаты во временную таблицу, не зная, сколько столбцов ожидать. Однако, если целью является вывод на веб-страницу или другой пользовательский интерфейс, то это может стоить усилий ...

...