[PILLOLA] Dati gerarchici e db (ricorsione)

[mircov]

Bene, visto che sul forum ho visto parecchie richieste di aiuto riguardo la creazione di un sistema di directories e

sottodirectories e visto che in rete la documentazione in italiano a riguardo è inesistente (o almeno io non ho trovato

niente) ho deciso di scrivere questa pillola su come porre rimedio a questo problema.
Cominciamo con un po' di teoria.
I sistemi che sono maggiormente usati per raggiungere lo scopo in oggetto sono due:

1) Gestione gerarchica
2) Gestione orizzontale

Noi eamineremo solo la prima di queste due alternative.
La ricorsione è un sistema ampiamente usato in programmazione attraverso il quale una funzione richiama se stessa.
La ricorsione è alla base del nostro sitema.
Ovviamente ci sono vantaggi e svantaggi.
I vantaggi sono che il sistema è molto più semplice da utilizzare.
Gli svantaggi che per ogni record va fatta una query, la ricorsione è cmq un processo più lento rispetto ala gestione

orizzontale (che invece utilizza una sola query) e di conseguenza non va molto bene per ottenere alberi molto grandi con una

gerarchia abbastanza ramificata.

Bene, fatte le chiacchiere passiamo alla pratica.
Cominciamo con l'organizzazione del db.

Abbiamo una tabella "categories" con i campi id,name,parent

id = è l'id univoco del record (autoincrement)
name = il nome della categoria
parent = l'id della categoria padre (se zero significa che la categoria non è una sottocategoria)

Vi faccio un esempio per farvi capire come sarebbe nel db l'insieme di dati:

+------+-----------------+----------+
|  ID  |  NAME           |  PARENT  |
+------+-----------------+----------+
|  1   | Programmazione  |     0    |
+------+-----------------+----------+
|  2   | C               |     1    |
+------+-----------------+----------+
|  3   | Guide           |     2    |
+------+-----------------+----------+
|  4   | Tutorials       |     2    |
+------+-----------------+----------+
|  5   | Pascal          |     1    |
+------+-----------------+----------+
|  6   | Guide           |     5    |
+------+-----------------+----------+
|  7   | Tutorials       |     5    |
+------+-----------------+----------+

Passiamo alla costruzione della funzione (la posto ora per comodità e poi passo a spiegarvi come funziona).

 1 function ShowCats ($id,$name,$level)
 2         {
 3           global $categories;
 4         $query = "SELECT id,name,parent FROM categories WHERE parent=$id ORDER BY name";
 5          
 6         $result = mysql_query($query,$db);
 7         while ($row = mysql_fetch_array($result))
 8          {
 9             $name = str_repeat("",$level) . $row['name'] .  "\n";
10             $categories["$name"] = $row['id'];
11             ShowCats ($row['id'],$name,$level+1);
12              }
13         return $categories;
14         } 

riga 1
Definizione del nome della funzione e parametri da passarle

$id = è l'id della categoria che fungerà da root. In pratica la categoria a partire dalla quale vogliamo far partire la

funzione
$name = il nome della categoria passata
$level = un contatore che servirà per costruire graficamente l'albero

riga 3
Definiamo come globale una variabile definita all'esterno della funzione. La variabile va definita come array
$categories = array();

riga 4,6,7
Il codice per estrarre i record dal db

riga 9
str_repeat ripete la stringa indicata come primo parametro x volte dove x è un numero indicato dal seconod parametro (avete

capito a cosa srviva $level?)
Questa è la parte che "costruisce" graficamente l'albero.

riga 10
inseriamo nell'array il nome della categoria ed il suo id

riga 11
Ed eccoci arrivati all'oggetto di questa pillola: la ricorsione.
Come vedete la funzione richiama se stessa passando i dati che ha estratto e costruito

riga 13
Dopo aver eseguito tutte le operazioni ritorna l'array $categories riempito con il nostro bell'albero.


Vi starete chiedendo: "Ora ho estratto tutti i dati e li ho messi nell'array. E mò come li mostro?"

