Diseño de bases de datos para etiquetado

¿Cómo diseñaría una base de datos para admitir las siguientes características de etiquetado:

• los elementos pueden tener una gran cantidad de etiquetas
• Las búsquedas de todos los elementos que están etiquetados con un conjunto determinado de etiquetas deben ser rápidas (los elementos deben tener TODAS las etiquetas, por lo que es una búsqueda AND, no una búsqueda OR)
• crear / escribir elementos puede ser más lento para permitir una búsqueda / lectura rápida

Idealmente, la búsqueda de todos los elementos que están etiquetados con (al menos) un conjunto de n etiquetas dadas debe hacerse usando una sola instrucción SQL. Dado que se desconoce el número de etiquetas para buscar, así como el número de etiquetas en cualquier elemento y puede ser alto, no es práctico usar JOIN.

¿Algunas ideas?

Gracias por todas las respuestas hasta el momento.

Sin embargo, si no me equivoco, las respuestas dadas muestran cómo hacer una búsqueda OR en las etiquetas. (Seleccione todos los elementos que tengan una o más de n etiquetas). Estoy buscando una eficiente búsqueda AND. (Seleccione todos los elementos que tengan TODAS las etiquetas n, y posiblemente más).

Acerca de AND: Parece que está buscando la operación de "división relacional". Este artículo cubre la división relacional de manera concisa y sin embargo comprensible.

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

Aquí hay un buen artículo sobre etiquetado de esquemas de bases de datos:

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

junto con pruebas de rendimiento:

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

Tenga en cuenta que las conclusiones allí son muy específicas para MySQL, que (al menos en 2005 en el momento en que se escribió) tenía características de indexación de texto completo muy pobres.

No veo un problema con una solución sencilla: tabla para elementos, tabla para etiquetas, tabla cruzada para "etiquetado"

Los índices en la tabla cruzada deberían ser suficiente optimización. Seleccionar elementos apropiados sería

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

Y el etiquetado sería

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

lo cual es cierto, no es tan eficiente para un gran número de etiquetas de comparación. Si desea mantener el recuento 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ía más rápidamente. Dependiendo del número esperado de etiquetas con las que se comparará y la expectativa de que coincida con cualquiera de ellas, esta podría ser una buena solución, si va a hacer coincidir 20 etiquetas y espera que algún elemento aleatorio coincida con 15 de ellas, entonces esto aún sería pesado en una base de datos

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

ps: el enfoque del que todos hablan aquí se conoce como la solución "Toxi" en el artículo.

Es posible que desee experimentar con una solución no estrictamente de base de datos, como una implementación de Java Content Repository (por ejemplo, Apache Jackrabbit ) y utilizar un motor de búsqueda creado además de eso como Apache Lucene .

Esta solución con los mecanismos de almacenamiento en caché apropiados posiblemente produciría un mejor rendimiento que una solución local.

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.

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

Consultar los datos sería algo 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
Según su requisito de 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]

En segundo lugar, sugiero a @Zizzencs que tal vez quieras algo que no esté totalmente centrado en (R) DB

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

He implementado sistemas de etiquetado usando 3 tablas para representar una relación de muchos a muchos antes (Item Tags ItemTags), pero supongo que tratarás con etiquetas en muchos lugares, puedo decirte que con 3 tablas tienes que ser manipulado / consultado simultáneamente todo el tiempo definitivamente hará que su código sea más complejo.

Es posible que desee considerar si la complejidad adicional lo vale.

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 un FK a una tercera tabla, la llamaré TagXREF:

 TagXrefID | ItemID | TagId

Entonces, obtener todas las etiquetas para un artículo sería algo como:

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

Y para obtener todos los elementos para una etiqueta, usaría 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;

Para AND un montón de etiquetas juntas, debe modificar ligeramente la declaración anterior para agregar AND Tags.TagName = @ TagName1 AND Tags.TagName = @ TagName2, etc. ... y generar dinámicamente la consulta.

Lo que me gusta hacer es tener una serie de tablas que representen los datos sin procesar, por lo que en este caso tendrías

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 puede 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 la lectura es crear una tabla de almacenamiento en caché por comando configurando un procedimiento almacenado que esencialmente crea una nueva tabla que representa los datos en un formato plano ...

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

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

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 masiva, desea pasar un único parámetro que contenga 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 asignar a un elemento, en binario podríamos 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 solo un caso de encontrar los valores binarios con los 1s y ceros en la columna que desee. Usando los operadores Bitwise de SQL Server, puede verificar que haya un 1 en la primera de las columnas usando consultas muy simples.

Consulte este enlace para obtener más información .

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

El ingenuo esquema de Entidades / Etiquetas / Etiquetas es el camino correcto. Pero como ha 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 no sea la plataforma que está utilizando.

Una variación de la respuesta anterior es tomar los identificadores de etiqueta, ordenarlos, combinarlos como una cadena ^ separada y hacerlos hash. Luego, simplemente asocia 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 dados y busque. Cambiar las etiquetas de un elemento hará que se vuelva a crear el hash. Los elementos con el mismo conjunto de etiquetas comparten la misma clave hash.

Si tiene un tipo de matriz, puede agregar previamente los datos necesarios. Vea esta respuesta en un hilo separado:

¿Cuál es la utilidad del tipo de matriz?