Как реализовать систему тегов

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

Я думал о простом решении из трех таблиц: tagsтаблица, таблица articlesи tag_to_articlesтаблица.

Это лучшее решение проблемы или есть альтернативы? При использовании этого метода таблица со временем станет очень большой, и я полагаю, что для поиска это не слишком эффективно. С другой стороны, не так важно, чтобы запрос выполнялся быстро.

Думаю, вам будет интересно это сообщение в блоге: Теги: схемы баз данных

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

«MySQLicious» решение

В этом решении в схеме всего одна таблица, она денормализована. Этот тип называется «решением MySQLicious», потому что MySQLicious импортирует данные del.icio.us в таблицу с такой структурой.

Пересечение (И) Запрос «поиск + веб-сервис + semweb»:

SELECT *
FROM `delicious`
WHERE tags LIKE "%search%"
AND tags LIKE "%webservice%"
AND tags LIKE "%semweb%"

Union (OR) Запрос для «search | webservice | semweb»:

SELECT *
FROM `delicious`
WHERE tags LIKE "%search%"
OR tags LIKE "%webservice%"
OR tags LIKE "%semweb%"

Минус-запрос для «search + webservice-semweb»

SELECT *
FROM `delicious`
WHERE tags LIKE "%search%"
AND tags LIKE "%webservice%"
AND tags NOT LIKE "%semweb%"

Раствор «Скаттл»

Скаттл систематизирует свои данные в двух таблицах. Эта таблица scCategories является таблицей «тегов» и имеет внешний ключ к таблице «закладок».

Пересечение (И) Запрос для «закладка + веб-сервис + semweb»:

SELECT b.*
FROM scBookmarks b, scCategories c
WHERE c.bId = b.bId
AND (c.category IN ('bookmark', 'webservice', 'semweb'))
GROUP BY b.bId
HAVING COUNT( b.bId )=3

Сначала ищутся все комбинации закладки и тега, где тегом является «закладка», «веб-сервис» или «semweb» (c.category IN («закладка», «веб-сервис», «semweb»)), а затем только закладки, которые учитываются все три найденных тега (HAVING COUNT (b.bId) = 3).

Union (OR) Запрос для «bookmark | webservice | semweb»: просто опустите предложение HAVING, и у вас будет union:

SELECT b.*
FROM scBookmarks b, scCategories c
WHERE c.bId = b.bId
AND (c.category IN ('bookmark', 'webservice', 'semweb'))
GROUP BY b.bId

Минус (исключение) Запрос «закладка + веб-сервис-semweb», то есть: закладка И веб-сервис, А НЕ semweb.

SELECT b. *
FROM scBookmarks b, scCategories c
WHERE b.bId = c.bId
AND (c.category IN ('bookmark', 'webservice'))
AND b.bId NOT
IN (SELECT b.bId FROM scBookmarks b, scCategories c WHERE b.bId = c.bId AND c.category = 'semweb')
GROUP BY b.bId
HAVING COUNT( b.bId ) =2

Отсутствие HAVING COUNT приводит к запросу «закладка | webservice-semweb».

Раствор «Токси»

Toxi придумал структуру из трех столов. Через таблицу «tagmap» закладки и теги связаны n-к-m. Каждый тег можно использовать вместе с разными закладками и наоборот. Эта схема БД также используется wordpress. Запросы такие же, как и в решении «scuttle».

Пересечение (И) Запрос «закладка + веб-сервис + semweb»

SELECT b.*
FROM tagmap bt, bookmark b, tag t
WHERE bt.tag_id = t.tag_id
AND (t.name IN ('bookmark', 'webservice', 'semweb'))
AND b.id = bt.bookmark_id
GROUP BY b.id
HAVING COUNT( b.id )=3

Union (OR) Запрос для «закладка | веб-сервис | semweb»

SELECT b.*
FROM tagmap bt, bookmark b, tag t
WHERE bt.tag_id = t.tag_id
AND (t.name IN ('bookmark', 'webservice', 'semweb'))
AND b.id = bt.bookmark_id
GROUP BY b.id

Минус (исключение) Запрос «закладка + веб-сервис-semweb», то есть: закладка И веб-сервис, А НЕ semweb.

