Il modello di dati a grafo è probabilmente uno dei più espressivi e permette di effettuare operazioni molto interessanti, difficili se non impossibili in un modello relazionale. In questo articolo, dapprima presentiamo le caratteristiche di Neo4j, un database a grafo open source; quindi, con un esempio vediamo come è possibile utilizzarlo con le operazioni più comuni, ma anche come il modello di dati permette di effettuare inferenza, ossia dedurre informazioni da un grafo dato. Infine accenniamo alle possibilità di rendere Neo4j un database distribuito.
Caratteristiche
Neo4j [1] è un database pienamente transazionale che memorizza dati sotto forma di grafo, nodi e archi. Rispetto ai tradizionali RDBMS, Neo4j offre un modello di dati molto flessibile ed espressivo, che permette di maneggiare facilmente l’incompletezza e facilitare l’inferenza, con un’API object oriented. A differenza di MongoDB, che rilassa le proprietà ACIDe [2] per una grande capacità di scalare orizzontalmente, esso non rinuncia alle transazioni per avere un grafo sempre consistente secondo le necessità dell’applicazione.
Le caratteristiche fondamentali di questo database, che analizzeremo, sono:
- modalità di utilizzo;
- modello di dati, a grafo, come già detto;
- interrogazioni tramite attraversamento del grafo (graph traversal);
- capacità di scalare verticalmente e orizzontalmente, attraverso il progetto Neo4j High Availability (HA)
Neo4j è disponibile in tre modalità:
- Embedded
- Server
- Cluster
Nel primo caso, l’entry point del database è costituito dalla classe EmbeddedGraphDatabase, mentre nel caso del server abbiamo un’interfaccia REST.
Modello di dati
Un grafo di Neo4j è costituito da nodi non tipizzati (senza schema) e archi tipizzati. Entrambe le entità possono avere un numero arbitrario di proprietà. Le proprietà devono avere un nome (stringa) e un valore che può essere:
- di un tipo primitivo;
- stringa;
- un array dei precedenti.
Un esempio
Vediamolo con un esempio. Poniamo di voler modellare un database di un organigramma aziendale semplificato. I nodi sono costituiti dai dipendenti e dai centri di costo, mentre gli archi rappresentano la relazione di superiore gerarchico e di afferenza ad un centro di costo (figura 1). Le proprietà del dipendente sono nome, cognome, data di nascita, etc. Anche le relazioni possono avere proprietà, ad esempio la relazione di superiore gerarchico può contenere la data d’inizio. Essendo i nodi senza schema ne’ tipo possiamo gestire anche dati incompleti o mancanti, per esempio posizioni vacanti nell’organigramma.
Figura 1 – Grafo di un organigramma aziendale.
Proviamo a realizzare questo grafo in Neo4j. Innanzitutto dobbiamo definire le relazioni:
public enum EmployeeRelationship implements RelationshipType {
RIPORTA_A,
AFFERISCE
}
A questo punto, dobbiamo collegarci al database. Se vogliamo usare un database embedded:
GraphDatabaseService graphDb = new EmbeddedGraphDatabase("var/graphdb");
Quando avremo finito, dobbiamo ricordarci di chiudere la connessione:
graphDb.shutdown();
Le operazioni di scrittura sul database devono essere fatte in transazione, altrimenti otteniamo un errore a run-time. Con questo accorgimento, inseriamo i nodi nel database:
Transaction tx = graphDb.beginTx();
try {
// creazione dei centri di costo
Node cc1 = graphDb.createNode();
cc1.setProperty("Nome", "CC1");
Node cc2 = graphDb.createNode();
cc2.setProperty("Nome", "CC2");
Node rossi = graphDb.createNode();
rossi.setProperty("Nome", "Mario");
rossi.setProperty("Cognome", "Rossi");
Node verdi = graphDb.createNode();
verdi.setProperty("Nome", "Giuseppe");
verdi.setProperty("Cognome", "Verdi");
Node bianchi = graphDb.createNode();
bianchi.setProperty("Nome", "Carlo");
bianchi.setProperty("Cognome", "Bianchi");
// Sappiamo che c'è una posizione vacante
// nell'organigramma. Quindi senza nome.
Node posizioneVacante = graphDb.createNode();
// Creiamo le relazioni
rossi.createRelationshipTo(cc1, EmployeeRelationship.AFFERISCE);
verdi.createRelationshipTo(cc1, EmployeeRelationship.AFFERISCE);
verdi.createRelationshipTo(rossi, EmployeeRelationship.RIPORTA_A);
// Bianchi afferisce al secondo centro di costo
// solo dal 2011. Lo possiamo impostare
Relationship bianchiCC2
= bianchi.createRelationshipTo(cc2,
EmployeeRelationship.AFFERISCE);
bianchiCC2.setProperty("anno", 2011);
// Sappiamo che Bianchi riporterà ad
// un manager non ancora designato
bianchi.createRelationshipTo(posizioneVacante, EmployeeRelationship.RIPORTA_A);
// Ma della posizione vacante sappiamo però anche
// i centri di costo e il superiore gerarchico
posizioneVacante.createRelationshipTo(rossi,
EmployeeRelationship.RIPORTA_A);
posizioneVacante.createRelationshipTo(cc2,
EmployeeRelationship.AFFERISCE);
tx.success();
} finally {
tx.finish();
}
Al termine del blocco, nodi e relazioni sono stati inseriti nel database, in modo atomico (o tutto o niente).
Indicizzazione
In realtà questo grafo, così com’è stato inserito non è abbastanza utile; infatti, per andare a cercare un nodo saremmo costretti a scorrere tutti i nodi del grafo o a effettuare un attraversamento (che vedremo più avanti), oppure a memorizzare da qualche altra parte gli ID univoci che Neo4j assegna ai nodi. Ma c’è un modo più semplice: ricorrere agli indici sulle proprietà.
Supponiamo di volerci riservare l’opportunità di ricercare i dipendenti per matricola. In tal caso, non è sufficiente il codice riportato sopra ma è necessario creare un indice. Quindi prima della fine della transazione inseriamo una sezione come questa:
Indexemployees = graphDb.index().forNodes("employees");
employees.add(bianchi, "codice", 100101);
employees.add(rossi, "codice", 100102);
employees.add(verdi, "codice", 100103);
Ciò permetterà di interrogare l’indice, ad esempio, in questo modo:
Node rossi = graphDb.index().forNodes("employees")
.get("codice", 100101).getSingle();
L’indicizzazione può essere estesa a più proprietà e non è univoca, infatti, la funzione get sull’indice restituisce un oggetto che implementa Iterable. Se, ad esempio, avessimo indicizzato anche il cognome, la ricerca ci avrebbe restituito tutti i dipendenti con quel cognome:
Indexemployees = graphDb.index().forNodes("employees");
employees.add(bianchi, "Cognome", "Bianchi");
employees.add(rossi, "Cognome", "Rossi");
employees.add(verdi, "Cognome", "Verdi");
for(Node n : graphDb.index().forNodes("employees").get("Cognome", "Bianchi"))
System.out.println( "Trovato " + n.getProperty("Nome") );
Da notare che, se decidiamo di indicizzare un nodo con una chiave che coincide con una proprietà di quel nodo, siamo noi, ovvero la nostra applicazione, a dover garantire che quell’indice coincida effettivamente col valore della proprietà, perche’ nulla ci vieta, ad esempio, di assegnare una proprietà cognome ad un nodo con un valore diverso dal valore del suo indice cognome.
Attraversamento del grafo
L’interrogazione con gli indici sicuramente è molto utile per le operazioni più comuni, ma spesso vogliamo ricercare anche informazioni in base alle relazioni con altre informazioni. Ad esempio, supponiamo di voler cercare tutti i nodi connessi a un certo centro di costo. Per farlo abbiamo due modi: o navighiamo il grafo a partire dal centro di costo oppure effettuiamo un attraversamento del grafo, ossia lasciamo che sia Neo4j a farlo per noi in modo molto più efficiente e scalabile, ad esempio con la seguente funzione. Lasciamo i commenti direttamente nel codice, per una maggiore comprensione.
void trovaPerCentroDiCosto(Node cc) {
// il metodo traverse crea un Traverser,
// un iteratore che attraversa il grafo
// in un modo preciso
Traverser traverser = cc.traverse(
// facciamo una ricerca Depth-First
Traverser.Order.DEPTH_FIRST,
// ci fermiamo al primo livello di profondità
StopEvaluator.DEPTH_ONE,
// vogliamo tutti i nodi tranne il primo...
ReturnableEvaluator.ALL_BUT_START_NODE,
// ...che abbiano la relazione AFFERISCE
// con il nodo di partenza...
EmployeeRelationship.AFFERISCE,
// ...in entrata (i dipendenti afferiscono
// ai centri di costo, non viceversa)
Direction.INCOMING
);
// A questo punto possiamo iterare
for(Node node : traverser) {
if(node.hasProperty("Cognome"))
System.out.println( node.getProperty("Cognome") );
}
}
Gli overload del metodo traverse permettono di ricercare interi sottografi, ad esempio trovare il nodo x che è collegato tramite la proprietà A ad un nodo y collegato tramite la proprietà B ad un nodo z etc.
Tramite questi operatori è possibile fare inferenza. Ad esempio, poniamo di avere nel database il grafo come risulta dal primo listato; se volessimo accrescere il grafo, aggiungendo una relazione “manager di secondo livello”, che collega un manager con i sottoposti dei suoi sottoposti, potremmo iniziare con una funzione del tipo:
IterableelencoSecondoLivello(final Node manager) {
Traverser trv = manager.traverse(
Traverser.Order.BREADTH_FIRST,
// ci fermiamo ai nodi di secondo livello
new StopEvaluator() {
public boolean isStopNode(TraversalPosition
traversalPosition) {
return traversalPosition.depth() == 2;
}
},
new ReturnableEvaluator() {
public boolean isReturnableNode(TraversalPosition
traversalPosition) {
// vogliamo solo i nodi di secondo livello
if(traversalPosition.depth() != 2)
return false;
// ma non vogliamo i nodi già collegati
// direttamente al manager
for(Relationship rel
: traversalPosition.currentNode()
.getRelationships(
EmployeeRelationship.RIPORTA_A,
Direction.OUTGOING))
{
if(rel.getEndNode() == primo)
return false;
}
return true;
}
},
EmployeeRelationship.RIPORTA_A,
Direction.INCOMING
);
return trv;
}
A questo punto è sufficiente iterare per creare le nuove relazioni:
for(Node manager : managers)
for(Node n : elencoSecondoLivello(manager))
n.createRelationshipTo(manager,
EmployeeRelationship.SECONDO_LIVELLO);
Interrogazione con Gremlin
Gremlin [3] è un linguaggio per l’attraversamento di grafi, sviluppato per Groovy. Quindi esso non è stato scritto specificamente per Neo4j, ma in realtà trova applicazione su tutti i database a grafo che abbiano implementato il modello Blueprints [4].
La sintassi è molto semplice e permette di effettuare anche operazioni di aggregazione. Per esempio, per effettuare l’attraversamento presentato precedentemente nella funzione elencoSecondoLivello, è sufficiente l’espressione (in Groovy):
x = []
manager.outE('RIPORTA_A').inV.aggregate(x).outE('RIPORTA_A').inV.except(x)
È evidente l’espressività di questo linguaggio:
- outE considera le relazioni in uscita (in questo caso di tipo RIPORTA_A)
- inV indica i nodi in arrivo di tali relazioni
- aggregate aggiunge questi nodi alla variabile x
- except toglie dal risultato i nodi presenti in x
Esistono diversi altri costrutti e operatori per cui rimandiamo alla documentazione ufficiale.
Per usarla in Java, una query può essere compilata da una stringa in questo modo:
Pipe secondoLivello = Gremlin.compile("_().outE('RIPORTA_A').inV.outE('RIPORTA_A').inV");
quindi il Pipe può essere applicato al nodo di partenza.
Neo4j Server
Il server, una volta avviato (figura 2), è utilizzabile tramite un qualsiasi client REST, come cURL [2].
Figura 2 – Neo4j Server.
Un’interfaccia web (figura 3), permette di amministrare il server, di navigare il grafo e di modificarlo.
Figura 3 – interfaccia di amministrazione.
Neo4j High Availability
Questo progetto [5] si propone lo scopo di realizzare un server tollerante agli errori e scalabile orizzontalmente. Non ci dilungheremo sul come configurare il cluster perche’ la documentazione ufficiale propone una guida passo passo sufficientemente esaustiva. Il coordinamento del cluster può essere effettuato con Zookeeper [6], un server di informazioni di configurazione e sincronizzazione centralizzato).
Fondamentalmente, l’architettura è di tipo master-slave con un insieme di slave che eleggono un unico master. Tutti i nodi accettano sia operazioni in lettura sia in scrittura ma la sincronizzazione dei dati da master a slave avviene in modo asincrono (quindi in teoria, la consistenza è rilassata in questo caso, infatti una lettura che segue una scrittura potrebbe non essere aggiornata: vale il teorema CAP).
Figura 4 – Neo4j HA.
Conclusioni
Abbiamo dato una rapida introduzione delle potenzialità di questo database, a questo punto è facile immaginare il principale contesto d’applicazione: sicuramente domini applicativi particolarmente complessi e che devono essere anche flessibili, con possibilità di affrontare incompletezza d’informazione. Scenario dove un RDBMS può mostrare forti limiti, ma nello stesso tempo dove è necessario garantire transazionalità e proprietà ACIDe: un contesto, potremmo dire, quasi ortogonale a quello tipico di MongoDB.
Per ulteriori informazioni rimandiamo alla documentazione sul sito ufficiale [1], ricca di esempi. Jim Webber, Chief Scientist del progetto, quest’anno ha pubblicato sul suo blog personale [7] una serie di post su questioni inerenti in generale la scalabilità di Neo4j e le difficoltà relative allo sharding dei database a grafo.
Un’ultima nota, gli interessati al Semantic Web possono utilizzare Neo4j anche come database di tuple RDF [8], interrogabile con query SPARQL [9] e [10].
Riferimenti
[1] Neo4j
[2] cURL
[3] Gremlin
[4] Blueprints
http://github.com/tinkerpop/blueprints/wiki/
[5] High Availability Cluster
http://wiki.neo4j.org/content/High_Availability_Cluster
[6] Apache Zookeeper
[7] World Wide Webber
[8] W3C: Resource Description Framework
[9] W3C: SPARQL Query Language for RDF
http://www.w3.org/TR/rdf-sparql-query/
[10] SPARQL Engine for Java
http://sparql.sourceforge.net/
Onofrio Panzarino, ingegnere elettronico, lavora ad Ancona come software architect, per Wolters Kluwer Italia. Sviluppatore con esperienza in vari linguaggi e piattaforme, soprattutto web-oriented, è molto interessato a soluzioni scalabili e a linguaggi di programmazione funzionali. È speaker in JUG Marche su argomenti correlati a Scala e database NoSQL.