E' presto data una risposta alla domanda che vi sta frullando in testa.

In questo semplice modo:

1) Fate una query estraendo tutti i record dove parent = 0
2) nel ciclo while per ogni record estratto richiamate la funzione di sopra
3) Altro cicolo while sull'array

//seleziono tutte le righe dove "padre = 0" estraendo id e nome
$QueryCategories = "SELECT id,name,parent FROM categories WHERE parent = 0 ORDER BY name";
$ResultCategories = mysql_query($QueryCategories);
while ($RowCategories = mysql_fetch_array($ResultCategories))
     {
    //definisco l'array che poi mi servirà per la funzione
        $categories = array();
    
        // Richiamo la funzione
        ShowCats($RowCategories['id'],$RowCategories['name'],'catalogo_categories',1);
    echo $RowCategories['name'] . ' [' . $RowCategories['id'] . ']';
        while (list($name, $id) = each ($categories))
             {
        echo $name . ' [' . $id . ']';
         } // End while list     
} // End while query 

Otterrete così qualcosa del tipo

nome_categoria [id_categoria]

Abbiamo finito. Semplice no?!
Spero di aver fatto cosa gradita scrivedo questa pillola.
A questo punto possiamo salutarci e non mi resta che dirvi di postare migliorie al codice, perplessità, consigli, perchè no... complimenti e tutto quello che vi passa per la testa (senza andare OT ovviamente!)

[andr3a]

ora non so se questo mi ometodo sperimentale e' da definirsi "gestione orizzontale" , sta' di fatto che con una query sola tira fuori un array ordinato .

Per chi fosse interessato la classe e' qui:
http://www.devpro.it/php4_id_64.html

e questa e' una pagina di esempio, create un database di nome
test_tree e la tabella foglie come descritto nei commenti

<?php
/**
 * DATABASE test_tree
 * la tabella foglie puo' contenere quanti campi volete
 * unico VINCOLO e' il campo per il parent_id
 * che dovra' essere un VARCHAR
 * ------------------------------------------
 * CREATE TABLE foglie (
 *	id INT(10) NOT NULL AUTO_INCREMENT PRIMARY KEY,
 *	descrizione VARCHAR( 255 ),
 *	link VARCHAR( 255 ),
 *	parent_id VARCHAR( 255 )
 * )
 * ------------------------------------------
 * NOTA: la tabella foglie va creata prima di usare la classe
 */

// dichiaro nome database e nome tabella foglie
$dbname = 'test_tree';
$fogliename = 'foglie';

// richiedo la classe
require( 'MySQL_TreeManager.class.php' );

// mi connetto al database
$db = &mysql_connect( 'localhost', 'root', 'password' );

// istanzio la classe passando connessione e nome database
$dbtree = &new MySQL_TreeManager( $db, $dbname );

