Comment mettre en œuvre un système d'étiquettes

Je me demandais quelle était la meilleure façon d'implémenter un système de balises, comme celui utilisé sur SO. J'y pensais mais je n'arrive pas à trouver une bonne solution évolutive.

Je pensais avoir une solution de base à 3 tables: avoir une tagstable, une articlestable et une tag_to_articlestable.

Est-ce la meilleure solution à ce problème ou existe-t-il des alternatives? En utilisant cette méthode, la table deviendrait extrêmement volumineuse dans le temps, et je suppose que la recherche n'est pas trop efficace. D'un autre côté, il n'est pas si important que la requête s'exécute rapidement.

Je crois que vous trouverez intéressant ce billet de blog: Tags: Schémas de base de données

Le problème: vous voulez avoir un schéma de base de données dans lequel vous pouvez baliser un signet (ou un article de blog ou autre) avec autant de balises que vous le souhaitez. Plus tard, vous souhaitez exécuter des requêtes pour contraindre les signets à une union ou une intersection de balises. Vous souhaitez également exclure (par exemple: moins) certaines balises du résultat de la recherche.

Solution «MySQLicious»

Dans cette solution, le schéma n'a qu'une seule table, il est dénormalisé. Ce type est appelé «solution MySQLicious» car MySQLicious importe les données del.icio.us dans une table avec cette structure.

Requête d'intersection (AND) pour "recherche + webservice + semweb":

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

Requête Union (OR) pour "recherche | webservice | semweb":

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

Requête moins pour "recherche + webservice-semweb"

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

Solution «Scuttle»

Scuttle organise ses données en deux tableaux. Cette table «scCategories» est la table «tag» et a une clé étrangère vers la table «signet».

Requête d'intersection (AND) pour "bookmark + webservice + 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

Tout d'abord, toutes les combinaisons de signets-balises sont recherchées, où la balise est "signet", "webservice" ou "semweb" (c.category IN ("bookmark", "webservice", "semweb")), puis uniquement les ont obtenu les trois balises recherchées sont prises en compte (HAVING COUNT (b.bId) = 3).

Requête Union (OR) pour "bookmark | webservice | semweb": omettez simplement la clause HAVING et vous avez union:

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

Moins (exclusion) Requête pour «signet + webservice-semweb», c'est-à-dire: signet ET webservice ET NON 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

Le fait d'omettre HAVING COUNT conduit à la requête "bookmark | webservice-semweb".

Solution «Toxi»

Toxi a proposé une structure à trois tables. Via le tableau «tagmap», les signets et les balises sont liés de n à m. Chaque balise peut être utilisée avec différents signets et vice versa. Ce schéma DB est également utilisé par wordpress. Les requêtes sont sensiblement les mêmes que dans la solution «scuttle».

Requête d'intersection (AND) pour "bookmark + webservice + 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

Requête Union (OR) pour "bookmark | webservice | 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

Moins (exclusion) Requête pour «signet + webservice-semweb», c'est-à-dire: signet ET webservice ET NON 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

Le fait d'omettre HAVING COUNT conduit à la requête "bookmark | webservice-semweb".

Rien de mal avec votre solution à trois tables.

Une autre option consiste à limiter le nombre de balises pouvant être appliquées à un article (comme 5 dans SO) et à les ajouter directement à votre tableau d'articles.

La normalisation de la base de données a ses avantages et ses inconvénients, tout comme le câblage des éléments dans une seule table présente des avantages et des inconvénients.

Rien ne dit que vous ne pouvez pas faire les deux. Répéter des informations va à l'encontre des paradigmes de base de données relationnelle, mais si l'objectif est la performance, vous devrez peut-être briser les paradigmes.

L'implémentation de trois tables que vous proposez fonctionnera pour le balisage.

Le débordement de pile utilise cependant une implémentation différente. Ils stockent les balises dans la colonne varchar dans la table des articles en texte brut et utilisent l'indexation de texte intégral pour récupérer les articles qui correspondent aux balises. Par exemple posts.tags = "algorithm system tagging best-practices". Je suis sûr que Jeff a mentionné cela quelque part mais j'oublie où.

