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

Question

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

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

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

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

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

Answer 1

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

• бирка
• путь

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

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/%'

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

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

Answer 2

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

Answer 3

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

Скажем, ваша иерархия выглядит следующим образом: 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

Answer 4

Несколько способов здесь

Answer 5

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

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