Cómo implementar el sistema de etiquetas

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.

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.

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

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

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

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.

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.

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.

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.

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í

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.

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