Datenbankdesign für Tagging

https://stackoverflow.com/questions/48475

09-06-2019
|

Frage

Wie würden Sie eine Datenbank entwerfen, um die folgenden Tagging-Funktionen zu unterstützen:

Elemente können eine große Anzahl von Tags haben
Die Suche nach allen Elementen, die mit einem bestimmten Satz von Tags versehen sind, muss schnell erfolgen (die Elemente müssen ALLE Tags haben, es handelt sich also um eine UND-Suche und nicht um eine ODER-Suche).
Das Erstellen/Schreiben von Elementen kann langsamer sein, um ein schnelles Suchen/Lesen zu ermöglichen

Idealerweise sollte die Suche nach allen Elementen, die mit (mindestens) einem Satz von n angegebenen Tags gekennzeichnet sind, mit einer einzigen SQL-Anweisung erfolgen.Da die Anzahl der zu suchenden Tags sowie die Anzahl der Tags für jedes Element unbekannt sind und möglicherweise hoch sind, ist die Verwendung von JOINs unpraktisch.

Irgendwelche Ideen?

Vielen Dank für alle bisherigen Antworten.

Wenn ich mich jedoch nicht irre, zeigen die gegebenen Antworten, wie man eine ODER-Suche nach Tags durchführt.(Wählen Sie alle Elemente aus, die eines oder mehrere von n Tags haben.)Ich suche eine effiziente UND-Suche.(Wählen Sie alle Elemente aus, die ALLE n Tags haben – und möglicherweise mehr.)

Lösung

Über ANDing:Es hört sich so an, als ob Sie nach der Operation „relationale Division“ suchen. Dieser Artikel behandelt die relationale Aufteilung prägnant und dennoch verständlich.

Über Leistung:Ein bitmapbasierter Ansatz scheint intuitiv gut zur Situation zu passen.Allerdings bin ich nicht davon überzeugt, dass es eine gute Idee ist, die Bitmap-Indizierung „manuell“ zu implementieren, wie Digiguru vorschlägt:Es klingt nach einer komplizierten Situation, wenn neue Tags hinzugefügt werden (?). Aber einige DBMS (einschließlich Oracle) bieten Bitmap-Indizes an, die irgendwie nützlich sein können, da ein integriertes Indexierungssystem die potenzielle Komplexität der Indexpflege beseitigt;Darüber hinaus sollte ein DBMS, das Bitmap-Indizes anbietet, in der Lage sein, diese bei der Ausführung des Abfrageplans ordnungsgemäß zu berücksichtigen.

Andere Tipps

Hier ist ein guter Artikel zum Markieren von Datenbankschemata:

http://howto.philippkeller.com/2005/04/24/Tags-Database-schemas/

zusammen mit Leistungstests:

http://howto.philippkeller.com/2005/06/19/Tagsystems-performance-tests/

Beachten Sie, dass die Schlussfolgerungen dort sehr spezifisch für MySQL sind, das (zumindest im Jahr 2005, als dieser Artikel geschrieben wurde) sehr schlechte Volltextindizierungseigenschaften aufwies.

Ich sehe kein Problem mit einer einfachen Lösung:Tabelle für Artikel, Tabelle für Tags, Kreuztabelle für „Tagging“

Indizes in der Kreuztabelle sollten eine ausreichende Optimierung darstellen.Die Auswahl geeigneter Artikel wäre

SELECT * FROM items WHERE id IN  
    (SELECT DISTINCT item_id FROM item_tag WHERE  
    tag_id = tag1 OR tag_id = tag2 OR ...)

UND Tagging wäre

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

was zugegebenermaßen bei einer großen Anzahl von Vergleichs-Tags nicht so effizient ist.Wenn Sie die Anzahl der Tags im Speicher beibehalten möchten, können Sie die Abfrage so veranlassen, dass sie mit Tags beginnt, die nicht häufig vorkommen, sodass die UND-Sequenz schneller ausgewertet wird.Abhängig von der erwarteten Anzahl der Tags, mit denen abgeglichen werden soll, und der Erwartung, dass auch nur ein einzelnes davon übereinstimmen wird, könnte dies eine gute Lösung sein. Wenn Sie 20 Tags abgleichen möchten und davon ausgehen, dass ein zufälliges Element mit 15 davon übereinstimmt, wäre dies immer noch schwierig auf einer Datenbank.

