Diseño de bases de datos para etiquetado

https://stackoverflow.com/questions/48475

09-06-2019
|

Pregunta

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

Los artículos pueden tener una gran cantidad de etiquetas.
las búsquedas de todos los elementos 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 Y, no una búsqueda O)
La creación/escritura de elementos puede ser más lenta 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 determinadas debería realizarse mediante una única instrucción SQL.Dado que la cantidad de etiquetas a buscar, así como la cantidad de etiquetas en cualquier elemento, se desconocen y pueden ser altas, el uso de JOIN 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 realizar una búsqueda OR en etiquetas.(Seleccione todos los elementos que tengan una o más de n etiquetas).Estoy buscando una búsqueda AND eficiente.(Seleccione todos los elementos que tengan TODAS las n etiquetas, y posiblemente más).

Solución

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

Sobre el rendimiento:Un enfoque basado en mapas de bits parece intuitivamente adecuado para 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 útiles, porque un sistema de indexación incorporado elimina la complejidad potencial del mantenimiento del índice;Además, un DBMS que ofrezca índices de mapas de bits debería poder considerarlos de forma adecuada al realizar el plan de consulta.

Otros consejos

Aquí hay un buen artículo sobre cómo etiquetar 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-rendimiento-tests/

Tenga en cuenta que las conclusiones son muy específicas de 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 ningún problema con una solución sencilla:Tabla para artículos, tabla para etiquetas, tabla cruzada para "etiquetado"

Los índices en la tabla cruzada deberían ser suficiente optimización.Seleccionar los 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, ciertamente, no es tan eficiente para una gran cantidad de etiquetas comparativas.Si desea mantener el recuento de etiquetas en la memoria, puede realizar una consulta para comenzar con etiquetas que no son frecuentes, de modo que la secuencia Y se evalúe más rápido.Dependiendo del número esperado de etiquetas con las que se comparará y de la expectativa de coincidir 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 @Jeff Atwood enlaza (http://howto.philippkeller.com/2005/04/24/Tags-Database-schemas/) es muy completo (analiza los méritos de 3 enfoques de esquema diferentes) y tiene una buena solución para las consultas AND que normalmente funcionarán mejor que 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.

PD: el enfoque del que todo el mundo habla aquí se denomina solución "Toxi" en el artículo.

Es posible que desees experimentar con una solución que no sea estrictamente de base de datos, como Repositorio de contenidos Java implementación (por ej. Conejo Apache) y usar un motor de búsqueda creado sobre eso como apache lucene.

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

Sin embargo, realmente no creo que en una aplicación pequeña o mediana necesites 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.Esto simplificaría enormemente sus programas a largo plazo.

El método más sencillo es crear un etiquetas mesa.
Target_Type -- en caso de que estés 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]

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

Secundo la sugerencia de @Zizzencs de que quizás quieras algo que no esté totalmente centrado en (R)DB

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

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

Quizás quieras considerar si la complejidad adicional vale la pena.

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

 TagXrefID | ItemID | TagId

Entonces, obtener todas las etiquetas de 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 de 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 unir un montón de etiquetas, deberá modificar ligeramente la declaración anterior para agregar AND Tags.TagName = @TagName1 AND Tags.TagName = @TagName2, etc... y crear dinámicamente la consulta.

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 puede notar que para cada etiqueta, necesitará unir tablas dos veces para cada etiqueta adicional que desee Y, por lo que la lectura es lenta.

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

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

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

Ahora, para ser realmente inteligente en la recuperación de datos, querrás 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 registros de elementos.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 eso

Si las cuatro etiquetas están asignadas a un objeto, el objeto se vería así...

Si solo los dos primeros...

Entonces es sólo cuestión de encontrar los valores binarios con los unos y los ceros en la columna que desea.Utilizando los operadores Bitwise de SQL Server, puedes comprobar que hay un 1 en la primera de las columnas mediante consultas muy sencillas.

Consulta este enlace para descubrirlo. más.

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

El esquema ingenuo de Entidades/Etiquetas/Etiquetas es el camino correcto a seguir.Pero como ha visto, no queda 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 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ás usando.

Una variación de la respuesta anterior es tomar los identificadores de etiquetas, ordenarlos, combinarlos como una cadena separada ^ y aplicar hash.Luego simplemente asocie el hash al elemento.Cada combinación de etiquetas produce una nueva clave.Para realizar una búsqueda AND, simplemente vuelva a crear el hash con los identificadores de etiqueta proporcionados 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?

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow