Conception de base de données pour le balisage
https://stackoverflow.com/questions/48475
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Comment concevriez-vous une base de données pour prendre en charge les fonctionnalités de balisage suivantes :
- les éléments peuvent avoir un grand nombre de balises
- les recherches de tous les éléments marqués avec un ensemble de balises donné doivent être rapides (les éléments doivent avoir TOUTES les balises, il s'agit donc d'une recherche ET, pas d'une recherche OU)
- la création/l'écriture d'éléments peut être plus lente pour permettre une recherche/lecture rapide
Idéalement, la recherche de tous les éléments marqués avec (au moins) un ensemble de n balises données devrait être effectuée à l’aide d’une seule instruction SQL.Étant donné que le nombre de balises à rechercher ainsi que le nombre de balises sur un élément sont inconnus et peuvent être élevés, l'utilisation de JOIN n'est pas pratique.
Des idées?
Merci pour toutes les réponses jusqu'à présent.
Si je ne me trompe pas, cependant, les réponses données montrent comment effectuer une recherche OU sur les balises.(Sélectionnez tous les éléments qui ont une ou plusieurs balises parmi n).Je recherche une recherche ET efficace.(Sélectionnez tous les éléments qui ont TOUTES les n balises - et éventuellement plus.)
La solution
À propos de AND :On dirait que vous recherchez l'opération "division relationnelle". Cet article couvre la division relationnelle de manière concise mais compréhensible.
À propos des performances :Une approche basée sur bitmap semble intuitivement convenir à la situation.Cependant, je ne suis pas convaincu que ce soit une bonne idée d'implémenter l'indexation bitmap "manuellement", comme le suggère Digiguru :Cela semble être une situation compliquée chaque fois que de nouvelles balises sont ajoutées (?). Mais certains SGBD (y compris Oracle) proposent des index bitmap qui peuvent être utiles d'une manière ou d'une autre, car un système d'indexation intégré supprime la complexité potentielle de la maintenance des index ;De plus, un SGBD proposant des index bitmap devrait être capable de les prendre en compte correctement lors de l'exécution du plan de requête.
Autres conseils
Voici un bon article sur le balisage des schémas de base de données :
http://howto.philippkeller.com/2005/04/24/Tags-Database-schemas/
ainsi que des tests de performances :
http://howto.philippkeller.com/2005/06/19/Tagsystems-performance-tests/
Notez que les conclusions sont très spécifiques à MySQL, qui (au moins en 2005 au moment de la rédaction de cet article) avait de très mauvaises caractéristiques d'indexation de texte intégral.
Je ne vois pas de problème avec une solution simple :Tableau pour les éléments, tableau pour les balises, tableau croisé pour le "tagging"
Les indices sur le tableau croisé devraient constituer une optimisation suffisante.La sélection des éléments appropriés serait
SELECT * FROM items WHERE id IN
(SELECT DISTINCT item_id FROM item_tag WHERE
tag_id = tag1 OR tag_id = tag2 OR ...)
ET le marquage serait
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 ...
ce qui n'est certes pas si efficace pour un grand nombre de balises de comparaison.Si vous souhaitez conserver le nombre de balises en mémoire, vous pouvez effectuer une requête pour démarrer avec des balises qui ne sont pas fréquentes, afin que la séquence AND soit évaluée plus rapidement.En fonction du nombre attendu de balises à comparer et de l'attente de faire correspondre l'une d'entre elles, cela pourrait être une solution correcte, si vous devez faire correspondre 20 balises et vous attendre à ce qu'un élément aléatoire corresponde à 15 d'entre elles, alors cela serait toujours lourd sur une base de données.
Je voulais juste souligner que l'article auquel @Jeff Atwood renvoie (http://howto.philippkeller.com/2005/04/24/Tags-Database-schemas/) est très complet (il discute des mérites de 3 approches de schéma différentes) et propose une bonne solution pour les requêtes AND qui fonctionneront généralement mieux que ce qui a été mentionné ici jusqu'à présent (c'est-à-direil n'utilise pas de sous-requête corrélée pour chaque terme).Et plein de bonnes choses aussi dans les commentaires.
ps - L'approche dont tout le monde parle ici est appelée solution "Toxi" dans l'article.
Vous souhaiterez peut-être expérimenter une solution non strictement basée sur une base de données, telle qu'un Référentiel de contenu Java mise en œuvre (par ex. Apache Jackrabbit) et utilisez un moteur de recherche construit en plus comme Apache Lucène.
Cette solution, dotée des mécanismes de mise en cache appropriés, pourrait éventuellement produire de meilleures performances qu'une solution développée en interne.
Cependant, je ne pense pas vraiment que dans une application de petite ou moyenne taille, vous auriez besoin d'une implémentation plus sophistiquée que la base de données normalisée mentionnée dans les articles précédents.
MODIFIER:avec votre clarification, il semble plus convaincant d'utiliser une solution de type JCR avec un moteur de recherche.Cela simplifierait grandement vos programmes à long terme.
La méthode la plus simple consiste à créer un Mots clés tableau.
Target_Type -- au cas où vous marqueriez plusieurs tables
Target -- La clé de l'enregistrement étiqueté
Tag -- Le texte d'une balise
L'interrogation des données ressemblerait à quelque chose comme :
Select distinct target from tags
where tag in ([your list of tags to search for here])
and target_type = [the table you're searching]
MISE À JOUR
En fonction de vos exigences ET des conditions, la requête ci-dessus se transformerait en quelque chose comme ceci
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]
J'appuie la suggestion de @Zizzencs selon laquelle vous pourriez vouloir quelque chose qui n'est pas totalement centré sur (R)DB
D'une manière ou d'une autre, je pense que l'utilisation de champs nvarchar simples pour stocker ces balises avec une mise en cache/indexation appropriée pourrait donner des résultats plus rapides.Mais c'est juste moi.
J'ai déjà implémenté des systèmes de marquage utilisant 3 tables pour représenter une relation plusieurs-à-plusieurs (Item Tags ItemTags), mais je suppose que vous aurez affaire à des balises dans de nombreux endroits, je peux vous dire qu'avec 3 tables, vous devrez être manipulé/interrogeé simultanément tout le temps rendra certainement votre code plus complexe.
Vous voudrez peut-être vous demander si la complexité supplémentaire en vaut la peine.
Vous ne pourrez pas éviter les jointures tout en étant quelque peu normalisé.
Mon approche consiste à avoir une table de balises.
TagId (PK)| TagName (Indexed)
Ensuite, vous avez une colonne TagXREFID dans votre table d'éléments.
Cette colonne TagXREFID est un FK vers une 3ème table, je l'appellerai TagXREF :
TagXrefID | ItemID | TagId
Ainsi, pour obtenir toutes les balises d’un élément, ce serait quelque chose comme :
SELECT Tags.TagId,Tags.TagName
FROM Tags,TagXref
WHERE TagXref.TagId = Tags.TagId
AND TagXref.ItemID = @ItemID
Et pour obtenir tous les éléments d'une balise, j'utiliserais quelque chose comme ceci :
SELECT * FROM Items, TagXref
WHERE TagXref.TagId IN
( SELECT Tags.TagId FROM Tags
WHERE Tags.TagName = @TagName; )
AND Items.ItemId = TagXref.ItemId;
Pour ET un tas de balises ensemble, vous devez modifier légèrement l'instruction ci-dessus pour ajouter AND Tags.TagName = @TagName1 AND Tags.TagName = @TagName2 etc... et construire dynamiquement la requête.
Ce que j'aime faire, c'est avoir un certain nombre de tableaux qui représentent les données brutes, donc dans ce cas, vous auriez
Items (ID pk, Name, <properties>)
Tags (ID pk, Name)
TagItems (TagID fk, ItemID fk)
Cela fonctionne rapidement pour les temps d'écriture et maintient tout normalisé, mais vous pouvez également noter que pour chaque balise, vous devrez joindre les tables deux fois pour chaque autre balise que vous souhaitez ET, la lecture est donc lente.
Une solution pour améliorer la lecture consiste à créer une table de mise en cache sur commande en configurant une procédure stockée qui crée essentiellement une nouvelle table qui représente les données dans un format aplati...
CachedTagItems(ID, Name, <properties>, tag1, tag2, ... tagN)
Ensuite, vous pouvez déterminer la fréquence à laquelle la table des éléments marqués doit être maintenue à jour. Si elle se trouve à chaque insertion, appelez ensuite la procédure stockée dans un événement d'insertion de curseur.S'il s'agit d'une tâche horaire, configurez une tâche horaire pour l'exécuter.
Maintenant, pour devenir vraiment intelligent dans la récupération de données, vous devez créer une procédure stockée pour obtenir les données des balises.Plutôt que d'utiliser des requêtes imbriquées dans une instruction case massive, vous souhaitez transmettre un seul paramètre contenant une liste de balises que vous souhaitez sélectionner dans la base de données et renvoyer un ensemble d'enregistrements d'éléments.Ce serait mieux au format binaire, en utilisant des opérateurs au niveau du bit.
Au format binaire, c'est facile à expliquer.Disons qu'il y a quatre balises à attribuer à un élément, en binaire nous pourrions représenter cela
0000
Si les quatre balises sont affectées à un objet, l'objet ressemblerait à ceci...
1111
Si seulement les deux premiers...
1100
Ensuite, il suffit de trouver les valeurs binaires avec les 1 et les zéros dans la colonne souhaitée.À l'aide des opérateurs Bitwise de SQL Server, vous pouvez vérifier qu'il y a un 1 dans la première des colonnes à l'aide de requêtes très simples.
Consultez ce lien pour le savoir plus.
Pour paraphraser ce que d'autres ont dit :l'astuce n'est pas dans le schéma, c'est dans le requête.
Le schéma naïf Entités/Étiquettes/Tags est la bonne voie à suivre.Mais comme vous l'avez vu, il n'est pas immédiatement clair comment effectuer une requête AND avec un grand nombre de balises.
La meilleure façon d'optimiser cette requête dépendra de la plate-forme, je vous recommande donc de re-étiqueter votre question avec votre RDBS et de changer le titre en quelque chose comme « Manière optimale d'effectuer une requête ET sur une base de données de marquage ».
J'ai quelques suggestions pour MS SQL, mais je m'abstiendrai au cas où ce ne serait pas la plate-forme que vous utilisez.
Une variante de la réponse ci-dessus consiste à prendre les identifiants de balise, à les trier, à les combiner sous forme de chaîne séparée par ^ et à les hacher.Ensuite, associez simplement le hachage à l'élément.Chaque combinaison de balises produit une nouvelle clé.Pour effectuer une recherche ET, recréez simplement le hachage avec les identifiants de balise donnés et effectuez une recherche.La modification des balises sur un élément entraînera la recréation du hachage.Les éléments avec le même ensemble de balises partagent la même clé de hachage.
Si vous disposez d'un type de tableau, vous pouvez pré-agréger les données nécessaires.Voir cette réponse dans un fil séparé :
