Diseño de bases de datos para etiquetado

171

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

Christian Berg
fuente

Respuestas:

22

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.

Troels Arvin
fuente
44
Tengo que decir que la respuesta es un poco miope, porque usar un tipo de campo de bits de la base de datos lo limita a un número específico de bits. Esto no significa que cada elemento esté limitado a un cierto número de etiquetas, sino que solo puede haber un cierto número de etiquetas únicas en todo el sistema (generalmente hasta 32 o 64).
Mark Renouf
1
Suponiendo una implementación 3nf (Question, Tag, Question_has_Tag) y un índice de mapa de bits en Tag_id en Question_has_Tag, el índice de mapa de bits debe reconstruirse cada vez que una pregunta tiene una etiqueta agregada o eliminada. Una consulta como select * from question q inner join question_has_tag qt where tag_id in (select tag_id from tags where (what we want) minus select tag_id from tags where (what we don't)debería estar bien y escalar asumiendo que existen los índices b-tree correctos en la tabla central
Adam Musch
El enlace "Este artículo" está muerto. Me hubiera gustado leer eso :(
mpen
3
Marca: Esta se ve bien: simple-talk.com/sql/t-sql-programming/… Probablemente sea una versión reeditada de la que mencioné .
Troels Arvin
la URL del artículo ya no es válida
Sebastien H.
77

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.

Jeff Atwood
fuente
1
También me gustaría tener una visión técnica más detallada sobre cómo implementó el sistema de etiquetado con SO. ¿Creo que en un podcast dijiste que mantienes todas las etiquetas en una columna con cada pregunta y luego las serializas / des-serializas sobre la marcha? Me encantaría saber más al respecto y tal vez ver algunos fragmentos de código. He estado buscando y he encontrado algún detalle, ¿hay algún enlace en el que ya hayas hecho esto antes de hacer la pregunta sobre META?
Marston A.
55
Esta pregunta sobre Meta tiene información sobre el esquema SO: meta.stackexchange.com/questions/1863/so-database-schema
Barrett
Los enlaces originales estaban muertos, pero creo que encontré su nueva ubicación. Es posible que desee verificar que estos eran los artículos a los que se refería.
Brad Larson
12
A pesar de haber sido escrito por @Jeff, esto sigue siendo esencialmente una respuesta de solo enlace.
curiousdannii
13

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

Slartibartfast
fuente
13

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.

Winston Fassett
fuente
3
Recuerdo haber leído ese gran artículo, pero desafortunadamente el enlace está muerto ahora. :( ¿Alguien sabe de un espejo?
localhost
55
el enlace estaba muerto: <
Aaron
6

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.

Zizzencs
fuente
5

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]
Brad Bruce
fuente
1

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.

chakrit
fuente
0

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.

FlySwat
fuente
0

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 .

digiguru
fuente
0

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.

Portman
fuente
66
Probablemente no debas abstenerte de dar información sobre cierta tecnología porque otras personas que intentan trabajar en este dominio problemático pueden estar usando esa tecnología y se beneficiarían.
Bryan Rehbein el
0

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.

nitinahuja
fuente
44
Con este enfoque, solo puede buscar entradas con exactamente el mismo conjunto de etiquetas, eso siempre es trivial. En mi pregunta original, quiero encontrar entradas que tengan todas las etiquetas que solicito y posiblemente más.
Christian Berg