SELECT b. *
FROM bookmark b, tagmap bt, tag t
WHERE b.id = bt.bookmark_id
AND bt.tag_id = t.tag_id
AND (t.name IN ('Programming', 'Algorithms'))
AND b.id NOT IN (SELECT b.id FROM bookmark b, tagmap bt, tag t WHERE b.id = bt.bookmark_id AND bt.tag_id = t.tag_id AND t.name = 'Python')
GROUP BY b.id
HAVING COUNT( b.id ) =2

Отсутствие HAVING COUNT приводит к запросу «закладка | webservice-semweb».

Нет ничего плохого в вашем решении с тремя столами.

Другой вариант - ограничить количество тегов, которые можно применить к статье (например, 5 в SO), и добавить их непосредственно в таблицу статей.

Нормализация БД имеет свои преимущества и недостатки, точно так же, как жесткое объединение вещей в одну таблицу имеет преимущества и недостатки.

Ничто не говорит о том, что нельзя делать и то, и другое. Повторение информации противоречит парадигмам реляционных БД, но если целью является производительность, возможно, вам придется нарушить парадигмы.

Предложенная вами реализация трех таблиц будет работать с тегами.

Однако переполнение стека использует другую реализацию. Они хранят теги в столбце varchar в таблице сообщений в виде обычного текста и используют полнотекстовую индексацию для извлечения сообщений, соответствующих тегам. Например posts.tags = "algorithm system tagging best-practices". Я уверен, что Джефф где-то упоминал об этом, но я забыл где.

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

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

Я хотел бы предложить оптимизированный MySQLicious для лучшей производительности. До этого недостатками раствора Toxi (3 таблица) было

Если у вас есть миллионы вопросов, и в каждом из них по 5 тегов, то в таблице tagmap будет 5 миллионов записей. Итак, сначала мы должны отфильтровать 10 тысяч записей карты тегов на основе поиска по тегам, а затем снова отфильтровать соответствующие вопросы из этих 10 тысяч. Таким образом, при фильтрации, если художественный идентификатор является простым числовым, тогда это нормально, но если это своего рода UUID (32 varchar), тогда для фильтрации требуется большее сравнение, хотя оно индексируется.

Мое решение:

Каждый раз, когда создается новый тег, используйте counter ++ (base 10) и преобразуйте этот счетчик в base64. Теперь у каждого имени тега будет идентификатор base64. и передайте этот идентификатор в пользовательский интерфейс вместе с именем. Таким образом, у вас будет максимум два идентификатора char, пока в нашей системе не будет создано 4095 тегов. Теперь объедините эти несколько тегов в каждый столбец тегов таблицы вопросов. Также добавьте разделитель и отсортируйте его.

Итак, таблица выглядит так

При запросе запрашивайте идентификатор вместо реального имени тега. Поскольку он СОРТИРОВАН , andусловие для тега будет более эффективным ( LIKE '%|a|%|c|%|f|%).

Обратите внимание, что одинарного разделителя пробелов недостаточно, и нам нужен двойной разделитель, чтобы различать такие теги, как sqlи, mysqlпотому что также LIKE "%sql%"будут возвращаться mysqlрезультаты. Должно бытьLIKE "%|sql|%"

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

Наконец, с этим решением не требуется внутреннее соединение, когда миллион записей нужно сравнивать с 5 миллионами записей по условию соединения.

CREATE TABLE Tags (
    tag VARHAR(...) NOT NULL,
    bid INT ... NOT NULL,
    PRIMARY KEY(tag, bid),
    INDEX(bid, tag)
)

Примечания:

• Это лучше, чем TOXI, поскольку в нем нет лишних таблиц many: many, что затрудняет оптимизацию.
• Конечно, мой подход может быть немного более громоздким (чем TOXI) из-за избыточных тегов, но это небольшой процент от всей базы данных, и повышение производительности может быть значительным.
• Он хорошо масштабируется.
• У него нет (потому что он не нужен) суррогатного AUTO_INCREMENTПК. Следовательно, это лучше, чем Scuttle.
• MySQLicious отстой, потому что он не может использовать индекс ( LIKEс ведущим подстановочным знаком ; ложные попадания в подстроки)
• Для MySQL обязательно используйте ENGINE = InnoDB, чтобы получить эффекты «кластеризации».

Связанные обсуждения (для MySQL):
many: many упорядоченные списки оптимизации таблиц сопоставления