Иерархическая маркировка в SQL

У меня есть веб-приложение PHP, которое использует базу данных MySQL для тегирования объектов, в котором я использовал структуру тегов, принятую в качестве ответа на этот вопрос SO.

Я хотел бы реализовать иерархию тегов, где каждый тег может иметь уникальный родительский тег. Тогда поиск родительского тега T будет соответствовать всем потомкам T (т. Е. Тегам T, родительским тегом T (дочерние элементы T), внуки T и т. Д.).

Самый простой способ сделать это, по-видимому, - добавить поле ParentID в таблицу тегов, которое содержит идентификатор родительского тега тега или какое-то магическое число, если у тега нет родительского элемента. Однако поиск потомков требует повторных полных поисков в базе данных для поиска тегов в каждом «поколении», чего я бы хотел избежать.

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

Есть ли хороший способ быстро выполнять запросы для поиска потомков, сохраняя при этом данные как можно более нормализованными?


mysql sql database tags normalizing
person Chris Johnson    schedule 02.11.2008    source источник

Ответы (5)


arrow_upward
9
arrow_downward

Я реализовал это с помощью двух столбцов. Я немного упрощаю его здесь, потому что мне пришлось оставить имя тега в отдельном поле / таблице, потому что мне пришлось локализовать его для разных языков:

  • тег
  • дорожка

Посмотрите, например, на эти строки:

tag            path
---            ----
database       database/
mysql          database/mysql/
mysql4         database/mysql/mysql4/
mysql4-1       database/mysql/mysql4-1/
oracle         database/oracle/
sqlserver      database/sqlserver/
sqlserver2005  database/sqlserver/sqlserver2005/
sqlserver2005  database/sqlserver/sqlserver2008/

и Т. Д.

Используя оператор like в поле пути, вы можете легко получить все необходимые строки тегов:

SELECT * FROM tags WHERE path LIKE 'database/%'

Есть некоторые детали реализации, например, когда вы перемещаете узел в иерархии, вам также нужно изменить всех дочерних элементов и т. Д., Но это несложно.

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

person splattne    schedule 02.11.2008
comment
Я почти наверняка собираюсь использовать это в будущем. Спасибо! - person Stephen Walcher; 02.11.2008
comment
Что, если у тега может быть несколько путей (n: m)? Есть ли решение, которое я просто не вижу прямо сейчас? - person Dong3000; 26.11.2019

arrow_upward
2
arrow_downward

В ответе Али есть ссылка на Деревья и иерархии Джо Селко в SQL for Smarties, что подтверждает мои подозрения - не существует простой структуры базы данных, предлагающей лучшее из всех миров. Лучшим для моей цели, по-видимому, является «Дерево частой вставки», подробно описанное в этой книге, которое похоже на «Модель вложенного набора» ссылки Али, но с непоследовательной индексацией. Это позволяет вставку O (1) (как неструктурированная нумерация строк BASIC) с периодической реорганизацией индекса по мере необходимости.

person Chris Johnson    schedule 02.11.2008

arrow_upward
1
arrow_downward

Вот несколько способов

person Ali Afshar    schedule 02.11.2008

arrow_upward
1
arrow_downward

Вы можете построить то, что Кимбалл называет таблицей помощников по иерархии.

Допустим, ваша иерархия выглядит так: A -> B | B -> C | C -> D

вы бы вставили записи в таблицу, которая выглядит так

ParentID, ChildID, Depth, Highest Flag, Lowest Flag
A, A, 0, Y, N
A, B, 1, N, N
A, C, 2, N, N
A, D, 3, N, Y
B, B, 0, N, N
B, C, 1, N, N
B, D, 2, N, Y
C, C, 0, N, N
C, D, 1, N, Y
D, D, 0. N, Y

Я думаю, что это правильно .... в любом случае. Дело в том, что вы по-прежнему правильно храните свою иерархию, вы просто создаете эту таблицу ИЗ своей правильной таблицы. ЭТА таблица запрашивает как Банши. Допустим, вы хотите знать, что такое первый уровень ниже B.

WHERE parentID = 'B' and Depth = 1
person Community    schedule 03.11.2008

arrow_upward
0
arrow_downward

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

[Edit] Прочитав статью Али, я еще немного поохотился и нашел эту презентацию на набор подходов для реализации иерархий в postgres. Может все еще быть полезным для пояснительных целей.

person Dana the Sane    schedule 02.11.2008