Cómo implementar el sistema de etiquetas

90

Me preguntaba cuál es la mejor manera de implementar un sistema de etiquetas, como el que se usa en SO. Estaba pensando en esto, pero no puedo encontrar una buena solución escalable.

Estaba pensando en tener una solución básica de 3 mesas: tener una tagsmesa, una articlesmesa y una tag_to_articlesmesa.

¿Es esta la mejor solución a este problema o existen alternativas? Usando este método, la tabla se volvería extremadamente grande con el tiempo, y supongo que para buscar esto no es demasiado eficiente. Por otro lado, no es tan importante que la consulta se ejecute rápidamente.

Saif Bechan
fuente

Respuestas:

119

Creo que encontrará interesante esta publicación de blog: Etiquetas: esquemas de base de datos

El problema: desea tener un esquema de base de datos en el que pueda etiquetar un marcador (o una publicación de blog o lo que sea) con tantas etiquetas como desee. Luego, desea ejecutar consultas para restringir los marcadores a una unión o intersección de etiquetas. También desea excluir (digamos: menos) algunas etiquetas del resultado de la búsqueda.

Solución "MySQLicious"

En esta solución, el esquema tiene solo una tabla, está desnormalizado. Este tipo se llama “solución MySQLicious” porque MySQLicious importa datos del.icio.us a una tabla con esta estructura.

ingrese la descripción de la imagen aquíingrese la descripción de la imagen aquí

Consulta de intersección (Y) para "búsqueda + servicio web + semweb":

SELECT *
FROM `delicious`
WHERE tags LIKE "%search%"
AND tags LIKE "%webservice%"
AND tags LIKE "%semweb%"

Consulta de unión (OR) para "búsqueda | servicio web | semweb":

SELECT *
FROM `delicious`
WHERE tags LIKE "%search%"
OR tags LIKE "%webservice%"
OR tags LIKE "%semweb%"

Menos consulta para "búsqueda + servicio web-semweb"

SELECT *
FROM `delicious`
WHERE tags LIKE "%search%"
AND tags LIKE "%webservice%"
AND tags NOT LIKE "%semweb%"

Solución "Scuttle"

Scuttle organiza sus datos en dos tablas. Esa tabla “scCategories” es la tabla de “etiquetas” y tiene una clave externa para la tabla de “marcadores”.

ingrese la descripción de la imagen aquí

Consulta de intersección (Y) para "marcador + servicio web + semweb":

SELECT b.*
FROM scBookmarks b, scCategories c
WHERE c.bId = b.bId
AND (c.category IN ('bookmark', 'webservice', 'semweb'))
GROUP BY b.bId
HAVING COUNT( b.bId )=3

Primero, se buscan todas las combinaciones de marcador-etiqueta, donde la etiqueta es "marcador", "servicio web" o "semweb" (c.category IN ('marcador', 'servicio web', 'semweb')), luego solo los marcadores que tienen las tres etiquetas buscadas se tienen en cuenta (HAVING COUNT (b.bId) = 3).

Unión (OR) Consulta de "marcador | servicio web | semweb": simplemente omita la cláusula HAVING y tendrá unión:

SELECT b.*
FROM scBookmarks b, scCategories c
WHERE c.bId = b.bId
AND (c.category IN ('bookmark', 'webservice', 'semweb'))
GROUP BY b.bId

Menos (exclusión) Consulta para “marcador + servicio web-semweb”, es decir: marcador Y servicio web Y NO semweb.

SELECT b. *
FROM scBookmarks b, scCategories c
WHERE b.bId = c.bId
AND (c.category IN ('bookmark', 'webservice'))
AND b.bId NOT
IN (SELECT b.bId FROM scBookmarks b, scCategories c WHERE b.bId = c.bId AND c.category = 'semweb')
GROUP BY b.bId
HAVING COUNT( b.bId ) =2

Si se omite HAVING COUNT, aparecerá la consulta de "marcador | webservice-semweb".


Solución "Toxi"

Toxi ideó una estructura de tres mesas. A través de la tabla "mapa de etiquetas", los marcadores y las etiquetas están relacionados de n-a-m. Cada etiqueta se puede utilizar junto con diferentes marcadores y viceversa. Wordpress también utiliza este esquema de base de datos. Las consultas son prácticamente las mismas que en la solución “scuttle”.

ingrese la descripción de la imagen aquí

Consulta de intersección (Y) para "marcador + servicio web + semweb"

SELECT b.*
FROM tagmap bt, bookmark b, tag t
WHERE bt.tag_id = t.tag_id
AND (t.name IN ('bookmark', 'webservice', 'semweb'))
AND b.id = bt.bookmark_id
GROUP BY b.id
HAVING COUNT( b.id )=3

