Database  »  Articoli  »  MySQL 

Alla ricerca di una soluzione migliore

Dopo aver constatato che la prima soluzione proposta, quella effettivamente più intuitiva, si è rivelata inadatta al nostro scopo, proviamo ad affrontare il problema da un altro punto di vista.

L'approccio che andiamo a descrivere è stato suggerito da Joe Celko, uno dei personaggi più in vista nel mondo dei database, per cui ci rifaremo direttamente ai suoi insegnamenti, che ci arrivano tramite numerosi scritti, alcuni dei quali elencati nel paragrafo conclusivo.

Per comprendere meglio questa nuova soluzione, possiamo considerare la nostra struttura gerarchica non solo come un albero, ma piuttosto come una serie di insiemi e sottoinsiemi, da cui il nome "nested sets". In figura 5 troviamo una rappresentazione insiemistica della struttura aziendale proposta nella prima parte dell'articolo.

Figura 5

Naturalmente è sbagliato pensare ad una persona come ad un insieme. Si tratta invece, in questo esempio, di avere una visualizzazione semplice di chi è il capo (l'insieme più grande) e di chi sono i vari dipendenti (gli insiemi via via innestati).

Un ulteriore punto di vista, che servirà poi per implementare nella pratica questo nuovo approccio, consiste nel riprendere l'albero e scorrerlo completamente dalla radice, passando per i nodi intermedi, ai nodi foglia, per poi tornare alla radice. Ad ogni nodo associamo due etichette che conterranno un numero crescente. La numerazione parte dalla radice, in cui è necessario segnare la prima etichetta col numero 1. Si prosegue scendendo attraverso i livelli, marcando sempre la prima etichetta di ciascun nodo. Arrivando ai nodi foglia, non sarà più possibile scendere, per cui si andrà a marcare anche la seconda etichetta per poi risalire di un livello. Quando tutte le foglie sono state etichettate due volte, si risale via via fino alla radice.

L'ordine apparentemente strano di questi numeri ci fornisce però alcuni risultati che sono predicibili, grazie ai quali possiamo costruire delle query che tornano poi estremamente utili. Notiamo ad esempio che la radice è sempre marcata con il numero 1 e con il numero N*2, dove N è il numero totale dei nodi. Inoltre ogni nodo foglia è marcato con due numeri consecutivi.

La figura 6 rappresenta la solita struttura aziendale, aggiornata con le nuove etichette: consideriamo la prima etichetta quella di sinistra, mentre la seconda quella di destra.

Figura 6

Il fatto di attraversare in questo modo l'albero, modificando il normale "ordine" dei nodi (che per altro non ne hanno uno definito), offre il nome all'algoritmo, ossia Modified Preorder Tree Traversal Algorithm.

Altri articoli

Altre guide

Altre newsletter