Tagging gerarchico in SQL

Question

Ho un'applicazione web PHP che utilizza un database MySQL per la codifica degli oggetti, in cui ho usato la struttura di tag accettata come risposta a questa domanda SO .

Vorrei implementare una gerarchia di tag, in cui ogni tag può avere un tag genitore univoco. Le ricerche di un tag padre T corrisponderebbero quindi a tutti i discendenti di T (ad esempio, T, tag di cui padre è T (figli di T), nipoti di T, ecc.)

Il modo più semplice per farlo sembra essere quello di aggiungere un campo ParentID alla tabella dei tag, che contiene l'ID del tag parent di un tag o un numero magico se il tag non ha parent. La ricerca di discendenti, tuttavia, richiede quindi ripetute ricerche complete del database per trovare i tag in ogni "generazione", che vorrei evitare.

Un modo (presumibilmente) più veloce, ma meno normalizzato per farlo sarebbe quello di avere una tabella contenente tutti i figli di ogni tag, o anche tutti i discendenti di ciascun tag. Ciò comporta tuttavia il rischio di dati incoerenti nel database (ad esempio un tag che è figlio di più di un genitore).

C'è un buon modo per fare query per trovare rapidamente i discendenti, mantenendo i dati il ??più possibile normalizzati?

Answer 1

La risposta di Ali ha un link a Alberi e gerarchie di Joe Celko in SQL per Smarties , il che conferma il mio sospetto: non esiste una struttura di database semplice che offra il meglio di tutti i mondi. Il migliore per il mio scopo sembra essere l '"Albero di inserzione frequente" dettagliato in questo libro, che è come il "Modello di set nidificato" del collegamento di Ali, ma con indicizzazione non consecutiva. Ciò consente l'inserimento di O (1) ( a la numerazione di riga BASIC non strutturata), con riorganizzazione periodica dell'indice come e quando necessario.

Answer 2

L'ho implementato usando due colonne. Lo semplifico un po 'qui, perché dovevo mantenere il nome del tag in un campo / tabella separato perché dovevo localizzarlo in diverse lingue:

• tag
• path

Guarda queste righe per esempio:

tag            path
---            ----
database       database/
mysql          database/mysql/
mysql4         database/mysql/mysql4/
mysql4-1       database/mysql/mysql4-1/
oracle         database/oracle/
sqlserver      database/sqlserver/
sqlserver2005  database/sqlserver/sqlserver2005/
sqlserver2005  database/sqlserver/sqlserver2008/

ecc.

Utilizzando l'operatore like nel campo del percorso è possibile ottenere facilmente tutte le righe di tag necessarie:

SELECT * FROM tags WHERE path LIKE 'database/%'

Ci sono alcuni dettagli di implementazione come quando sposti un nodo nella gerarchia devi cambiare anche tutti i figli, ecc., ma non è difficile.

Assicurati anche che la lunghezza del tuo percorso sia abbastanza lunga - nel mio caso non ho usato il nome del tag per il percorso, ma un altro campo per assicurarmi di non avere percorsi troppo lunghi.

Answer 3

Alcuni modi qui

Answer 4

Potresti costruire quello che Kimball chiama una tabella degli aiutanti della gerarchia.

Supponi che la tua gerarchia assomigli a questo: A - > B | B - > C | C - > D

inseriresti i record in una tabella simile a questa

ParentID, ChildID, Depth, Highest Flag, Lowest Flag
A, A, 0, Y, N
A, B, 1, N, N
A, C, 2, N, N
A, D, 3, N, Y
B, B, 0, N, N
B, C, 1, N, N
B, D, 2, N, Y
C, C, 0, N, N
C, D, 1, N, Y
D, D, 0. N, Y

Penso di averlo corretto .... comunque. Il punto è che conservi ancora la tua gerarchia correttamente, devi solo creare questa tabella DALLA tua tabella corretta. QUESTA tabella esegue una query come una Banshee. Supponi di voler sapere quali sono tutti i primi livelli inferiori a B.

WHERE parentID = 'B' and Depth = 1

Answer 5

Userei un qualche tipo di array per archiviare i tag secondari, questo dovrebbe essere molto più veloce rispetto all'unire una tabella su se stesso (specialmente se hai un gran numero di tag). Ho dato un'occhiata e non so se mysql abbia un tipo di dati di array nativo, ma puoi emularlo usando una colonna di testo e memorizzando un array serializzato in esso. Se vuoi velocizzare ulteriormente le cose, dovresti essere in grado di inserire un indice di ricerca di testo su quella colonna per scoprire quali tag sono correlati.

[Modifica] Dopo aver letto l'articolo di Ali, ho fatto ancora un po 'di caccia e ho trovato questa su un mucchio di approcci per l'implementazione di gerarchie in postgres. Potrebbe essere ancora utile a fini esplicativi.