Progettare database a grafo

I database di questa tipologia si basano su una struttura dati a grafo dotata di interfaccia CRUD, che offre quindi operazioni di creazione, lettura, aggiornamento e cancellazione dei dati. Un grafo è ciò che in informatica rappresenta meglio una rete. È costituito da nodi (detti vertici) e archi che stabiliscono collegamenti tra essi. Le informazioni sono presenti in entrambi: nei vertici che rappresentano aggregazioni di dati, e negli archi a simboleggiare un collegamento tra nodi e per definire dei valori che ne regolano le proprietà.

Gli archi, in particolare, "comunicano" informazioni in almeno tre modi: con la loro direzione (un collegamento dal nodo A al nodo B non equivale nè a uno che va in senso opposto nè a uno bidirezionale), con il significato (una relazione tra nodi in genere esprime un determinato rapporto di dipendenza tra essi), con le proprietà immagazzinate in essi (se i nodi - ad esempio - indicano due città, l'arco che li congiunge può contemplare come proprietà la distanza chilometrica che le separa). Il valore si estrae da un grafo percorrendolo, trovando percorsi tra i suoi nodi e soprattutto mettendo in luce collegamenti che a prima vista risulterebbero invisibili: non a caso il loro impiego trova spazio nell'ambito di social network, in quello scientifico (sociale, geografico, etc.) ma anche investigativo, nonchè nel settore della sicurezza.

I database a grafo permettono di ovviare bene agli svantaggi dei DBMS relazionali che abbiamo già citato in questa guida. Permettono infatti di scalare orizzontalmente mediante distribuzione dei dati su più nodi di rete senza richiedere il potenziamento hardware delle singole macchine. Inoltre, mediante il collegamento diretto tra nodi, evitano il costo richiesto dai JOIN in termini di performance. Il grafo è inoltre una struttura facilmente espandibile, che può essere esplorata parzialmente senza dover necessariamente coinvolgere una quantità eccessiva di dati. Lo svantaggio che si può accusare, come in altre realtà NoSQL, consiste nell'impossibilità di basarsi su procedure universali per la loro realizzazione e analisi, a causa della forte eterogeneità delle strutture dati cui danno vita.

Come strumento di esempio, utilizzeremo in queste lezioni un DBMS cui abbiamo già dedicato una guida, OrientDB, che costituisce un ottimo esempio di sistema per la gestione di un database a grafo.
In fase di esemplificazione, ci tornerà utile non solo la console testuale, ma anche OrientDB Studio, il client visuale.

Progettiamo il database

OrientDB si fonda, in primis, su un meccanismo ad oggetti che, come sappiamo, è l'ideale per l'aggregazione di dati in informazioni di più alto livello. Considerando che ci troviamo in una fase di progettazione, questo aspetto può tornarci utile visto che, qualunque sia il nostro problema, partiremo dalla definizione delle entità che lo compongono. Sottolineiamo a tal proposito - come già ricordato in precedenza - che un grafo si basa su due tipologie di concetti, i nodi e gli archi: questi ultimi non vanno considerati meri collegamenti tra oggetti, in quanto rivestiti di una grande dignità informativa, molto significativa. Pertanto sarà importante definire le entità principali e scegliere per loro un ruolo: chi sarà un nodo (diciamo la parte più statica dell'informazione, quella che in un database relazionale avrebbe costituito un record) e quale un arco (il collegamento dinamico da vedere un pò come le relazioni, che possono essere connotate con proprietà).

OrientDB permette di definire classi per rappresentare le entità individuate, ed in questo caso ne abbiamo già due da usare come modello: V ed E. Esse rappresentano, rispettivamente, vertici e archi di un grafo: volendo, ad esempio, nodi che rappresentano utenti, potremmo creare la classe Utente che estende V. La creazione di classi può essere realizzata sia utilizzando i comandi da console - come spiegato nella guida - sia sfruttando l'interfaccia visuale, come si vede nella figura seguente: al click del pulsante New Class, potremo sfruttare un'apposita finestra di dialogo:

Una volta create le classi, inizierà l'utilizzo del database che consisterà per lo più nell'inserimento dei dati. L'attività che risulterà più impegnativa con i grafi sarà costituita dalla analisi della rete creata. Esiste una grande varietà di comandi da console per svolgere queste operazioni, o anche in questo caso si può scegliere la via visuale tramite la scheda Graph offerta da Studio. Indipendentemente da quale di questi mezzi si sceglierà, teniamo in considerazione alcuni fattori sui grafi:

• come abbiamo detto, è fondamentale considerare la direzione di un arco; allo stesso modo, è importante considerare in un nodo quali sono gli archi entranti e quali quelli in uscita. Ogni volta che interrogheremo le proprietà di un vertice vedremo elencati i collegamenti in (in ingresso) e out (in uscita). Quando faremo le nostre analisi sui dati, sarà importante definire a priori, per ognuna di esse, se ci interessa visitare gli archi in, quelli out o entrambi: ovviamente un medesimo rapporto tra due vertici può essere letto in modo diverso alla luce della direzione dell'arco che li collega;
• l'operazione fondamentale sui grafi è il traversamento, che consiste nel trovare le possibili vie che da un nodo portano agli altri, soprattutto quelli raggiungibili indirettamente per svelare relazioni non inizialmente evidenti. Il traversamento, per il quale esiste il comando SQL di OrientDB TRAVERSE, può seguire due strategie:
  • in profondità (DEPTH_FIRST), la strategia di default, in cui l'ordine di visita mira ad esplorare i rami che partono da ogni nodo fino in fondo per poi passare agli altri;
    Figura 2. Visita in profondità di un grafo (click per ingrandire)
    
    
    
  • in ampiezza (BREADTH_FIRST) dove si mira a esplorare ogni figlio di un nodo prima di passare ai discendenti di questi:
    Figura 3. Visita in ampiezza di un grafo (click per ingrandire)
    
    
    
• un fattore importante da considerare nelle interrogazioni è la profondità che si vuole esplorare, intesa come distanza in archi tra due nodi. Questo dato, solitamente messo a disposizione delle query con la variabile $depth, risulta utile per ottimizzare la ricerca limitandola alla sfera di nostro interesse, con conseguente risparmio di risorse;

Chiariti nell'ordine questi aspetti, possiamo metterli in pratica con un esempio che vedrà coinvolta una rete di informazioni definita come grafo.