Conception de base de données pour le marquage

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
• recherche tous les éléments marqués avec un ensemble de balises donné doit être rapide (les éléments doivent avoir TOUTES les balises, il s'agit donc d'une recherche AND, pas d'une recherche OR)
• la création / écriture d'éléments peut être plus lente pour permettre une recherche / lecture rapide

Idéalement, la recherche de tous les éléments qui sont balisé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 JOINs n'est pas pratique.

Des idées?

Merci pour toutes les réponses à ce jour.

Si je ne me trompe pas, cependant, les réponses données montrent comment effectuer une recherche OR 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 balises n - et éventuellement plus.)

À propos de ANDing: Il semble que vous recherchiez l'opération "division relationnelle". Cet article couvre la division relationnelle de manière concise et compréhensible.

À propos des performances: une approche basée sur des images 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 ressemble à une situation compliquée chaque fois que de nouvelles balises sont ajoutées (?) Mais certains SGBD (y compris Oracle) offrent des index bitmap qui peuvent en quelque sorte être utile, 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 doit être en mesure de les considérer comme il se doit lors de l'exécution du plan de requête.

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 performance:

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) 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, croisé pour le "balisage"

Les indices sur table croisée devraient être 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 aussi 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 commencer avec des balises qui ne le sont pas souvent, de sorte que la séquence AND sera évaluée plus rapidement. En fonction du nombre attendu de balises à comparer et de l'espérance de correspondre à l'une d'entre elles, cela pourrait être une solution acceptable, si vous devez faire correspondre 20 balises et vous attendre à ce qu'un élément aléatoire corresponde à 15 d'entre elles, alors ce 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 schémas différents approches) et a une bonne solution pour les requêtes AND qui fonctionnent généralement mieux que ce qui a été mentionné ici jusqu'à présent (c'est-à-dire qu'il n'utilise pas de sous-requête corrélée pour chaque terme). Aussi beaucoup de bonnes choses dans les commentaires.

ps - L'approche dont tout le monde parle ici est appelée solution "Toxi" dans l'article.

Vous voudrez peut-être expérimenter une solution non strictement basée sur une base de données comme une implémentation de référentiel de contenu Java (par exemple Apache Jackrabbit ) et utiliser un moteur de recherche construit en plus de cela comme Apache Lucene .

Cette solution avec les mécanismes de mise en cache appropriés donnerait peut-être de meilleures performances qu'une solution maison.

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.

EDIT: 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 une table de balises .
Target_Type- dans le cas où vous étiquetez plusieurs tables
Target- La clé de l'enregistrement à
Tagétiqueter - Le texte d'une étiquette

Interroger les données serait 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 transforme en quelque chose comme ça

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]

Je seconderais la suggestion de @Zizzencs selon laquelle vous voudrez peut-être quelque chose qui n'est pas totalement (R) DB-centric

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 ce n'est que moi.

J'ai implémenté des systèmes de balisage utilisant 3 tables pour représenter une relation plusieurs-à-plusieurs avant (Item Tags ItemTags), mais je suppose que vous aurez affaire à des balises dans de nombreux endroits, je peux vous dire qu'avec 3 tables devant être manipulé / interrogé 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 restant quelque peu normalisé.

Mon approche est d'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

Donc, pour obtenir toutes les balises pour 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 étiquette, 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 créer 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 garde tout normalisé, mais vous pouvez également noter que pour chaque balise, vous devrez joindre deux fois les tables pour chaque autre balise que vous souhaitez ET, donc la lecture est lente.

Une solution pour améliorer la lecture consiste à créer une table de mise en cache sur commande en mettant en place 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 à quelle fréquence la table des éléments marqués doit être tenue à jour, si elle se trouve à chaque insertion, puis appeler 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 voudrez 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 de cas massive, vous souhaitez transmettre un paramètre unique 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 à assigner à un élément, en binaire, nous pourrions représenter que

0000

Si les quatre balises sont attribuées à un objet, l'objet ressemblerait à ceci ...

1111

Si seulement les deux premiers ...

1100

Ensuite, il s'agit simplement 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 existe un 1 dans la première des colonnes à l'aide de requêtes très simples.

Consultez ce lien pour en savoir plus .

Pour paraphraser ce que les autres ont dit: l'astuce n'est pas dans le schéma , c'est dans la requête .

Le schéma naïf des entités / étiquettes / balises 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 beaucoup de balises.

La meilleure façon d'optimiser cette requête dépendra de la plate-forme, je vous recommande donc de re-tagger votre question avec votre RDBS et de changer le titre en quelque chose comme "Façon 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 est de prendre les identifiants de balise, de les trier, de les combiner sous forme de chaîne séparée par ^ et de les hacher. Ensuite, associez simplement le hachage à l'élément. Chaque combinaison de balises produit une nouvelle clé. Pour effectuer une recherche AND, recréez simplement le hachage avec les identifiants de balise et recherchez. 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 avez un type de tableau, vous pouvez pré-agréger les données nécessaires. Voir cette réponse dans un fil séparé:

quelle est l'utilité du type de tableau?