Иерархическое тегирование в SQL

Question

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

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

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

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

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

Answer 1

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

Answer 2

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

• тег
• путь

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

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 3

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

Answer 4

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

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

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

[Редактировать] После прочтения статьи Али я провел еще несколько поисков и нашел это презентация о множестве подходов к реализации иерархий в postgres.Все еще может быть полезно в пояснительных целях.