img attribute sql database-design tags tagging

sql - attribute - Diseño de base de datos para etiquetado



title html attribute (12)

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

  • los artículos pueden tener una gran cantidad de etiquetas
  • las búsquedas de todos los artículos etiquetados con un conjunto determinado de etiquetas deben ser rápidos (los artículos deben tener TODAS las etiquetas, por lo que se trata de una búsqueda AND, no de 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 debe hacerse con 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.

¿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 artículos que tienen una o más n etiquetas). Estoy buscando una búsqueda AND eficiente. (Seleccione todos los elementos que tengan TODAS las etiquetas ny posiblemente más).

Acerca de ANDing: Parece que está buscando la operación de "división relacional". Este artículo 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.

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 etiquetado
Tag - El texto de una etiqueta

Consultar 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]

ACTUALIZAR
En función de su requisito para 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]

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

Esta solución con los mecanismos apropiados de almacenamiento en caché posiblemente rinda 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.

Lo que me gusta hacer es tener varias 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 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 la lectura es crear una tabla de almacenamiento en caché al 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 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 que se asignan a un elemento, en binario podríamos representar eso

0000

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

1111

Si solo los primeros dos ...

1100

Entonces es solo el 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 obtener more .

Me gustaría sugerir a @Zizzencs que podría querer algo que no sea totalmente (R) centrado en la base de datos

De alguna manera, creo que el uso de campos nvarchar simples para almacenar esas etiquetas con cierto almacenamiento en caché / indexación podría 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 elementos), pero supongo que tratarás con etiquetas en muchos lugares, puedo decirte que con 3 tablas debes ser manipulado / consultado simultáneamente todo el tiempo definitivamente hará que su código sea más complejo.

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

No podrás evitar uniones y aún 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, la 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 obtener todos los artículos por 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 Y un grupo de etiquetas juntas, debería modificar ligeramente la declaración anterior para agregar AND Tags.TagName = @ TagName1 Y Tags.TagName = @ TagName2 etc ... y generar dinámicamente la consulta.

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 los artículos 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 ...

que, sin duda, no es tan eficiente para un gran número de etiquetas de comparación. 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.

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

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 esquemas diferentes) enfoques) y tiene una buena solución para las consultas AND que normalmente funcionará mejor de lo que se ha mencionado 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.

Una variación de la respuesta anterior es tomar los identificadores de etiquetas, ordenarlos, combinarlos como una cadena separada y asignarlos. 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.