Consulta de unión (OR) para "marcador | servicio web | semweb"

SELECT b.*
FROM tagmap bt, bookmark b, tag t
WHERE bt.tag_id = t.tag_id
AND (t.name IN ('bookmark', 'webservice', 'semweb'))
AND b.id = bt.bookmark_id
GROUP BY b.id

Menos (exclusión) Consulta para “marcador + servicio web-semweb”, es decir: marcador Y servicio web Y NO semweb.

SELECT b. *
FROM bookmark b, tagmap bt, tag t
WHERE b.id = bt.bookmark_id
AND bt.tag_id = t.tag_id
AND (t.name IN ('Programming', 'Algorithms'))
AND b.id NOT IN (SELECT b.id FROM bookmark b, tagmap bt, tag t WHERE b.id = bt.bookmark_id AND bt.tag_id = t.tag_id AND t.name = 'Python')
GROUP BY b.id
HAVING COUNT( b.id ) =2

Si se omite HAVING COUNT, aparecerá la consulta de "marcador | webservice-semweb".

Nick Dandoulakis
fuente
3
autor de esa publicación de blog aquí. El blog ya no está bloqueado por Chrome (estúpidas vulnerabilidades de wordpress, movido a tumblr ahora). Felicitaciones por transformarlo en rebajas
hansaplast
hola @Philipp. OK, edité mi respuesta. Por cierto, gracias por la excelente publicación sobre sistemas de etiquetas de bases de datos.
Nick Dandoulakis
1
Solo como una nota: si desea que la consulta de intersección para la solución Toxi también muestre el marcador si buscó 'marcador' Y 'servicio web', deberá cambiar "HAVING COUNT (b.id) = 3" de 3 a "sizeof (array ('marcador', 'servicio web'))". Solo un detalle menor si planea usar esto como una función de consulta de etiqueta dinámica.
Toxicate 20 de
3
¿Algún enlace para comparar el rendimiento de las diferentes soluciones mencionadas en la publicación?
kampta
@kampta, no, no tengo ningún enlace.
Nick Dandoulakis
8

No hay nada de malo en su solución de tres mesas.

Otra opción es limitar la cantidad de etiquetas que se pueden aplicar a un artículo (como 5 en SO) y agregarlas directamente a la tabla de artículos.

La normalización de la base de datos tiene sus ventajas e inconvenientes, al igual que el cableado fijo en una tabla tiene sus ventajas y sus inconvenientes.

Nada dice que no puedas hacer ambas cosas. Va en contra de los paradigmas de bases de datos relacionales repetir información, pero si el objetivo es el rendimiento, es posible que deba romper los paradigmas.

Juan
fuente
Sí, poner las etiquetas directamente en la tabla de artículos seguramente sería una opción, aunque hay algunos inconvenientes en este método. Si almacena las 5 etiquetas en un campo separado por comas como (etiqueta1,2,3,4), este sería un método fácil. La pregunta es si la búsqueda será más rápida. Por ejemplo, alguien quiere ver todo con tag1, tiene que recorrer toda la tabla de artículos. Esto sería menos que ir a través de la tabla tag_to_article. Pero, de nuevo, la tabla tags_to_article es más delgada. Otra cosa es que tienes que explotar cada vez en php, no sé si esto lleva tiempo.
Saif Bechan
Si hace ambas cosas (etiquetas con el artículo y en una tabla separada), esto le brinda rendimiento tanto para búsquedas poscentradas como para búsquedas centradas en etiquetas. La compensación es la carga de mantener la información repetida. Además, al limitar el número de etiquetas, puede colocar cada una en su propia columna. Simplemente seleccione * de los artículos Donde XXXXX y vaya; no es necesario explotar.
John
6

La implementación de tres tablas propuesta funcionará para el etiquetado.

El desbordamiento de pila usa, sin embargo, una implementación diferente. Almacenan etiquetas en la columna varchar en la tabla de publicaciones en texto sin formato y usan la indexación de texto completo para buscar publicaciones que coinciden con las etiquetas. Por ejemplo posts.tags = "algorithm system tagging best-practices". Estoy seguro de que Jeff ha mencionado esto en alguna parte, pero olvido dónde.

Juha Syrjälä
fuente
4
Esto parece muy ineficiente. ¿Qué pasa con el orden de las etiquetas? ¿O etiquetas relacionadas? (por ejemplo, "proceso" es similar a "algoritmo" o algo por el estilo)
Richard Duerr
3

La solución propuesta es la mejor, si no la única forma práctica, que se me ocurre para abordar la relación de muchos a muchos entre etiquetas y artículos. Así que mi voto es por 'sí, sigue siendo el mejor'. Aunque estaría interesado en cualquier alternativa.

