Проектирования баз данных для Tagging

Question

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

• элементы могут иметь большое количество тегов
• поиска по всем пунктам, которые помечены с заданным набором тегов должен быть быстрым (детали должны иметь все теги, так что это и поиска данных, а не OR-поиск)
• создания/написания элементов может быть медленнее, чтобы обеспечить быстрый поиск/чтение

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

Любые идеи?

---

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

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

Answer 1

О ANDing: Похоже, вы ищете операцию «реляционного деления». This article охватывает реляционное разделение кратким и при этом понятным образом.

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

Answer 2

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

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

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 ... 

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

Answer 3

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

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

Мой подход заключается в том, чтобы иметь таблицу меток.

TagId (PK)| TagName (Indexed) 

Затем у вас есть столбец TagXREFID в таблице ваших товаров.

Этот столбец TagXREFID является FK на 3 стола, я буду называть его 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; 

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

Answer 5

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

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

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

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

Answer 6

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

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

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

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

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

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

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

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

0000 

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

1111 

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

1100 

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

Проверьте эту ссылку, чтобы найти more.

Answer 7

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

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

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

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

Answer 8

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

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

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

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

Answer 9

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

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

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

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

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

Answer 10

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

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

Answer 11

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

Answer 12

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

what's the utility of array type?