Posts tagged: strutture dati

Nested Set + Java + Spring + Postgresql + Pl/pgsql + Yahoo framework

hierarchicE’ da 4-5 giorni che sono alle prese con un problemino, che all’inizio sembrava di facile soluzione, ma alla fine, ha impegnato un pò di tempo e non solo….ha richiesto l’uso di molte tecnologie e alla fine mi ha dato soddisfazione, che ovviamente voglio condividere con voi….voi chi, visto che non posta ancora nessuno? ancora non è chiaro :P Dunque il problema in origine era: come faccio a memorizzare una struttura dati gerarchica all’interno di un database ? Se vi fermate un attimo a pensarci, vi accorgerete che la risposta non è né banale, né immediata.Avevo già utilizzato una soluzione tempo fa, ma mi sono reso conto che non era molto potente dal momento che, la struttura gerarchica per quella particolare specifica era statica, quindi non era possibile aggiungere/eliminare alcun elemento, e per modificarla occorreva un grosso refactoring. Dopo di che mi sono imbattuto nell’algoritmo Preorder traversal tree o Nested set molto potente che consente di memorizzare una struttura gerarchica da albero all’interno di un database relazionale, e mi accorgo che la soluzione da me usata in precedenza ha un nome ben preciso Adjacency List Model che in effetti ha una serie di limitazioni come ho potuto riscontrare sul campo. Non starò qui a descrivere nel dettaglio come funzionano i 2 algoritmi, potete tranquillamente approfondire seguendo i link di sopra che spiegano in modo esaustivo il concetto che sta dietro. Sappiate solo che per risolvere i problemi dell’Adjacency List Model, l’algoritmo Nested Set tende ad aggiungere delle meta-informazioni che permettono di recuperare i dati relativi alla struttura gerarchica al costo di query molto semplici che usano dei self-join. Analizziamo ora lo sviluppo dell’applicazione in blocchi.

  • Business Logic La logica di business include diverse componenti, tra cui Spring il potente framework utilizzato per lo sviluppo di applicazione web J2EE, database Postgresql e il linguaggio procedurale PL/pgsql. La logica di Spring ha richiesto lo sviluppo di un interfaccia che descrive le operazioni possibili sull’albero, una classe che la implementa che definisce la logica delle operazioni e comunica con lo strato del database. Il database contiene la struttura di una tabella per memorizzare le informazioni sull’albero, con le sue meta-informazioni. Ho aggiunto una meta-informazione aggiuntiva che definisce la profondità di ciascun nodo, utile poi in fase di visualizzazione.
     CREATE TABLE nestedset ( idnode serial NOT NULL, nome CHARACTER VARYING NOT NULL, descrizione CHARACTER VARYING NOT NULL, lft INTEGER NOT NULL, rgt INTEGER NOT NULL, depth INTEGER );

    Tutte le operazioni a livello di database per la gestione dell’albero, sono implementate all’interno del database stesso sotto forma di funzioni procedurali scritte in linguaggio PL/pgsql. Le funzioni realizzate sono:

    • setnodesdepth che aggiorna il campo profondità della tabella subito dopo un operazione di inserimento o cancellazione.
    • insertnode, inserisce un nodo all’interno dell’albero.
    • deletesubtree, elimina un nodo dall’albero. Distinguiamo 2 casi: 1, nodo non ha figli e viene eliminato; 2, nodo ha figli e quindi tutto il sottoalbero viene eliminato.
    • deleteparentnode, elimina un singolo nodo dall’albero. Se il nodo ha figli, questi ultimi vengono spostati verso l’alto di un livello.

    Sono ‘slegate’ dall’implementazione Java in modo da poter apportare modifiche senza influire sul codice, ovviamente dipende dalla modica.

  • Presentation logic La logica di presentazione include il framework di Yahoo, in particolare il TreeView Control che mappa l’albero sul componente grafico per visualizzarlo, con in aggiunta un menù contestuale, che permette di realizzare le operazioni di Aggiunta nodo/elimina sottoalbero. Nota:La funzione elimina singolo nodo non è stata mappata ad alcuna voce di menù.

DI seguito trovate alcuni riferimenti sull’argomento e qui il pacchettino con i file sorgenti.

Alla prossima….

WordPress Themes