Ich wollte nur hervorheben, dass der Artikel, auf den @Jeff Atwood verlinkt (http://howto.philippkeller.com/2005/04/24/Tags-Database-schemas/) ist sehr gründlich (es werden die Vorzüge von drei verschiedenen Schemaansätzen besprochen) und bietet eine gute Lösung für die UND-Abfragen, die normalerweise eine bessere Leistung erbringt als das, was hier bisher erwähnt wurde (d. h.es wird nicht für jeden Begriff eine korrelierte Unterabfrage verwendet).Auch viel Gutes in den Kommentaren.

ps – Der Ansatz, über den hier alle reden, wird im Artikel als „Toxi“-Lösung bezeichnet.

Möglicherweise möchten Sie mit einer Lösung experimentieren, die nicht ausschließlich auf einer Datenbank basiert, z Java Content Repository Umsetzung (z.B. Apache Jackrabbit) und verwenden Sie eine darauf basierende Suchmaschine Apache Lucene.

Diese Lösung mit den entsprechenden Caching-Mechanismen würde möglicherweise eine bessere Leistung erzielen als eine selbst entwickelte Lösung.

Allerdings glaube ich nicht wirklich, dass Sie in einer kleinen oder mittelgroßen Anwendung eine ausgefeiltere Implementierung als die in früheren Beiträgen erwähnte normalisierte Datenbank benötigen würden.

BEARBEITEN:Mit Ihrer Klarstellung erscheint es überzeugender, eine JCR-ähnliche Lösung mit einer Suchmaschine zu verwenden.Das würde Ihre Programme auf lange Sicht erheblich vereinfachen.

Die einfachste Methode besteht darin, eine zu erstellen Stichworte Tisch.
Target_Type – falls Sie mehrere Tabellen markieren
Target – Der Schlüssel zu dem Datensatz, der getaggt wird
Tag – Der Text eines Tags

Das Abfragen der Daten würde etwa so aussehen:

Select distinct target from tags   
where tag in ([your list of tags to search for here])  
and target_type = [the table you're searching]

AKTUALISIEREN
Basierend auf Ihrer Anforderung, die Bedingungen UND zu erfüllen, würde die obige Abfrage in etwa so aussehen

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]

Ich würde @Zizzencs Vorschlag unterstützen, dass Sie vielleicht etwas wollen, das nicht völlig (R)DB-zentriert ist

Irgendwie glaube ich, dass die Verwendung einfacher Nvarchar-Felder zum Speichern dieser Tags mit einer geeigneten Zwischenspeicherung/Indizierung zu schnelleren Ergebnissen führen könnte.Aber das bin nur ich.

Ich habe bereits Tagging-Systeme implementiert, die 3 Tabellen verwenden, um eine Viele-zu-Viele-Beziehung darzustellen (Artikel-Tags, ItemTags), aber ich nehme an, dass Sie an vielen Stellen mit Tags zu tun haben werden, ich kann Ihnen sagen, dass dies bei 3 Tabellen der Fall sein muss Wenn Sie ständig gleichzeitig manipuliert/abgefragt werden, wird Ihr Code definitiv komplexer.

Vielleicht möchten Sie überlegen, ob sich die zusätzliche Komplexität lohnt.

Sie werden Verknüpfungen nicht vermeiden können und trotzdem einigermaßen normalisiert sein.

Mein Ansatz besteht darin, eine Tag-Tabelle zu haben.

 TagId (PK)| TagName (Indexed)

Dann haben Sie eine TagXREFID-Spalte in Ihrer Artikeltabelle.

Diese TagXREFID-Spalte ist ein FK zu einer dritten Tabelle, ich nenne sie TagXREF:

 TagXrefID | ItemID | TagId

Um also alle Tags für einen Artikel abzurufen, würde das etwa so aussehen:

SELECT Tags.TagId,Tags.TagName 
     FROM Tags,TagXref 
     WHERE TagXref.TagId = Tags.TagId 
         AND TagXref.ItemID = @ItemID

Und um alle Elemente für ein Tag zu erhalten, würde ich so etwas verwenden:

SELECT * FROM Items, TagXref
     WHERE TagXref.TagId IN 
          ( SELECT Tags.TagId FROM Tags
                WHERE Tags.TagName = @TagName; )
     AND Items.ItemId = TagXref.ItemId;

Um eine Reihe von Tags mit UND zu verknüpfen, müssen Sie die obige Anweisung leicht ändern, um AND Tags.TagName = @TagName1 AND Tags.TagName = @TagName2 usw. hinzuzufügen und die Abfrage dynamisch zu erstellen.

Was ich gerne mache, ist, eine Reihe von Tabellen zu haben, die die Rohdaten darstellen, in diesem Fall also

Items (ID pk, Name, <properties>)
Tags (ID pk, Name)
TagItems (TagID fk, ItemID fk)

Dies funktioniert bei den Schreibzeiten schnell und sorgt dafür, dass alles normalisiert bleibt. Beachten Sie jedoch möglicherweise auch, dass Sie für jedes Tag die Tabellen zweimal für jedes weitere Tag verknüpfen müssen, das Sie mit UND verknüpfen möchten, sodass das Lesen langsam ist.

Eine Lösung zur Verbesserung des Lesevorgangs besteht darin, auf Befehl eine Caching-Tabelle zu erstellen, indem eine gespeicherte Prozedur eingerichtet wird, die im Wesentlichen eine neue Tabelle erstellt, die die Daten in einem abgeflachten Format darstellt ...

CachedTagItems(ID, Name, <properties>, tag1, tag2, ... tagN)

Dann können Sie überlegen, wie oft die Tabelle mit markierten Elementen auf dem neuesten Stand gehalten werden muss, wenn sie bei jedem Einfügen vorhanden ist, und dann die gespeicherte Prozedur in einem Cursor-Einfügeereignis aufrufen.Wenn es sich um eine stündliche Aufgabe handelt, richten Sie einen stündlichen Job ein, um sie auszuführen.

Um beim Datenabruf wirklich clever vorzugehen, sollten Sie eine gespeicherte Prozedur erstellen, um Daten aus den Tags abzurufen.Anstatt verschachtelte Abfragen in einer umfangreichen Case-Anweisung zu verwenden, möchten Sie einen einzelnen Parameter übergeben, der eine Liste von Tags enthält, die Sie aus der Datenbank auswählen möchten, und einen Datensatz mit Elementen zurückgeben.Dies geschieht am besten im Binärformat mit bitweisen Operatoren.

Im Binärformat ist es leicht zu erklären.Nehmen wir an, es gibt vier Tags, die einem Element zugewiesen werden müssen. Binär könnten wir das darstellen

Wenn einem Objekt alle vier Tags zugewiesen sind, würde das Objekt so aussehen ...

Wenn nur die ersten beiden...

Dann müssen Sie nur noch die Binärwerte mit den Einsen und Nullen in der gewünschten Spalte finden.Mithilfe der bitweisen Operatoren von SQL Server können Sie mit sehr einfachen Abfragen überprüfen, ob in der ersten Spalte eine 1 steht.

Schauen Sie sich diesen Link an, um es herauszufinden mehr.

Um zu paraphrasieren, was andere gesagt haben:Der Trick liegt nicht darin Schema, es ist in Abfrage.

Das naive Schema von Entities/Labels/Tags ist der richtige Weg.Aber wie Sie gesehen haben, ist es nicht sofort klar, wie man eine UND-Abfrage mit vielen Tags durchführt.

Der beste Weg, diese Abfrage zu optimieren, ist plattformabhängig. Ich würde daher empfehlen, Ihre Frage erneut mit Ihrem RDBS zu kennzeichnen und den Titel in etwas wie „Optimale Möglichkeit zur Durchführung einer UND-Abfrage in einer Tagging-Datenbank“ zu ändern.

Ich habe ein paar Vorschläge für MS SQL, werde aber davon Abstand nehmen, falls dies nicht die Plattform ist, die Sie verwenden.

Eine Variation der obigen Antwort besteht darin, die Tag-IDs zu nehmen, sie zu sortieren, als ^-getrennte Zeichenfolge zu kombinieren und sie zu hashen.Dann verknüpfen Sie einfach den Hash mit dem Element.Jede Kombination von Tags erzeugt einen neuen Schlüssel.Um eine UND-Suche durchzuführen, erstellen Sie einfach den Hash mit den angegebenen Tag-IDs neu und suchen Sie.Wenn Sie Tags für ein Element ändern, wird der Hash neu erstellt.Elemente mit demselben Tag-Satz verwenden denselben Hash-Schlüssel.

Wenn Sie über einen Array-Typ verfügen, können Sie die benötigten Daten vorab aggregieren.Sehen Sie sich diese Antwort in einem separaten Thread an:

Welchen Nutzen hat der Array-Typ?

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow