Дизайн базы данных для тегов

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

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

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

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

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

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

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

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

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

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

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

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 из них, тогда это все равно будет тяжелым в базе данных.

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

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

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

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

Самый простой способ - создать таблицу тегов.
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]

ОБНОВЛЕНИЕ
В соответствии с вашими требованиями к И условиям, приведенный выше запрос будет выглядеть примерно так

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]

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

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

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

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

Вы не сможете избежать объединений и все равно будете несколько нормализованы.

Мой подход - иметь таблицу тегов.

 TagId (PK)| TagName (Indexed)

Затем у вас есть столбец TagXREFID в таблице элементов.

Этот столбец TagXREFID является FK для третьей таблицы, я назову ее TagXREF:

 TagXrefID | ItemID | TagId

Итак, получить все теги для элемента можно примерно так:

SELECT Tags.TagId,Tags.TagName 
     FROM Tags,TagXref 
     WHERE TagXref.TagId = Tags.TagId 
         AND TagXref.ItemID = @ItemID

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

SELECT * FROM Items, TagXref
     WHERE TagXref.TagId IN 
          ( SELECT Tags.TagId FROM Tags
                WHERE Tags.TagName = @TagName; )
     AND Items.ItemId = TagXref.ItemId;

Чтобы объединить несколько тегов AND, вам следует немного изменить приведенный выше оператор, добавив AND Tags.TagName = @ TagName1 AND Tags.TagName = @ TagName2 и т. Д. И динамически построить запрос.

Мне нравится иметь несколько таблиц, которые представляют необработанные данные, поэтому в этом случае у вас будет

Items (ID pk, Name, <properties>)
Tags (ID pk, Name)
TagItems (TagID fk, ItemID fk)

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

Решением для улучшения чтения является создание таблицы кэширования по команде путем настройки хранимой процедуры, которая по существу создает новую таблицу, представляющую данные в плоском формате ...

CachedTagItems(ID, Name, <properties>, tag1, tag2, ... tagN)

Затем вы можете определить, как часто нужно обновлять таблицу Tagged Item, если она присутствует при каждой вставке, а затем вызывать хранимую процедуру в событии вставки курсора. Если это почасовая задача, настройте ежечасное задание для ее выполнения.

Теперь, чтобы по-настоящему умно извлекать данные, вам нужно создать хранимую процедуру для получения данных из тегов. Вместо того, чтобы использовать вложенные запросы в массивном операторе case, вы хотите передать один параметр, содержащий список тегов, которые вы хотите выбрать из базы данных, и вернуть набор записей Items. Лучше всего в двоичном формате с использованием побитовых операторов.

В двоичном формате это легко объяснить. Допустим, элементу нужно присвоить четыре тега, в двоичном формате мы могли бы представить это

0000

Если все четыре тега назначены объекту, объект будет выглядеть так ...

1111

Если бы только первые два ...

1100

Тогда это просто случай нахождения двоичных значений с единицами и нулями в нужном столбце. Используя побитовые операторы SQL Server, вы можете проверить, стоит ли 1 в первом столбце, с помощью очень простых запросов.

Перейдите по этой ссылке, чтобы узнать дополнительную информацию.

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

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

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

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

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

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

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