Progettazione del database per il tagging

Come progetteresti un database per supportare le seguenti funzionalità di tagging:

  • gli articoli possono avere un numero elevato di tag
  • la ricerca di tutti gli elementi taggati con un determinato set di tag deve essere veloce (gli elementi devono avere TUTTI i tag, quindi è una ricerca AND, non una ricerca OR)
  • la creazione / scrittura di elementi potrebbe essere più lenta per consentire una rapida ricerca / lettura

Idealmente, la ricerca di tutti gli articoli che sono contrassegnati con (almeno) un insieme di n tag dati dovrebbe essere fatta usando una singola istruzione SQL. Poiché il numero di tag da cercare e il numero di tag su qualsiasi elemento sono sconosciuti e potrebbero essere elevati, l’utilizzo di JOIN non è pratico.

Qualche idea?


Grazie per tutte le risposte finora.

Tuttavia, se non sbaglio, le risposte fornite mostrano come eseguire una ricerca OR sui tag. (Seleziona tutti gli articoli che hanno uno o più tag n). Sto cercando una ricerca AND efficiente. (Seleziona tutti gli elementi che hanno TUTTI i tag n – e possibilmente di più).

Informazioni su ANDing: Sembra che tu stia cercando l’operazione “divisione relazionale”. Questo articolo copre la divisione relazionale in modo conciso e tuttavia comprensibile.

Informazioni sulle prestazioni: un approccio basato su bitmap sembra intuitivamente adatto alla situazione. Tuttavia, non sono convinto che sia una buona idea implementare l’indicizzazione bitmap “manualmente”, come suggerisce Digiguru: Sembra una situazione complicata ogni volta che vengono aggiunti nuovi tag (?) Ma alcuni DBMS (incluso Oracle) offrono indici bitmap che potrebbero in qualche modo essere utile, perché un sistema di indicizzazione integrato elimina la potenziale complessità della manutenzione dell’indice; Inoltre, un DBMS che offre indici bitmap dovrebbe essere in grado di considerarli appropriati quando si esegue il piano di query.

Ecco un buon articolo sul tagging degli schemi di database:

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

insieme ai test delle prestazioni:

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

Si noti che le conclusioni sono molto specifiche per MySQL, che (almeno nel 2005, al momento in cui è stato scritto) aveva caratteristiche di indicizzazione del testo completo molto scadenti.

Non vedo un problema con una soluzione semplice: tabella per gli articoli, tabella per i tag, crosstable per “tagging”

Gli indici sul cross table dovrebbero essere abbastanza ottimizzati. La selezione di articoli appropriati sarebbe

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

E tagging sarebbe

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

che è certamente, non così efficiente per un gran numero di tag di confronto. Se si desidera conservare il conteggio dei tag in memoria, è ansible fare in modo che la query inizi con tag che non sono spesso, quindi la sequenza AND verrà valutata più rapidamente. A seconda del numero atteso di tag da abbinare e dell’aspettativa di corrispondere a ciascuno di essi, questa potrebbe essere una soluzione OK, se si devono abbinare 20 tag e aspettarsi che alcuni elementi casuali corrispondano a 15 di essi, questo sarebbe comunque pesante su un database.

Volevo solo sottolineare che l’articolo che @Jeff Atwood collega a ( http://howto.philippkeller.com/2005/04/24/Tags-Database-schemas/ ) è molto approfondito (discute i meriti di 3 diversi schemi approcci) e ha una buona soluzione per le query AND che di solito funzionano meglio di quanto è stato menzionato finora (cioè non utilizza una subquery correlata per ogni termine). Anche un sacco di cose buone nei commenti.

ps – L’approccio di cui tutti parlano qui è indicato come la soluzione “Toxi” nell’articolo.

Potresti voler sperimentare una soluzione non strettamente di database come un’implementazione del repository di contenuti Java (ad es. Apache Jackrabbit ) e utilizzare un motore di ricerca basato su Apache Lucene .

Questa soluzione con i meccanismi di caching appropriati potrebbe fornire prestazioni migliori di una soluzione sviluppata in casa.

Tuttavia, non penso che in un’applicazione di piccole o medie dimensioni sia necessaria un’implementazione più sofisticata rispetto al database normalizzato menzionato nei post precedenti.

EDIT: con il tuo chiarimento sembra più interessante utilizzare una soluzione simile a JCR con un motore di ricerca. Ciò semplificherebbe enormemente i tuoi programmi a lungo termine.

Il metodo più semplice è creare una tabella di tag .
Target_Type – nel caso in cui stai taggando più tabelle
Target : la chiave del record che viene taggato
Tag : il testo di un tag

Interrogare i dati sarebbe qualcosa di simile:

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

AGGIORNARE
In base al tuo requisito di AND le condizioni, la query di cui sopra si trasformsrà in qualcosa di simile

 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] 