// se non ci sono livelli, per fare il test, li creo
// per ricreare una strutura di esempio come quella di mircov
if( $dbtree->getLevels() == 0 ) {
        
        // setto il primo livello
        $dbtree->setLevels(1);
        
        // metto il "super" parent ( uno o piu' super parents, basta usare il NULL )
        $dbtree->addSubLevel( NULL, 'Programmazione', 'descrizione ramo programmazione' );
        
        // sotto livello di Programmazione
        $dbtree->addSubLevel( 'Programmazione', 'C', 'descrizione del linguaggio C' );
        
        // sottolivelli di Programmazione / C
        $dbtree->addSubLevel( Array( 'Programmazione', 'C' ), 'Guide', 'lista guide disponibili' );
        $dbtree->addSubLevel( Array( 'Programmazione', 'C' ), 'Tutorials', 'elenco dei tutorials disponibili' );
        
        // altro sotto livello di Programmazione
        $dbtree->addSubLevel( 'Programmazione', 'Pascal', 'descrizione del linguaggio Pascal' );
        
        // sottolivelli di Programmazione / Pascal
        $dbtree->addSubLevel( Array( 'Programmazione', 'Pascal' ), 'Guide', 'lista guide disponibili' );
        $dbtree->addSubLevel( Array( 'Programmazione', 'Pascal' ), 'Tutorials', 'elenco dei tutorials disponibili' );
        
        // un po' di "foglie"
        $foglia1 = $dbtree->getNode( 'Programmazione', 'C', 'Guide' );
        $foglia1 = 'INSERT INTO '.$fogliename.' VALUES ( NULL, "guida per il C", "http://www...", "'.$foglia1.'" )';
        
        $foglia2 = $dbtree->getNode( 'Programmazione', 'C', 'Tutorials' ); 
        $foglia2 = 'INSERT INTO '.$fogliename.' VALUES ( NULL, "tutorial per il C", "http://www...", "'.$foglia2.'" )';
        
        $foglia3 = $dbtree->getNode( 'Programmazione', 'Pascal', 'Guide' ); 
        $foglia3 = 'INSERT INTO '.$fogliename.' VALUES ( NULL, "guida per il Pascal", "http://www...", "'.$foglia3.'" )';
        
        $foglia4 = $dbtree->getNode( 'Programmazione', 'Pascal', 'Tutorials' ); 
        $foglia4 = 'INSERT INTO '.$fogliename.' VALUES ( NULL, "tutorial per il Pascal", "http://www...", "'.$foglia4.'" )';

        // popolo il database
        mysql_unbuffered_query( $foglia1 ) or die( mysql_error() );
        mysql_unbuffered_query( $foglia2 ) or die( mysql_error() );
        mysql_unbuffered_query( $foglia3 ) or die( mysql_error() );
        mysql_unbuffered_query( $foglia4 ) or die( mysql_error() );
}

// prendo l' Array associativo rilasciato dal metodo getArray
// passando il nome della tabella con le foglie
$queryTree = &$dbtree->getArray( $fogliename );

// controllo che non sia vuoto e stampo in var_dump
if( $queryTree !== false ) {
        echo '<pre>';
        var_dump( $queryTree );
        echo '</pre>';
} 
?>

risultato

array(1) {
  ["Programmazione"]=>
  array(3) {
    ["_description_"]=>
    string(31) "descrizione ramo programmazione"
    ["C"]=>
    array(3) {
      ["_description_"]=>
      string(28) "descrizione del linguaggio C"
      ["Guide"]=>
      array(2) {
        ["_description_"]=>
        string(23) "lista guide disponibili"
        [0]=>
        array(4) {
          [0]=>
          string(1) "1"
          [1]=>
          string(14) "guida per il C"
          [2]=>
          string(13) "http://www..."
          [3]=>
          string(5) "1|1|1"
        }
      }
      ["Tutorials"]=>
      array(2) {
        ["_description_"]=>
        string(32) "elenco dei tutorials disponibili"
        [0]=>
        array(4) {
          [0]=>
          string(1) "2"
          [1]=>
          string(17) "tutorial per il C"
          [2]=>
          string(13) "http://www..."
          [3]=>
          string(5) "1|1|2"
        }
      }
    }
    ["Pascal"]=>
    array(3) {
      ["_description_"]=>
      string(33) "descrizione del linguaggio Pascal"
      ["Guide"]=>
      array(2) {
        ["_description_"]=>
        string(23) "lista guide disponibili"
        [0]=>
        array(4) {
          [0]=>
          string(1) "3"
          [1]=>
          string(19) "guida per il Pascal"
          [2]=>
          string(13) "http://www..."
          [3]=>
          string(5) "1|2|3"
        }
      }
      ["Tutorials"]=>
      array(2) {
        ["_description_"]=>
        string(32) "elenco dei tutorials disponibili"
        [0]=>
        array(4) {
          [0]=>
          string(1) "4"
          [1]=>
          string(22) "tutorial per il Pascal"
          [2]=>
          string(13) "http://www..."
          [3]=>
          string(5) "1|2|4"
        }
      }
    }
  }
}

0.023606

