Quali sono le opzioni per la memorizzazione di dati gerarchici in un database relazionale?

Buone panoramiche

In generale, si sta prendendo una decisione tra tempi di lettura veloci (ad esempio, set nidificati) o tempi di scrittura rapidi (elenco di adiacenze). Di solito, si finisce con una combinazione delle opzioni di seguito che si adattano meglio alle proprie esigenze. Quanto segue fornisce una lettura approfondita:

  • Un altro confronto tra Nested Intervals e Adjacency List : il miglior confronto tra Adjacency List, Materialized Path, Nested Set e Nested Interval che ho trovato.
  • Modelli per i dati gerarchici : diapositive con buone spiegazioni dei compromessi e utilizzo degli esempi
  • Rappresentare gerarchie in MySQL : ottima panoramica del set annidato in particolare
  • Dati gerarchici in RDBMS : insieme di collegamenti più completo e ben organizzato che ho visto, ma non molto in termini di spiegazione

Opzioni

Sono a conoscenza di e caratteristiche generali:

  1. Lista di adiacenza :
    • Colonne: ID, ParentID
    • Facile da implementare.
    • Il nodo economico si muove, inserisce ed elimina.
    • Costoso per trovare il livello, ascendenza e discendenti, percorso
    • Evita N + 1 tramite Common Table Expressions nei database che li supportano
  2. Set nidificato (noto anche come Traversamento dell’albero preordinato modificato )
    • Colonne: sinistra, destra
    • Ascendenza economica, discendenti
    • Molto costoso O(n/2) muove, inserisce, cancella a causa della codifica volatile
  3. Bridge Table (aka trigger di chiusura tabella / w )
    • Utilizza una tabella di join separata con: antenato, discendente, profondità (facoltativo)
    • Ascendenza e discendenti economici
    • Scrive costi O(log n) (dimensione della sottostruttura) per inserimento, aggiornamenti, eliminazioni
    • Codifica normalizzata: buona per le statistiche RDBMS e il pianificatore di query in join
    • Richiede più righe per nodo
  4. Colonna del lignaggio (aka percorso materializzato , enumerazione dei percorsi)
    • Colonna: lignaggio (ad es. / Genitore / figlio / nipote / ecc …)
    • Discendenti economici tramite query prefissata (ad esempio LEFT(lineage, #) = '/enumerated/path' )
    • Scrive costi O(log n) (dimensione della sottostruttura) per inserimento, aggiornamenti, eliminazioni
    • Non relazionale: si basa sul tipo di dati Array o sul formato stringa serializzato
  5. Intervalli nidificati
    • Come il set nidificato, ma con reale / float / decimale, in modo che la codifica non sia volatile (mossa / inserimento / eliminazione economica)
    • Ha problemi di rappresentazione reale / fluttuante / decimale / precisione
    • La variante di codifica della matrice aggiunge la codifica degli antenati (percorso materializzato) per “libero”, ma con un’ulteriore complessità dell’algebra lineare.
  6. Tavolo piatto
    • Un elenco di adiacenze modificato che aggiunge una colonna di livello e classifica (ad es. Ordinamento) a ciascun record.
    • Economico per iterare / impaginare
    • Spostamento costoso ed eliminazione
    • Buon uso: discussione threaded – commenti forum / blog
  7. Colonne di lignaggio multiple
    • Colonne: una per ogni livello di lignaggio, si riferisce a tutti i genitori fino alla radice, i livelli inferiori dal livello dell’articolo sono impostati su NULL
    • Antenati economici, discendenti, livello
    • Inserto economico, cancella, sposta le foglie
    • Inserimento costoso, cancellazione, spostamento dei nodes interni
    • Limitato limite alla profondità della gerarchia

Note specifiche del database

MySQL

  • Utilizzare le variabili di sessione per l’elenco Adjacency

Oracolo

  • Usa CONNECT BY per attraversare le liste di adiacenza

PostgreSQL

  • Tipo di dati ltree per percorso materializzato

server SQL

  • Riassunto generale
  • 2008 offre il tipo di dati HierarchyId per aiutare con l’approccio Colonna Lineage ed espandere la profondità che può essere rappresentata.

La mia risposta preferita è come suggerito dalla prima frase in questa discussione. Utilizzare un elenco Adjacency per mantenere la gerarchia e utilizzare i set nidificati per interrogare la gerarchia.

Il problema finora è stato che il metodo di coverion da un Adjacecy List a Nested Sets è stato spaventosamente lento perché la maggior parte delle persone usa il metodo RBAR estremo conosciuto come “Push Stack” per fare la conversione ed è stato considerato come molto costoso per raggiungere il Nirvana della semplicità di manutenzione con l’Adjacency List e le fantastiche prestazioni degli Insiemi Nidificati. Di conseguenza, molte persone finiscono per doversi accontentare dell’uno o dell’altro soprattutto se ci sono più di, per dire, un pessimo 100.000 nodes o giù di lì. L’utilizzo del metodo push stack può richiedere un’intera giornata per eseguire la conversione su ciò che MLM’ers considererebbe una gerarchia di piccoli milioni di nodes.

Ho pensato di dare a Celko un po ‘di concorrenza inventando un metodo per convertire una lista di adiacenza in serie nidificate a velocità che sembrano semplicemente impossibili. Ecco le prestazioni del metodo push stack sul mio laptop i5.

 Duration for 1,000 Nodes = 00:00:00:870 Duration for 10,000 Nodes = 00:01:01:783 (70 times slower instead of just 10) Duration for 100,000 Nodes = 00:49:59:730 (3,446 times slower instead of just 100) Duration for 1,000,000 Nodes = 'Didn't even try this' 

Ed ecco la durata del nuovo metodo (con il metodo push stack tra parentesi).

 Duration for 1,000 Nodes = 00:00:00:053 (compared to 00:00:00:870) Duration for 10,000 Nodes = 00:00:00:323 (compared to 00:01:01:783) Duration for 100,000 Nodes = 00:00:03:867 (compared to 00:49:59:730) Duration for 1,000,000 Nodes = 00:00:54:283 (compared to something like 2 days!!!) 

Sì, è corretto. 1 milione di nodes convertiti in meno di un minuto e 100.000 nodes in meno di 4 secondi.

Puoi leggere il nuovo metodo e ottenere una copia del codice al seguente URL. http://www.sqlservercentral.com/articles/Hierarchy/94040/

Ho anche sviluppato una gerarchia “pre-aggregata” usando metodi simili. Gli MLM e le persone che elaborano le distinte materiali saranno particolarmente interessati a questo articolo. http://www.sqlservercentral.com/articles/T-SQL/94570/

Se ti fermi a dare un’occhiata a entrambi gli articoli, passa al link “Partecipa alla discussione” e fammi sapere cosa ne pensi.

Questo design non è stato ancora menzionato:

Colonne di lignaggio multiple

Anche se ha dei limiti, se riesci a sopportarli, è molto semplice e molto efficiente. Caratteristiche:

  • Colonne: una per ogni livello di lignaggio, si riferisce a tutti i genitori fino alla radice, i livelli sotto il livello degli elementi correnti sono impostati su NULL
  • Limita a quanto può essere profonda la gerarchia
  • Antenati economici, discendenti, livello
  • Inserto economico, cancella, sposta le foglie
  • Inserimento costoso, cancellazione, spostamento dei nodes interni

Segue un esempio: l’albero tassonomico degli uccelli in modo che la gerarchia sia Classe / Ordine / Famiglia / Genere / Specie – la specie è il livello più basso, 1 riga = 1 taxon (che corrisponde alle specie nel caso dei nodes foglia):

 CREATE TABLE `taxons` ( `TaxonId` smallint(6) NOT NULL default '0', `ClassId` smallint(6) default NULL, `OrderId` smallint(6) default NULL, `FamilyId` smallint(6) default NULL, `GenusId` smallint(6) default NULL, `Name` varchar(150) NOT NULL default '' ); 

e l’esempio dei dati:

 +---------+---------+---------+----------+---------+-------------------------------+ | TaxonId | ClassId | OrderId | FamilyId | GenusId | Name | +---------+---------+---------+----------+---------+-------------------------------+ | 254 | 0 | 0 | 0 | 0 | Aves | | 255 | 254 | 0 | 0 | 0 | Gaviiformss | | 256 | 254 | 255 | 0 | 0 | Gaviidae | | 257 | 254 | 255 | 256 | 0 | Gavia | | 258 | 254 | 255 | 256 | 257 | Gavia stellata | | 259 | 254 | 255 | 256 | 257 | Gavia arctica | | 260 | 254 | 255 | 256 | 257 | Gavia immer | | 261 | 254 | 255 | 256 | 257 | Gavia adamsii | | 262 | 254 | 0 | 0 | 0 | Podicipediformss | | 263 | 254 | 262 | 0 | 0 | Podicipedidae | | 264 | 254 | 262 | 263 | 0 | Tachybaptus | 

Questo è fantastico perché in questo modo esegui tutte le operazioni necessarie in un modo molto semplice, purché le categorie interne non cambino il loro livello nell’albero.

Questa è una risposta molto parziale alla tua domanda, ma spero comunque utile.

Microsoft SQL Server 2008 implementa due funzionalità estremamente utili per la gestione dei dati gerarchici:

  • il tipo di dati HierarchyId .
  • espressioni di tabella comuni, utilizzando la parola chiave with .

Dai un’occhiata a “Modelli le tue gerarchie di dati con SQL Server 2008” di Kent Tegels su MSDN per l’avvio. Vedi anche la mia domanda: query ricorsiva sulla stessa tabella in SQL Server 2008

Modello di adiacenza + modello di set nidificati

L’ho fatto perché potevo inserire facilmente nuovi elementi nell’albero (hai solo bisogno dell’ID di un ramo per inserire un nuovo elemento) e anche interrogarlo abbastanza velocemente.

 +-------------+----------------------+--------+-----+-----+ | category_id | name | parent | lft | rgt | +-------------+----------------------+--------+-----+-----+ | 1 | ELECTRONICS | NULL | 1 | 20 | | 2 | TELEVISIONS | 1 | 2 | 9 | | 3 | TUBE | 2 | 3 | 4 | | 4 | LCD | 2 | 5 | 6 | | 5 | PLASMA | 2 | 7 | 8 | | 6 | PORTABLE ELECTRONICS | 1 | 10 | 19 | | 7 | MP3 PLAYERS | 6 | 11 | 14 | | 8 | FLASH | 7 | 12 | 13 | | 9 | CD PLAYERS | 6 | 15 | 16 | | 10 | 2 WAY RADIOS | 6 | 17 | 18 | +-------------+----------------------+--------+-----+-----+ 
  • Ogni volta che hai bisogno di tutti i figli di qualsiasi genitore ti basta interrogare la colonna parent .
  • Se avevi bisogno di tutti i discendenti di qualsiasi genitore tu lft per gli articoli che hanno il loro lft tra lft e rgt del genitore.
  • Se avevi bisogno di tutti i genitori di qualsiasi nodo fino alla radice dell’albero, puoi lft una query per gli elementi con lft inferiore al lft del nodo e rgt più grande del rgt del nodo e ordinare il parent .

Avevo bisogno di rendere l’accesso e interrogare l’albero più velocemente degli inserti, ecco perché ho scelto questo

L’unico problema è correggere le colonne left e right quando si inseriscono nuovi elementi. ho creato una procedura memorizzata e l’ho chiamata ogni volta che ho inserito un nuovo object che era raro nel mio caso, ma è molto veloce. Ho avuto l’idea dal libro di Joe Celko, e la procedura memorizzata e il modo in cui l’ho ideata sono spiegate qui in DBA SE https://dba.stackexchange.com/q/89051/41481

Se il tuo database supporta matrici, puoi anche implementare una colonna di lignaggio o un percorso materializzato come una matrice di id padre.

In particolare con Postgres puoi quindi utilizzare gli operatori set per interrogare la gerarchia e ottenere prestazioni eccellenti con gli indici GIN. Ciò rende la ricerca di genitori, figli e profondità piuttosto banale in una singola query. Anche gli aggiornamenti sono abbastanza maneggevoli.

Se sei curioso, ho una descrizione completa dell’utilizzo di array per percorsi materializzati .

Questo è davvero un problema di buca quadrata, buco rotondo.

Se i database relazionali e SQL sono l’unico martello che hai o sei disposto a usare, allora le risposte che sono state pubblicate finora sono adeguate. Tuttavia, perché non utilizzare uno strumento progettato per gestire i dati gerarchici? Il database grafico è ideale per dati gerarchici complessi.

Le inefficienze del modello relazionale e le complessità di qualsiasi soluzione di codice / query per mappare un modello grafico / gerarchico su un modello relazionale non meritano lo sforzo rispetto alla facilità con cui una soluzione di database grafico può risolvere lo stesso problema.

Considerare una distinta base come una struttura dati gerarchica comune.

 class Component extends Vertex { long assetId; long partNumber; long material; long amount; }; class PartOf extends Edge { }; class AdjacentTo extends Edge { }; 

Percorso più breve tra due sottoinsiemi : algoritmo di attraversamento grafico semplice. I percorsi accettabili possono essere qualificati in base a criteri.

Somiglianza : qual è il grado di somiglianza tra due assemblee? Esegui una traversata su entrambi i sub-alberi calcolando l’intersezione e l’unione dei due sotto-alberi. La percentuale simile è l’intersezione divisa per l’unione.

Chiusura transitoria : percorri il sotto-albero e sum i campi di interesse, ad es. “Quanto alluminio è in una sottounità?”

Sì, puoi risolvere il problema con SQL e un database relazionale. Tuttavia, ci sono approcci molto migliori se si è disposti a utilizzare lo strumento giusto per il lavoro.

Sto usando PostgreSQL con le tabelle di chiusura per le mie gerarchie. Ho una procedura memorizzata universale per l’intero database:

 CREATE FUNCTION nomen_tree() RETURNS trigger LANGUAGE plpgsql AS $_$ DECLARE old_parent INTEGER; new_parent INTEGER; id_nom INTEGER; txt_name TEXT; BEGIN -- TG_ARGV[0] = name of table with entities with PARENT-CHILD relationships (TBL_ORIG) -- TG_ARGV[1] = name of helper table with ANCESTOR, CHILD, DEPTH information (TBL_TREE) -- TG_ARGV[2] = name of the field in TBL_ORIG which is used for the PARENT-CHILD relationship (FLD_PARENT) IF TG_OP = 'INSERT' THEN EXECUTE 'INSERT INTO ' || TG_ARGV[1] || ' (child_id,ancestor_id,depth) SELECT $1.id,$1.id,0 UNION ALL SELECT $1.id,ancestor_id,depth+1 FROM ' || TG_ARGV[1] || ' WHERE child_id=$1.' || TG_ARGV[2] USING NEW; ELSE -- EXECUTE does not support conditional statements inside EXECUTE 'SELECT $1.' || TG_ARGV[2] || ',$2.' || TG_ARGV[2] INTO old_parent,new_parent USING OLD,NEW; IF COALESCE(old_parent,0) <> COALESCE(new_parent,0) THEN EXECUTE ' -- prevent cycles in the tree UPDATE ' || TG_ARGV[0] || ' SET ' || TG_ARGV[2] || ' = $1.' || TG_ARGV[2] || ' WHERE id=$2.' || TG_ARGV[2] || ' AND EXISTS(SELECT 1 FROM ' || TG_ARGV[1] || ' WHERE child_id=$2.' || TG_ARGV[2] || ' AND ancestor_id=$2.id); -- first remove edges between all old parents of node and its descendants DELETE FROM ' || TG_ARGV[1] || ' WHERE child_id IN (SELECT child_id FROM ' || TG_ARGV[1] || ' WHERE ancestor_id = $1.id) AND ancestor_id IN (SELECT ancestor_id FROM ' || TG_ARGV[1] || ' WHERE child_id = $1.id AND ancestor_id <> $1.id); -- then add edges for all new parents ... INSERT INTO ' || TG_ARGV[1] || ' (child_id,ancestor_id,depth) SELECT child_id,ancestor_id,d_c+d_a FROM (SELECT child_id,depth AS d_c FROM ' || TG_ARGV[1] || ' WHERE ancestor_id=$2.id) AS child CROSS JOIN (SELECT ancestor_id,depth+1 AS d_a FROM ' || TG_ARGV[1] || ' WHERE child_id=$2.' || TG_ARGV[2] || ') AS parent;' USING OLD, NEW; END IF; END IF; RETURN NULL; END; $_$; 

Quindi per ogni tabella in cui ho una gerarchia, creo un trigger

 CREATE TRIGGER nomenclature_tree_tr AFTER INSERT OR UPDATE ON nomenclature FOR EACH ROW EXECUTE PROCEDURE nomen_tree('my_db.nomenclature', 'my_db.nom_helper', 'parent_id'); 

Per popolare una tabella di chiusura dalla gerarchia esistente, utilizzo questa stored procedure:

 CREATE FUNCTION rebuild_tree(tbl_base text, tbl_closure text, fld_parent text) RETURNS void LANGUAGE plpgsql AS $$ BEGIN EXECUTE 'TRUNCATE ' || tbl_closure || '; INSERT INTO ' || tbl_closure || ' (child_id,ancestor_id,depth) WITH RECURSIVE tree AS ( SELECT id AS child_id,id AS ancestor_id,0 AS depth FROM ' || tbl_base || ' UNION ALL SELECT t.id,ancestor_id,depth+1 FROM ' || tbl_base || ' AS t JOIN tree ON child_id = ' || fld_parent || ' ) SELECT * FROM tree;'; END; $$; 

Le tabelle di chiusura sono definite con 3 colonne: ANCESTOR_ID, DESCENDANT_ID, DEPTH. È ansible (e consiglio anche io) di archiviare i record con lo stesso valore per ANCESTOR e DISCENDENTE e un valore pari a zero per DEPTH. Ciò semplificherà le query per il recupero della gerarchia. E sono davvero molto semplici:

 -- get all descendants SELECT tbl_orig.*,depth FROM tbl_closure LEFT JOIN tbl_orig ON descendant_id = tbl_orig.id WHERE ancestor_id = XXX AND depth <> 0; -- get only direct descendants SELECT tbl_orig.* FROM tbl_closure LEFT JOIN tbl_orig ON descendant_id = tbl_orig.id WHERE ancestor_id = XXX AND depth = 1; -- get all ancestors SELECT tbl_orig.* FROM tbl_closure LEFT JOIN tbl_orig ON ancestor_id = tbl_orig.id WHERE descendant_id = XXX AND depth <> 0; -- find the deepest level of children SELECT MAX(depth) FROM tbl_closure WHERE ancestor_id = XXX;