Vorrei secondo suggerimento di Zizzencs che potresti volere qualcosa che non sia totalmente (R) DB-centrico

In qualche modo, credo che l’utilizzo di semplici campi nvarchar per archiviare tali tag con un corretto caching / indicizzazione potrebbe produrre risultati più rapidi. Ma sono solo io.

Ho implementato i sistemi di tagging utilizzando 3 tabelle per rappresentare una relazione molti-a-molti prima (tag tag articoli), ma suppongo che si tratterà di tag in molti punti, posso dirti che con 3 tabelle che devono essere manipolati / interrogati simultaneamente tutto il tempo renderà sicuramente il tuo codice più complesso.

Potresti considerare se la complessità aggiunta ne vale la pena.

Non sarai in grado di evitare i join e sarai comunque un po ‘normalizzato.

Il mio approccio è avere una tabella delle etichette.

  TagId (PK)| TagName (Indexed) 

Quindi, hai una colonna TagXREFID nella tabella degli articoli.

Questa colonna TagXREFID è un FK per un terzo tavolo, lo chiamerò TagXREF:

  TagXrefID | ItemID | TagId 

Quindi, per ottenere tutti i tag per un object sarebbe qualcosa di simile:

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

E per ottenere tutti gli elementi per un tag, userei qualcosa del genere:

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

Per AND un insieme di tag insieme, è necessario modificare leggermente l’istruzione precedente per aggiungere AND Tags.TagName = @ TagName1 AND Tags.TagName = @ TagName2 ecc. E creare dynamicmente la query.

Quello che mi piace fare è avere un certo numero di tabelle che rappresentano i dati grezzi, quindi in questo caso avresti

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

Funziona velocemente per i tempi di scrittura e mantiene tutto normalizzato, ma puoi anche notare che per ogni tag, dovrai unire le tabelle due volte per ogni ulteriore tag che vuoi E, quindi ha una lettura lenta.

Una soluzione per migliorare la lettura è creare una tabella di caching su comando impostando una stored procedure che essenzialmente crea una nuova tabella che rappresenta i dati in un formato appiattito …

 CachedTagItems(ID, Name, , tag1, tag2, ... tagN) 

Quindi puoi considerare quanto spesso la tabella Tagged Item deve essere aggiornata, se si trova su ogni insert, quindi chiamare la stored procedure in un evento di inserimento del cursore. Se si tratta di un’attività oraria, impostare un lavoro orario per eseguirlo.

Ora per essere davvero intelligenti nel recupero dei dati, ti consigliamo di creare una stored procedure per ottenere i dati dai tag. Anziché utilizzare query nidificate in un’enunciazione caso massiva, si desidera passare un singolo parametro contenente un elenco di tag che si desidera selezionare dal database e restituire un set di record di elementi. Questo sarebbe meglio in formato binario, usando operatori bit a bit.

In formato binario, è facile da spiegare. Diciamo che ci sono quattro tag da assegnare a un object, in binario potremmo rappresentarlo

 0000 

Se tutti e quattro i tag sono assegnati a un object, l’object sarebbe simile a questo …

 1111 

Se solo i primi due …

 1100 

Quindi è solo un caso di trovare i valori binari con gli 1 e gli zeri nella colonna desiderata. Usando gli operatori Bitwise di SQL Server, puoi verificare che ci sia un 1 nella prima delle colonne usando query molto semplici.

Controlla questo link per saperne di più .

Per parafrasare quello che hanno detto gli altri: il trucco non è nello schema , è nella query .

Lo schema ingenuo di Entità / Etichette / Tag è la strada giusta da percorrere. Ma come hai visto, non è immediatamente chiaro come eseguire una query AND con molti tag.

Il modo migliore per ottimizzare tale query dipenderà dalla piattaforma, quindi consiglierei di re-taggare la domanda con il vostro RDBS e di cambiare il titolo in qualcosa come “Modo ottimale per eseguire E query su un database di tagging”.

Ho alcuni suggerimenti per MS SQL, ma si asterrà nel caso in cui non sia la piattaforma che stai usando.

Una variante alla risposta sopra è prendere gli id ​​dei tag, ordinarli, combinarli come una stringa ^ separata e cancellarli. Quindi associare semplicemente l’hash all’elemento. Ogni combinazione di tag produce una nuova chiave. Per eseguire una ricerca AND, ricrea semplicemente l’hash con gli ID tag e la ricerca specificati. La modifica dei tag su un object farà ricreare l’hash. Gli articoli con lo stesso set di tag condividono la stessa chiave di hash.

Se hai un tipo di array, puoi pre-aggregare i dati necessari. Vedi questa risposta in un thread separato:

qual è l’utilità del tipo di matrice?