il tutto sta' a vedere quanto si guadagna in prestazioni su databases di grandi dimensioni rispetto il metodo di mircov ( adesso su questa struttura molto semplice sto sugli 0.03 di tempo trascorso, vorrei sapere i tuoi tempi mircov ), pero' e' un' alternativa valida per la ricorsivita' di ricerca ( ihmo ? )

@ 13manuel84 , la classe l' ho aggiornata perche' il getNode in MySQL 4.1.9-nt dava uno strano risultato ... ora e' ok, fammi sapere se ti va bene anche sul tuo script, grazie

[daniele_dll]

mmm la pillola è interessante ma con strutture grandi muore tutto

metti che potresti avere 3 livelli...ed ogni livello 3 figli...quindi lanceresti...

(Query Iniziale) 1 + (I primi 3 figli) 3 + 3 (I figli del primo figlio) + 3 (I figli del primo figlio del primo figlio) + 3 (i figli del secondo figlio del primo figlio) + 3 (i figli del terzo figlio del primo figlio) + ......... N

e come capisci bene lanci una marea di query...e tenendo conto che richiami ricorsivamente la stessa funzione...rischi di causare uno stack overflow e di far scoppiare tutto
quindi mi sa che ti conviene dichiarare delle variabili statiche e comunque il numero di query è un po estremo (oltre al fatto che nel caso specifico non usi mysql free result e quindi le query di php vengono eliminate tutte al momento della chiusura di php stesso occupando un sacco di memoria inutile)

cmq, a livello di studio, rimane uno dei sistemi più semplici per introdurre all'argomento ))

sciauzzz

[andr3a]

