Diseño de base de datos para el etiquetado

Question

¿Cómo diseñar una base de datos para apoyar las siguientes características de etiquetas:

• artículos pueden tener un gran número de etiquetas
• búsquedas para todos los elementos que están etiquetadas con un determinado conjunto de etiquetas debe ser rápido (los artículos deben tener todas las etiquetas, por lo que es un Y-búsqueda, no un O-búsqueda)
• crear/escribir artículos puede ser más lenta para permitir la búsqueda rápida/lectura

Idealmente, las operaciones de búsqueda de todos los artículos que están etiquetados con (al menos) un conjunto de n etiquetas dadas deben hacerse usando una sola instrucción SQL. Como el número de etiquetas para buscar así como el número de etiquetas en cualquier elemento son desconocidas y pueden ser altas, el uso de JOINs no es práctico.

¿Alguna idea?

---

Gracias por todas las respuestas hasta el momento.

Sin embargo, si no me equivoco, las respuestas proporcionadas muestran cómo hacer una búsqueda OR en las etiquetas. (Seleccione todos los artículos que tienen una o más n etiquetas). Estoy buscando una búsqueda AND eficiente. (Seleccionar todos los elementos que tienen todas las etiquetas n - y posiblemente más.)

Answer 1

Acerca de ANDing: Parece que está buscando la operación de "división relacional". This article cubre la división relacional de manera concisa pero comprensible.

Acerca del rendimiento: Un enfoque basado en mapas de bits suena intuitivamente que se adaptará bien a la situación. Sin embargo, no estoy convencido de que sea una buena idea implementar la indexación de bitmap "manualmente", como digiguru sugiere: suena como una situación complicada cada vez que se agregan nuevas etiquetas (?) Pero algunos DBMSes (incluido Oracle) ofrecen índices de mapa de bits que de alguna manera ser útil, porque un sistema de indexación incorporado elimina la complejidad potencial del mantenimiento del índice; Además, un DBMS que ofrece índices de mapa de bits debería poder considerarlos de forma adecuada cuando se realiza el plan de consulta.

Answer 2

no veo un problema con una solución sencilla: Tabla para los artículos de mesa, para las etiquetas, Cuadro cruzado para "etiquetar"

índices de tabla cruzada debe ser suficiente optimización. Selección de elementos apropiados serían

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

Y marcado se

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

que es cierto, no es tan eficiente para el gran número de etiquetas que comparan. Si va a mantener el conteo de etiquetas en la memoria, puede hacer que la consulta comience con etiquetas que no son frecuentes, por lo que la secuencia AND se evaluará más rápidamente. Dependiendo de la cantidad esperada de etiquetas a comparar y la expectativa de emparejar cualquiera de ellas, esta podría ser la solución correcta, si vas a unir 20 etiquetas y esperar que algún elemento aleatorio coincida con 15 de ellas, esto aún sería pesado en una base de datos.

Answer 3

El método más fácil es crear un etiquetas tabla.
Target_Type - en caso de que están etiquetando varias tablas
Target - La clave del registro que está siendo etiquetados
Tag - El texto de una etiqueta

Consulta de los datos sería algo así como:

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

ACTUALIZACIÓN
sobre la base de sus necesidades a Y las condiciones, la consulta anterior se convertiría en algo como esto

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

No podrá evitar las uniones y aún así estará algo normalizado.

Mi enfoque es tener una tabla de etiquetas.

TagId (PK)| TagName (Indexed) 

Luego, tiene una columna TagXREFID en su tabla de artículos.

Esta columna TagXREFID es una FK a una tercera mesa, lo llamaré TagXREF:

TagXrefID | ItemID | TagId 

Por lo tanto, para obtener todas las etiquetas de un artículo sería algo así como:

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

y para conseguir todos los elementos para una etiqueta, que haría uso de algo como esto:

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

a y un montón de etiquetas en conjunto, sería para modificar la declaración anterior ligeramente para agregar AND Tags.TagName = @ TagName1 Y Tags.TagName = @ TagName2 etc ... y construir dinámicamente la consulta.

Answer 5

Es posible que desee experimentar con una solución no-estrictamente la base de datos como una aplicación Java Content Repository (por ejemplo Apache Jackrabbit) y utilizar un motor de búsqueda integrado en la parte superior de la que, al igual Apache Lucene.

Esta solución con los mecanismos de caché apropiados posiblemente rinda un mejor rendimiento que una solución interna.

Sin embargo, realmente no creo que en una aplicación pequeña o mediana requiera una implementación más sofisticada que la base de datos normalizada mencionada en publicaciones anteriores.

EDITAR: con su aclaración parece más convincente utilizar una solución similar a JCR con un motor de búsqueda. Eso simplificaría enormemente sus programas a largo plazo.

Answer 6

Lo que me gusta hacer es tener una serie de tablas que representan los datos en bruto, por lo que en este caso tendría

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

Esto funciona rápido para los tiempos de escritura, y mantiene todo normalizado, pero También debe tener en cuenta que para cada etiqueta, deberá unir las tablas dos veces por cada etiqueta adicional que desee Y, por lo que tiene una lectura lenta.

una solución para mejorar lectura es la creación de una mesa de almacenamiento en caché en el comando mediante el establecimiento de un procedimiento almacenado que esencialmente crea una nueva tabla que representa los datos en un formato aplanado ...

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

entonces se puede considerar con qué frecuencia debe mantenerse actualizada la tabla de elementos etiquetados, si está en cada inserción, luego llame al procedimiento almacenado en un evento de inserción de cursor. Si se trata de una tarea por hora, configure un trabajo por hora para ejecutarlo.

Ahora, para ser realmente inteligente en la recuperación de datos, querrá crear un procedimiento almacenado para obtener datos de las etiquetas. En lugar de utilizar consultas anidadas en una declaración de caso masivo, desea pasar un único parámetro que contiene una lista de etiquetas que desea seleccionar de la base de datos, y devolver un conjunto de elementos de registro. Esto sería mejor en formato binario, utilizando operadores bit a bit.

En formato binario, es fácil de explicar.Digamos que hay cuatro etiquetas para ser asignados a un elemento, en binario que podría representar que

0000 

Si las cuatro etiquetas se asignan a un objeto, el objeto se vería así ...

1111 

Si solo los dos primeros ...

1100 

Entonces es sólo un caso de encontrar los valores binarios con los 1s y ceros en la columna que desea. Usando los operadores Bitwise de SQL Server, puede verificar que hay un 1 en la primera de las columnas que usa consultas muy simples.

Consulte este enlace para encontrar more.

Answer 7

Parafraseando lo que otros han dicho: el truco no está en el esquema , está en la consulta.

El esquema ingenuo de Entidades/Etiquetas/Etiquetas es el camino correcto a seguir. Pero como has visto, no está claro de inmediato cómo realizar una consulta AND con muchas etiquetas.

La mejor manera de optimizar esa consulta dependerá de la plataforma, por lo que recomendaría volver a etiquetar su pregunta con su RDBS y cambiar el título a algo así como "Forma óptima de realizar Y consultar en una base de datos de etiquetado".

Tengo algunas sugerencias para MS SQL, pero me abstendré en caso de que esa no sea la plataforma que está utilizando.

Answer 8

que había @Zizzencs segunda sugerencia de que es posible que desee algo que no es totalmente (R) DB-céntrico

De alguna manera, creo que el uso de campos nvarchar lisos para almacenar las etiquetas que con un poco de almacenamiento en caché apropiada/indexación podrían producir resultados más rápidos. Pero solo soy yo.

Implementé sistemas de etiquetado usando 3 tablas para representar una relación de Muchos a Muchos antes (Etiquetas de artículos Etiquetas de elemento), pero supongo que tratará con etiquetas en muchos lugares, puedo decirlo con 3 tablas que deben ser manipuladas/consultadas simultáneamente todo el tiempo definitivamente harán que su código sea más complejo.

Es posible que desee considerar si vale la pena la complejidad añadida.

Answer 9

He aquí un buen artículo sobre el etiquetado de los esquemas de bases de datos:

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

junto con las pruebas de rendimiento:

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

Tenga en cuenta que las conclusiones no son muy específicos de MySQL, que (por lo al menos en 2005 en el momento en que se redactó) presentaba características de indexación de texto muy pobres.

Answer 10

Solo quería resaltar que el artículo al que @Jeff Atwood se vincula (http://howto.philippkeller.com/2005/04/24/Tags-Database-schemas/) es muy minucioso (discute los méritos de 3 enfoques de esquema diferentes) y tiene una buena solución para las consultas AND que generalmente funcionan mejor que lo que se ha mencionado hasta ahora (es decir, no utiliza una subconsulta correlativa para cada término). También muchas cosas buenas en los comentarios.

ps - El enfoque que todo el mundo está hablando aquí se conoce como la solución "Toxi" en el artículo.

Answer 11

Una variación de la respuesta anterior es tomar los identificadores de etiquetas, ordenarlos, combinarlos como un^string separado y hash ellos. Luego, simplemente asocie el hash al elemento. Cada combinación de etiquetas produce una nueva clave. Para hacer una búsqueda AND, simplemente vuelva a crear el hash con los identificadores de etiqueta proporcionados y la búsqueda. Al cambiar las etiquetas de un artículo, se volverá a crear el hash. Los elementos con el mismo conjunto de etiquetas comparten la misma clave hash.

Answer 12

Si tiene un tipo de matriz, puede preagrupar los datos necesarios. Ver esta respuesta en un hilo separado:

what's the utility of array type?