David dice reinstalar a Monica
fuente
Estoy de acuerdo. Estas tablas de Tags y TagMap tienen un tamaño de registro pequeño y, cuando se indexan correctamente, no deberían disminuir el rendimiento de manera espectacular. También podría ser una buena idea limitar el número de etiquetas od por artículo.
PanJanek
2

Si su base de datos admite matrices indexables (como PostgreSQL, por ejemplo), recomendaría una solución completamente desnormalizada: almacenar etiquetas como una matriz de cadenas en la misma tabla. De lo contrario, la mejor solución es una tabla secundaria que asigne objetos a las etiquetas. Si necesita almacenar información adicional contra las etiquetas, puede usar una tabla de etiquetas separada, pero no tiene sentido introducir una segunda combinación para cada búsqueda de etiquetas.

Nick Johnson
fuente
POstgreSQL solo admite índices en matrices de enteros: postgresql.org/docs/current/static/intarray.html
Mike Chamberlain
1
Nowadys también admite texto: postgresql.org/docs/9.6/static/arrays.html
luckydonald
2

Me gustaría sugerir MySQLicious optimizado para un mejor rendimiento. Antes de eso, los inconvenientes de la solución Toxi (3 tablas) son

Si tiene millones de preguntas y tiene 5 etiquetas en cada una, habrá 5 millones de entradas en la tabla de mapa de etiquetas. Entonces, primero tenemos que filtrar 10 mil entradas de mapa de etiquetas basadas en la búsqueda de etiquetas y luego filtrar nuevamente las preguntas coincidentes de esas 10 mil. Entonces, mientras se filtra si la identificación artical es numérica simple, entonces está bien, pero si es una especie de UUID (32 varchar), entonces el filtrado necesita una comparación más grande aunque está indexado.

Mi solución:

Siempre que se cree una nueva etiqueta, tenga un contador ++ (base 10) y convierta ese contador en base64. Ahora cada nombre de etiqueta tendrá una identificación base64. y pasar esta identificación a la interfaz de usuario junto con el nombre. De esta manera, tendrá un máximo de dos ID de caracteres hasta que tengamos 4095 etiquetas creadas en nuestro sistema. Ahora concatene estas múltiples etiquetas en cada columna de etiquetas de la tabla de preguntas. Agregue delimitador también y hágalo ordenado.

Entonces la mesa se ve así

ingrese la descripción de la imagen aquí

Mientras realiza la consulta, consulte la identificación en lugar del nombre real de la etiqueta. Dado que está CLASIFICADO , la andcondición en la etiqueta será más eficiente ( LIKE '%|a|%|c|%|f|%).

Tenga en cuenta que el delimitador de un solo espacio no es suficiente y necesitamos un delimitador doble para diferenciar las etiquetas como sqly mysqlporque LIKE "%sql%"también devolverán mysqlresultados. Debiera serLIKE "%|sql|%"

Sé que la búsqueda no está indexada, pero aún así es posible que haya indexado otras columnas relacionadas con el artículo como autor / fecha y hora, de lo contrario, se realizará un escaneo completo de la tabla.

Finalmente, con esta solución, no se requiere unión interna donde se deben comparar millones de registros con 5 millones de registros en condición de unión.

Kanagavelu Sugumar
fuente
Equipo, proporcione su opinión sobre el inconveniente de esta solución en los comentarios.
Kanagavelu Sugumar
@Nick Dandoulakis Por favor, ayúdeme proporcionando sus comentarios sobre la solución anterior, ¿funcionará?
Kanagavelu Sugumar
@Juha Syrjälä ¿Está bien la solución anterior?
Kanagavelu Sugumar
0
CREATE TABLE Tags (
    tag VARHAR(...) NOT NULL,
    bid INT ... NOT NULL,
    PRIMARY KEY(tag, bid),
    INDEX(bid, tag)
)

Notas:

  • Esto es mejor que TOXI en el sentido de que no pasa por una tabla extra many: many, lo que dificulta la optimización.
  • Claro, mi enfoque puede ser un poco más voluminoso (que TOXI) debido a las etiquetas redundantes, pero ese es un pequeño porcentaje de toda la base de datos y las mejoras de rendimiento pueden ser significativas.
  • Es altamente escalable.
  • No tiene (porque no necesita) una AUTO_INCREMENTPK sustituta . Por lo tanto, es mejor que Scuttle.
  • MySQLicious chupa porque no puede usar un índice ( LIKEcon el líder de comodín; falsos accesos a subseries)
  • Para MySQL, asegúrese de usar ENGINE = InnoDB para obtener efectos de 'agrupamiento'.

Discusiones relacionadas (para MySQL):
muchas: muchas listas ordenadas de optimización de tabla de mapeo

Rick James
fuente