La solution proposée est la meilleure - sinon la seule possible - à laquelle je puisse penser pour aborder la relation plusieurs à plusieurs entre les balises et les articles. Donc mon vote est pour "oui, c'est toujours le meilleur". Je serais cependant intéressé par toutes les alternatives.

Si votre base de données prend en charge les tableaux indexables (comme PostgreSQL, par exemple), je recommanderais une solution entièrement dénormalisée - stocker les balises sous forme de tableau de chaînes sur la même table. Sinon, une table secondaire qui mappe les objets aux balises est la meilleure solution. Si vous avez besoin de stocker des informations supplémentaires sur les balises, vous pouvez utiliser une table de balises distincte, mais il ne sert à rien d'introduire une deuxième jointure pour chaque recherche de balises.

Je voudrais suggérer MySQLicious optimisé pour de meilleures performances. Avant cela, les inconvénients de la solution Toxi (3 tableau) sont

Si vous avez des millions de questions et qu'il contient 5 balises chacune, alors il y aura 5 millions d'entrées dans le tableau tagmap. Nous devons donc d'abord filtrer 10 000 entrées de tagmap en fonction de la recherche par tag, puis à nouveau filtrer les questions correspondantes de ces 10 000. Donc, tout en filtrant si l'ID artistique est numérique simple, alors c'est ok, mais s'il s'agit d'une sorte d'UUID (32 varchar), alors le filtrage nécessite une comparaison plus large bien qu'il soit indexé.

Ma solution:

Chaque fois qu'une nouvelle balise est créée, utilisez counter ++ (base 10) et convertissez ce compteur en base64. Désormais, chaque nom de balise aura un identifiant base64. et transmettez cet identifiant à l'interface utilisateur avec le nom. De cette façon, vous aurez au maximum deux identifiants de caractères jusqu'à ce que nous ayons 4095 balises créées dans notre système. Maintenant, concaténez ces multiples balises dans chaque colonne de balises de table de questions. Ajoutez également un délimiteur et triez-le.

Donc la table ressemble à ceci

Lors de l'interrogation, interrogez sur l'id au lieu du vrai nom de la balise Puisqu'il est TRIÉ , la andcondition sur la balise sera plus efficace ( LIKE '%|a|%|c|%|f|%).

Notez qu'un seul séparateur d'espace n'est pas suffisant et que nous avons besoin d'un double délimiteur pour différencier les balises comme sqlet mysqlcar LIKE "%sql%"renverra également des mysqlrésultats. Devrait êtreLIKE "%|sql|%"

Je sais que la recherche n'est pas indexée, mais vous avez peut-être encore indexé d'autres colonnes liées à un article comme auteur / dateTime, sinon, une analyse complète de la table sera effectuée.

Enfin, avec cette solution, aucune jointure interne n'est requise où des millions d'enregistrements doivent être comparés à 5 millions d'enregistrements à condition de jointure.

CREATE TABLE Tags (
    tag VARHAR(...) NOT NULL,
    bid INT ... NOT NULL,
    PRIMARY KEY(tag, bid),
    INDEX(bid, tag)
)

Remarques:

• C'est mieux que TOXI dans la mesure où il ne passe pas par un très grand nombre: plusieurs tables ce qui rend l'optimisation difficile.
• Bien sûr, mon approche peut être légèrement plus volumineuse (que TOXI) en raison des balises redondantes, mais c'est un petit pourcentage de l' ensemble de la base de données, et les améliorations de performances peuvent être significatives.
• Il est hautement évolutif.
• Il n'a pas (car il n'en a pas besoin) de AUTO_INCREMENTPK de substitution . Par conséquent, c'est mieux que Scuttle.
• MySQLicious est nul car il ne peut pas utiliser d'index ( LIKEavec un caractère générique en tête ; faux hits sur les sous-chaînes)
• Pour MySQL, veillez à utiliser ENGINE = InnoDB afin d'obtenir des effets de «clustering».

Discussions connexes (pour MySQL):
beaucoup: beaucoup de listes ordonnées d' optimisation de table de mappage