data - mysql tree traversal




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

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

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:

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 nodi interni
    • Limitato limite alla profondità della gerarchia

Note specifiche del database

MySQL

Oracolo

  • Usa CONNECT BY per attraversare le liste di adiacenza

PostgreSQL

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

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 nodi convertiti in meno di un minuto e 100.000 nodi 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 è 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 somma 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.


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 nodi 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 nodi 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 | Gaviiformes                   |
|     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 | Podicipediformes              |
|     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.


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. È possibile (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;




hierarchical-data