il mio metodo invece e' testato su 10 livelli ma potrebbero essere anche 20 ... visto i tempi di risposta ... 1 query, tutto l' ambaradan ( di fatto le query sono 2 ... ma una serve solo per vedere le tabelle categorie che ci sono, quindi irrisoria, l' altra per tirare fuori tutto in una botta sola )

che ne pensi ? ( a perte le & dappertutto )

[M4rko]

quanta fretta, non potevate aspettare giovedi prossimo?

[edit] mi è partito il post incompleto

i problemi con l'adjacency list (il metodo proposto da mircov) arrivano quando l'albero comincia a crescere, nel senso che servono troppe query
inoltre cancellare un nodo, o spostare un ramo risulta scomodo

il metodo di andrea non riesco ad inquadrarlo (leggere il codice altrui, anche se pulito e commentato, mi provoca sempre l'ansia)
andrea: in pratica fai una tabella per ogni livello? non risulta scomodo?

[andr3a]

veramente la mia classe e' su da mesi ... :rollo:

senti, ti stampo una query di esempio ( di questa struttura ) unica generata dinamicamente dalla classe e mi dici cosa ne pensi ?



SELECT * FROM __category__0 LEFT JOIN __category__1 ON __category__0.id = __category__1.parent_id LEFT JOIN __category__2 ON __category__1.id = __category__2.parent_id LEFT JOIN foglie ON foglie.parent_id = CONCAT_WS( "|", __category__0.id, __category__1.id, __category__2.id )

[Fabio Heller]

Ciao,

[PROMOTION]
il problema della ricorsività descritto da Daniele è serio, per questa ragione esiste una soluzione alternativa che richiede pochissime query, in certi casi una soltanto.

Per questo vi consiglio di correre a leggere l'articolo di Marko appena uscirà

Immagino che anche la classe di Andrea utilizzi il sistema alternativo, ma ancora non l'ho scaricata
[/PROMOTION]

[andr3a]

ma sono un fantasma o mi avete tutti in ignore ???



il mio metodo usera' SEMPRE un' unica query ( 2 di fatto ma una e' IRRISORIA => SELECT COUNT(id) FROM __categories__ WHERE label LIKE "__category__%" , l'altra e' mostrata qui sopra e generata dinamicamente ) sia che ci siano 3 livelli, sia che ce ne siano 19328 ....

[M4rko]

[supersaibal]Originariamente inviato da andr3a
veramente la mia classe e' su da mesi ... :rollo:

senti, ti stampo una query di esempio ( di questa struttura ) unica generata dinamicamente dalla classe e mi dici cosa ne pensi ?



SELECT * FROM __category__0 LEFT JOIN __category__1 ON __category__0.id = __category__1.parent_id LEFT JOIN __category__2 ON __category__1.id = __category__2.parent_id LEFT JOIN foglie ON foglie.parent_id = CONCAT_WS( "|", __category__0.id, __category__1.id, __category__2.id ) [/supersaibal]

L'idea è simpatica, ma non so se sia la struttura ottimale.
Resto un po perplesso di fronte all'aumentare del numero di join man mano che i livelli aumentano.
Sicuramente mi piace di piu della scelta ricorsiva.

Però se devi spostare un ramo dell'albero o cancellare un nodo intermedio, la situazione è gestibile comodamente?


@Fabio: grazie
il "metodo alternativo" lo discuto nella seconda paarte dell'articolo

[andr3a]

[supersaibal]Originariamente inviato da M4rko
L'idea è simpatica, ma non so se sia la struttura ottimale.
Resto un po perplesso di fronte all'aumentare del numero di join man mano che i livelli aumentano.[/supersaibal]

test su 15 livelli di sotto-foglie ...

array(2) {
  ["Seme"]=>
  array(2) {
    ["_description_"]=>
    string(22) "per fare un albero ..."
    ["Germoglio"]=>
    array(2) {
      ["_description_"]=>
      string(22) "per fare un albero ..."
      ["Radice"]=>
      array(2) {
        ["_description_"]=>
        string(22) "per fare un albero ..."
        ["Foglia"]=>
        array(2) {
          ["_description_"]=>
          string(22) "per fare un albero ..."
          ["Rametto"]=>
          array(2) {
            ["_description_"]=>
            string(22) "per fare un albero ..."
            ["Ramoscello"]=>
            array(2) {
              ["_description_"]=>
              string(22) "per fare un albero ..."
              ["Ramo"]=>
              array(2) {
                ["_description_"]=>
                string(22) "per fare un albero ..."
                ["Tronchetto"]=>
                array(2) {
                  ["_description_"]=>
                  string(22) "per fare un albero ..."
                  ["Tronco"]=>
                  array(2) {
                    ["_description_"]=>
                    string(22) "per fare un albero ..."
                    ["Ramoscelli"]=>
                    array(2) {
                      ["_description_"]=>
                      string(22) "per fare un albero ..."
                      ["Rami"]=>
                      array(2) {
                        ["_description_"]=>
                        string(22) "per fare un albero ..."
                        ["Foglie"]=>
                        array(2) {
                          ["_description_"]=>
                          string(22) "per fare un albero ..."
                          ["Fiori"]=>
                          array(2) {
                            ["_description_"]=>
                            string(22) "per fare un albero ..."
                            ["Frutti"]=>
                            array(2) {
                              ["_description_"]=>
                              string(22) "per fare un albero ..."
                              ["Semi"]=>
                              array(2) {
                                ["_description_"]=>
                                string(22) "per fare un albero ..."
                                [0]=>
                                array(4) {
                                  [0]=>
                                  string(1) "9"
                                  [1]=>
                                  string(10) "tanti semi"
                                  [2]=>
                                  string(16) "http://albero.it"
                                  [3]=>
                                  string(29) "1|1|1|1|1|1|1|1|1|1|1|1|1|1|1"
                                }
                              }
                            }
                          }
                        }
                      }
                    }
                  }
                }
              }
            }
          }
        }
      }
    }
  }
  ["Programmazione"]=>
  array(3) {
    ["_description_"]=>
    string(31) "descrizione ramo programmazione"
    ["C"]=>
    array(3) {
      ["_description_"]=>
      string(28) "descrizione del linguaggio C"
      ["Guide"]=>
      array(2) {
        ["_description_"]=>
        string(23) "lista guide disponibili"
        [0]=>
        array(4) {
          [0]=>
          string(2) "10"
          [1]=>
          string(14) "guida per il C"
          [2]=>
          string(13) "http://www..."
          [3]=>
          string(5) "2|2|2"
        }
      }
      ["Tutorials"]=>
      array(2) {
        ["_description_"]=>
        string(32) "elenco dei tutorials disponibili"
        [0]=>
        array(4) {
          [0]=>
          string(2) "11"
          [1]=>
          string(17) "tutorial per il C"
          [2]=>
          string(13) "http://www..."
          [3]=>
          string(5) "2|2|3"
        }
      }
    }
    ["Pascal"]=>
    array(3) {
      ["_description_"]=>
      string(33) "descrizione del linguaggio Pascal"
      ["Guide"]=>
      array(2) {
        ["_description_"]=>
        string(23) "lista guide disponibili"
        [0]=>
        array(4) {
          [0]=>
          string(2) "12"
          [1]=>
          string(19) "guida per il Pascal"
          [2]=>
          string(13) "http://www..."
          [3]=>
          string(5) "2|3|4"
        }
      }
      ["Tutorials"]=>
      array(2) {
        ["_description_"]=>
        string(32) "elenco dei tutorials disponibili"
        [0]=>
        array(4) {
          [0]=>
          string(2) "13"
          [1]=>
          string(22) "tutorial per il Pascal"
          [2]=>
          string(13) "http://www..."
          [3]=>
          string(5) "2|3|5"
        }
      }
    }
  }
}

0.028933

stesso tempo dei 3 livelli ... ma sono 5 volte tanto ...

[supersaibal]Originariamente inviato da M4rko
Sicuramente mi piace di piu della scelta ricorsiva.

Però se devi spostare un ramo dell'albero o cancellare un nodo intermedio, la situazione è gestibile comodamente?
[/supersaibal]

spostare un ramo, sullo stesso livello e' semplicissimo, basta cabiargli il parent

spostare un ramo dove vuoi non e' un metodo della classe
eliminare un ramo elimina in automatico tutti i sottorami e ripara le foglie ... se non ricordo male

tutto quello che non c'e' e' perche' non ho avuto tempo di metterlo nella classe ... senno' si tratta solo di spostare o aggiornare dati in una o piu' tabelle ... ovviamente non sono , entrambi, metodi semplici da implementare per via delle gerarchie ....

esempio:

sposto un ramo, che succede ai sottrami ??? ... sposto tutto ?

allora facilmente implementabile .... sposto un ramo, che succede ai sottorami, si accodano a quello superiore di quello che ho spostato ? ... complicato ma fattibile, come tutto il resto ...


cmq ecco la query del risultato mostrato sopra:

SELECT * FROM __category__0 LEFT JOIN __category__1 ON __category__0.id = __category__1.parent_id LEFT JOIN __category__2 ON __category__1.id = __category__2.parent_id LEFT JOIN __category__3 ON __category__2.id = __category__3.parent_id LEFT JOIN __category__4 ON __category__3.id = __category__4.parent_id LEFT JOIN __category__5 ON __category__4.id = __category__5.parent_id LEFT JOIN __category__6 ON __category__5.id = __category__6.parent_id LEFT JOIN __category__7 ON __category__6.id = __category__7.parent_id LEFT JOIN __category__8 ON __category__7.id = __category__8.parent_id LEFT JOIN __category__9 ON __category__8.id = __category__9.parent_id LEFT JOIN __category__10 ON __category__9.id = __category__10.parent_id LEFT JOIN __category__11 ON __category__10.id = __category__11.parent_id LEFT JOIN __category__12 ON __category__11.id = __category__12.parent_id LEFT JOIN __category__13 ON __category__12.id = __category__13.parent_id LEFT JOIN __category__14 ON __category__13.id = __category__14.parent_id LEFT JOIN foglie ON foglie.parent_id = CONCAT_WS( "|", __category__0.id, __category__1.id, __category__2.id, __category__3.id, __category__4.id, __category__5.id, __category__6.id, __category__7.id, __category__8.id, __category__9.id, __category__10.id, __category__11.id, __category__12.id, __category__13.id, __category__14.id )