Дизайн базы данных для маркировки

Question

Как бы вы разработали базу данных для поддержки следующих функций тегирования:

• элементы могут иметь большое количество тегов
• поиск всех элементов, помеченных данным набором тегов, должен быть быстрым (элементы должны иметь ВСЕ теги, так что это поиск И, а не ИЛИ)
• создание / запись элементов может быть медленнее, чтобы включить быстрый поиск / чтение

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

Есть идеи?

---

Спасибо за все ответы.

Однако, если я не ошибаюсь, приведенные ответы показывают, как выполнять ИЛИ-поиск по тегам. (Выберите все элементы, которые имеют один или несколько тегов n). Я ищу эффективный И-поиск. (Выберите все элементы, которые имеют ВСЕ n тегов - и, возможно, больше.)

Answer 1

Вот хорошая статья о маркировке схем базы данных:

http://howto.philippkeller.com/2005/04/24/Tags-Database-schemas/

вместе с тестами производительности:

http://howto.philippkeller.com/2005/06/19/Tagsystems-performance-tests/

Обратите внимание, что сделанные там выводы очень специфичны для MySQL, который (по крайней мере, в 2005 году на момент написания) имел очень плохие характеристики полнотекстовой индексации.

Answer 2

Об ANDing: Похоже, вы ищете операцию «реляционного деления». Эта статья охватывает реляционное деление в сжатой и понятной форме.

О производительности: интуитивно понятный подход, основанный на растровых изображениях, подходит для ситуации. Тем не менее, я не уверен, что это хорошая идея для реализации индексации растровых изображений «вручную», как предлагает digiguru: это звучит как сложная ситуация, когда добавляются новые теги (?) Но некоторые СУБД (включая Oracle) предлагают индексы растровых изображений, которые могут каким-то образом быть полезным, потому что встроенная система индексации устраняет потенциальную сложность ведения индекса; Кроме того, СУБД, предлагающая растровые индексы, должна быть в состоянии учитывать их при выполнении плана запроса.

Answer 3

Я не вижу проблемы с простым решением: таблица для элементов, таблица для тегов, перекрестная таблица для «тегирования»

Индексы на кросс-таблице должны быть достаточно оптимизационными. Выбор подходящих предметов будет

SELECT * FROM items WHERE id IN  
    (SELECT DISTINCT item_id FROM item_tag WHERE  
    tag_id = tag1 OR tag_id = tag2 OR ...)  

И пометка будет

SELECT * FROM items WHERE  
    EXISTS (SELECT 1 FROM item_tag WHERE id = item_id AND tag_id = tag1)  
    AND EXISTS (SELECT 1 FROM item_tag WHERE id = item_id AND tag_id = tag2)  
    AND ...

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

Answer 4

Я просто хотел подчеркнуть, что статья, на которую ссылается @Jeff Atwood (http://howto.philippkeller.com/2005/04/24/Tags-Database-schemas/)), очень тщательная (в ней рассматриваются достоинства трех различных подходов к схеме) и имеет хорошее решение для запросов AND, которые обычно работать лучше, чем было упомянуто здесь (т.е. он не использует коррелированный подзапрос для каждого термина). Также много хороших вещей в комментариях.

ps - подход, о котором все говорят здесь, упоминается как решение "Toxi" в статье.

Answer 5

Возможно, вы захотите поэкспериментировать с решением не строго в базе данных, таким как Java Content Repository реализация (например, Apache Jackrabbit ) и использовать поисковую систему, построенную на основе подобных Apache Lucene .

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

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

РЕДАКТИРОВАТЬ: с вашим разъяснением кажется более убедительным использование решения, подобного JCR, с поисковой системой. Это значительно упростит ваши программы в долгосрочной перспективе.

Answer 6

Самый простой способ - создать таблицу tags .
Target_Type - если вы помечаете несколько таблиц
Target - ключ к тегу записи
Tag - текст тега

Запрос данных будет выглядеть примерно так:

Select distinct target from tags   
where tag in ([your list of tags to search for here])  
and target_type = [the table you're searching]

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

select target
from (
  select target, count(*) cnt 
  from tags   
  where tag in ([your list of tags to search for here])
    and target_type = [the table you're searching]
)
where cnt = [number of tags being searched]

Answer 7

Второе предложение @Zizzencs, что вам может понадобиться что-то, что не полностью (R) ориентировано на DB

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

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

Возможно, вы захотите подумать, стоит ли дополнительная сложность.

Answer 8

Если у вас тип массива, вы можете предварительно агрегировать необходимые данные. Смотрите этот ответ в отдельной теме:

что за утилита типа массива?

Answer 9

Вариант с ответом выше - взять идентификаторы тегов, отсортировать их, объединить в виде ^ разделенной строки и хэшировать их Затем просто свяжите хеш с элементом. Каждая комбинация тегов создает новый ключ. Чтобы выполнить поиск AND, просто заново создайте хеш с указанными идентификаторами тегов и выполните поиск. Изменение тегов на элементе приведет к воссозданию хеша. Элементы с одинаковым набором тегов имеют одинаковый хэш-ключ.

Answer 10

Перефразируя то, что говорили другие: уловка не в схеме , а в запросе .

Наивная схема Entities / Labels / Tags - правильный путь. Но, как вы видели, не сразу понятно, как выполнить запрос AND с большим количеством тегов.

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

У меня есть несколько предложений по MS SQL, но я воздержусь, если это не та платформа, которую вы используете.