Da Big Data ai Graph Database

Scuola Politecnica e delle Scienze di Base
Corso di Laurea in Ingegneria Informatica
Elaborato finale in Basi di Dati
Da Big Data ai Graph Database
Anno Accademico 2014/2015
Candidato:
Luigi Carbone
matr. N46000176
A mia madre,
che trovi sempre
la forza di combattere
contro quel male che
l’affligge.
Indice
Indice ............................................................................................................................................ III
Introduzione .................................................................................................................................... 4
Capitolo 1: Big Data: un universo in espansione.............................................................................. 5
1.1 Caratteristiche dei Big Data .............................................................................................. 6
1.2 Come gestire i Big Data .................................................................................................... 7
Capitolo 2: Database NoSQL .......................................................................................................... 8
2.1 Classificazione .................................................................................................................... 10
2.1.1 Key-Value store................................................................................................................ 10
2.1.2 Document-oriented ........................................................................................................... 11
2.1.3 Column-oriented DBMS ................................................................................................... 11
2.1.4 Graph Database ................................................................................................................ 12
2.2 Vantaggi e svantaggi dei Database NoSQL.......................................................................... 12
Capitolo 3: Graph Database........................................................................................................... 14
3.1 Elementi di teoria dei grafi .................................................................................................. 14
3.2 I grafi nel mondo reale......................................................................................................... 16
3.2.1 Una vista ad alto livello dello spazio dei grafi ................................................................... 17
3.3 La potenza dei Graph Database............................................................................................ 18
3.3.1 Performance ..................................................................................................................... 19
3.3.2 Flessibilità ........................................................................................................................ 20
3.3.3 Agilità .............................................................................................................................. 20
3.4 Principali GraphDB ............................................................................................................. 21
3.4.1 Neo4j ............................................................................................................................... 21
3.4.2 InfiniteGraph .................................................................................................................... 22
3.4.3 HyperGraphDB ................................................................................................................ 23
3.4.4 OrientDB .......................................................................................................................... 23
3.4.5 Titan ................................................................................................................................. 24
Capitolo 4: Titan Database ............................................................................................................ 25
4.1 Benefici di Titan .................................................................................................................. 26
4.1.1 Benefici di Titan con Cassandra e HBase .......................................................................... 26
4.2 Titan e il Teorema CAP ....................................................................................................... 27
4.3 TinkerPop e Gremlin Shell .................................................................................................. 28
4.4 Sperimentazione con Titan e Gremlin Shell ......................................................................... 28
Conclusioni ................................................................................................................................... 35
Bibliografia ................................................................................................................................... 36
Ringraziamenti.............................................................................................................................. 37
Introduzione
L'evoluzione tecnologica ha portato, nel corso degli ultimi anni, ad un notevole incremento
di dispositivi in grado di automatizzare numerose operazioni, sia nel mondo produttivo, sia
nella vita quotidiana delle persone in generale. Tali dispositivi hanno generato un'enorme
quantità di dati, che si prevede in crescita esponenziale nel prossimo futuro. Anche il Web
2.0, da diversi anni, è una fonte sempre crescente di dati. Ciò è dovuto principalmente alla
produzione dei dati da parte degli utenti stessi come, ad esempio, i contenuti digitali, quali
video, foto, post, che circolano sui social network. È a causa di questa esplosione del
quantitativo di dati che negli ultimi tempi si è diffuso il termine Big Data, il quale si
riferisce all'enorme mole di dati prodotta e alla loro variabilità. Ciò ha aperto la strada verso
la ricerca di nuove tecnologie, in quanto le risorse necessarie a gestire un simile volume di
contenuti vanno ben oltre quelle offerte dai tradizionali sistemi RDBMS. Nascono così i
cosiddetti sistemi NoSQL, che rinunciando alla rigidità degli schemi tipici dei database
relazionali, offrono dei metodi più adeguati a rappresentare la dinamicità dei Big Data.
Punti chiave di questo elaborato sono proprio tali strumenti. In particolare, dopo una breve
panoramica sui Big Data e sui database NoSQL in generale, si analizzerà, in maniera più
approfondita, una particolare tipologia di database non relazionale, i cosiddetti Graph
Database, dopodiché, si passerà ad un caso particolare di sperimentazione relativo a Titan,
un database a grafo di recente sviluppo e diffusione, in grado di affrontare in maniera
efficace ed efficiente l’evolversi dei dati.
4
Capitolo 1: Big Data: un universo in espansione
Oggigiorno viviamo nell’epoca dei Big Data, in cui i volumi di dati di cui abbiamo bisogno
abitualmente per svolgere un lavoro, hanno superato le capacità di memorizzazione e di
gestione che un singolo sistema di elaborazione, di norma, è in grado di fornire.
Inizialmente, l’espressione “Big Data” è nata proprio con l’intento di indicare set di dati la
cui dimensione non era gestibile con gli strumenti convenzionalmente utilizzati.
Attualmente, però, l’espressione ha iniziato ad assumere un significato diverso, riferendosi
al crescente volume di informazioni presenti all'interno di un'azienda e alle sfide e alle
opportunità rappresentate da tale crescita. Risulta alquanto difficile indicare una dimensione
di riferimento, ma orientativamente la mole di dati è dell’ordine degli Zettabyte, ovvero
miliardi di Terabyte. Tale dimensione è in perenne aumento a causa della crescita dei
dataset e alla continua evoluzione delle macchine in termini di prestazioni. Pertanto, una
delle gradi sfide dell’informatica, nei prossimi anni, sarà la necessità di espandere le
5
architetture per la gestione dei dati. Risulta evidente, di fronte a cifre del genere, come sia
necessario l’impiego di una potenza di calcolo parallelo, con strumenti dedicati eseguiti su
decine, centinaia o anche migliaia di server.
Gli obiettivi dei Big Data sono molteplici: previsioni di varia natura, gestione dei dati
provenienti dai sensori di complessi apparati, ricerca in tempo reale di tentativi di frode,
ottimizzazione di call center, analisi competitiva sul Web, analisi dei social media e, più in
generale, deduzione ed estrapolazione di informazioni da grossi quantitativi di dati. Inoltre,
come già accennato, l'utilizzo ormai diffuso di qualsiasi dispositivo elettronico (computer,
tablet, smartphone) genera una massa di informazioni che possono andare ad alimentare
basi di dati di grandi dimensioni. Per evidenziare questo fenomeno si è ricorso, talvolta,
all'espressione “i dati siamo noi1”, dando una visione interessante di cosa siano i Big Data.
1.1 Caratteristiche dei Big Data
Ci si può chiedere se per parlare di Big Data sia sufficiente avere a che fare con dataset di
grosse dimensioni. Secondo molti analisti, le caratteristiche fondamentali di un Big Data
sono tre: volume, varietà e velocità.
L’aspetto “volume” è probabilmente il più ovvio, in quanto, come già accennato, ci
troviamo di fronte a moli di dati che partono dai terabyte e i petabyte per entrare nel mondo
degli zettabyte, e i volumi sono in continuo aumento.
Per quanto concerne l'aspetto “varietà”, si tratta di qualcosa di nuovo, che consiste
nell'esplorazione, oltre che delle informazioni tradizionali, anche di dati non strutturati,
ovvero di dati conservati senza alcuno schema. Tipici esempi possono essere i file
contenenti testi a carattere narrativo, prodotti per mezzo di uno dei più diffusi software di
editing testuale, o file multimediali, come immagini, audio e video. Se si pensa ad un post
su Facebook, un tweet o un blog, essi possono essere in un formato strutturato (JSON), ma
il vero valore si trova nella parte dei dati non strutturati. Risulta, pertanto, evidente
l’esigenza di ricorrere a strumenti diversi dai tradizionali database, che richiedono coerenza
1
Alexander Jaimes, ricercatore presso Yahoo Research.
6
e integrità. Varietà può essere intesa, oltre come eterogeneità di formati, anche come
molteplicità di fonti. Alcuni dati, infatti, possono essere generati automaticamente da
macchine (sensori, log dei server, log dei router), mentre altri sono generati dagli utenti
(user-generated content2).
Infine, l’ultimo aspetto che caratterizza i Big Data è la “velocità”, intesa sia come rapidità
con cui vengono generati i dati, sia come bisogno di grandi prestazioni computazionali per
elaborare gli stessi, al fine di fornire risposte in tempi utili.
I flussi di dati possono essere anche altamente inconsistenti, con picchi periodici. Che siano
essi eventi quotidiani, stagionali o attivati da eventi, i picchi di dati possono essere difficili
da gestire, soprattutto con la diffusione dei social media.
Quando si ha a che fare con enormi volumi di dati, essi derivano generalmente da molteplici
fonti e rappresenta una vera impresa collegarli ed elaborarli tra i vari sistemi. In ogni modo,
è necessario connettere e correlare le relazioni, le gerarchie e i collegamenti a dati multipli o
i dati possono finire fuori controllo. Oggigiorno, le tecnologie non solo offrono strumenti
per manipolare tali raccolte, ma possiedono anche la capacità di capire e sfruttare tutto il
loro valore, che aiuta le organizzazioni a funzionare in modo più efficiente e redditizio.
1.2 Come gestire i Big Data
Nel corso del tempo, si è assistito ad una crescita esponenziale dei dati e con essa ci si è
posto il problema di come gestirli e memorizzarli. Inizialmente, si è cercato di capire come
poter migliorare i sistemi RDBMS, ma le caratteristiche di queste tipologie di dati hanno
reso difficile il loro trattamento con i classici database relazionali. Ciò ha aperto la strada
verso la ricerca di nuovi modelli di elaborazione che, oltre a mostrarsi più adeguati, hanno
permesso una netta riduzione dei costi. I nuovi sistemi sono in grado di archiviare, elaborare
e combinare i dati in maniera più veloce, generando quindi un complessivo aumento di
efficienza. I modelli adottati sono molteplici e generalmente conosciuti come Database
NoSQL.
2
Letteralemente “contenuto generato dagli utenti”, con tale termine ci si riferisce a ogni tipo di materiale disponibile
sul web prodotto da utenti invece che da società specializzate.
7
Capitolo 2: Database NoSQL
Gli RDBMS, ampiamente utilizzati per una grande varietà di applicazioni, presentano
alcuni problemi quando la mole dei dati cresce oltre certi limiti. La scalabilità e i costi per
realizzarla sono soltanto una parte degli svantaggi; molto spesso, infatti, quando ci si trova
di fronte alla gestione di Big Data, anche la variabilità, ovvero la mancanza di una struttura
fissa, rappresenta una problematica di rilievo. Ciò che però ha dato una spinta allo sviluppo
di database NoSQL è quella che, prendendo a prestito il termine dall'elettronica, è
comunemente chiamata impedance mismatch, che denota la mancata corrispondenza tra
modello object-oriented e relazionale.
Negli anni Novanta, quando la programmazione ad oggetti è diventata predominante, si è
assistito alla nascita di database ad oggetti, in grado di archiviare i dati nella stessa forma
che essi hanno in memoria. Tuttavia, questi database non hanno avuto un grande successo,
anche grazie alla comparsa di framework in grado di realizzare la mappatura tra oggetti e
tabelle. In seguito, negli anni Duemila, si è assistito a un progressivo affermarsi di database
che non implementavano la teoria relazionale, nati per affrontare le problematiche di
scalabilità a costi contenuti e di gestione di dati non strutturati.
Il termine NoSQL, il cui significato è Not Only Sql, fa riferimento a tutti quei modelli che
non utilizzano, o che utilizzano in maniera non esclusiva, il modello relazionale per la
memorizzazione delle informazioni. Si riferisce, dunque, a quei database che vanno oltre
l’utilizzo di SQL, ossia che possono sfruttare anche SQL, ma presentano una struttura più
8
complessa.
I NoSQL DBMS sono contraddistinti dal fatto che non utilizzano un sistema transazionale
ACID, il quale garantisce che ogni transazione soddisfi le seguenti proprietà:
-
Atomicity: una transazione è un’unità di elaborazione atomica, indivisibile. Ciò
significa che dovrà essere eseguita totalmente oppure per niente, senza scinderla in parti più
piccole.
-
Consistency: quando viene lanciata, una transazione trova il database in uno stato
consistente e al suo completamento il database dovrà ancora godere di questa proprietà.
-
Isolation: le transazioni devono essere eseguite in modo indipendente l’una dalle
altre. Ciò vuol dire che gli effetti parziali di transazioni incomplete non devono essere
visibili alle altre transazioni.
-
Durability: gli effetti di una transazione che ha terminato correttamente la sua
esecuzione devono essere persistenti nel tempo.
Una pietra miliare anche dei Database NoSQL, invece, è il Teorema di Brewer, più noto
come Teorema di CAP, il quale afferma che non è possibile per un sistema informatico
distribuito fornire simultaneamente tutte e tre le seguenti garanzie:
-
Coerenza (Consistency): tutti i nodi vedono gli stessi dati nello stesso momento;
-
Disponibilità (Availability): la garanzia che ogni richiesta riceva una risposta su ciò
che sia riuscito o fallito;
-
Tolleranza di partizione (Partition tolerance): il sistema continua a funzionare
nonostante arbitrarie perdite di messaggi.
Nel caso di un database distribuito è possibile soddisfare al massimo due delle proprietà
sopraelencate. Lo stesso autore del Teorema CAP, Eric Brewer, ha introdotto anche le
proprietà BASE, descrivendo le caratteristiche che un sistema deve garantire sottostando al
teorema sopra enunciato. Le proprietà sono le seguenti:
-
Basically Available: il sistema deve garantire la disponibilità delle informazioni;
-
Soft State: il sistema può cambiare stato nel tempo, anche in assenza di letture o
scritture;
-
Eventual Consistency: un sistema può diventare consistente nel tempo, anche senza
9
scritture, grazie a dei sistemi di recupero della consistenza.
Inoltre, spesso questi tipi di DBMS sono schemaless, ovvero non possiedono uno schema
fisso a cui devono attenersi, evitando così le operazioni di JOIN, e puntano a scalare in
modo orizzontalmente anziché verticale.
2.1 Classificazione
Le implementazioni di NoSQL possono essere classificate in base al tipo di modello dei dati
adottato. Le categorie più diffuse sono quelle riportare di seguito.
2.1.1 Key-Value store
I database Key-Value Store si basano sul concetto di associative array, cioè una struttura
in grado di contenere un insieme di coppie chiave/valore. In generale, la chiave è un valore
univoco con il quale è possibile identificare e ricercare i valori nel database. Gli associative
array sono solitamente implementati attraverso una hash table. Le operazioni consentite da
un associative array sono:
-
Add, per l'aggiunta di un elemento all'array;
-
Remove, per l'eliminazione di un elemento;
10
-
Modify, operazione con cui si cambia il valore associato a una certa chiave;
-
Find, operazione con cui si ricerca un valore nell'array tramite la chiave.
Tali operazione sono le stesse che i database appartenenti alla categoria dei key/values store
consentono sui dati. Si tratta dunque di operazioni non complesse, ma con la caratteristica
di garantire tempi di esecuzione costanti.
I database appartenenti a questa categoria presentano un modello dati molto semplice, ma
sono piuttosto sofisticati per quanto riguarda altri aspetti, come per esempio la scalabilità
orizzontale, cioè la capacità di far fronte alla crescita del volume dei dati aggiungendo nodi
al cluster.
2.1.2 Document-oriented
I database di tipo Document-Oriented sono strumenti per la gestione di dati semistrutturati. Rappresentano l'evoluzione dei Key/Values Store, avendo a che fare con insiemi
di coppie chiave/valore, spesso organizzati in formato JSON o XML. Questi database
forniscono una struttura, anche se semplice, alle coppie chiave/valore, che però non pone
vincoli allo schema dei documenti, garantendo una grande flessibilità. Gli oggetti dei
linguaggi di programmazione object-oriented possono essere serializzati in un documento,
eliminando il problema dell'impedance mismatch.
L'utilizzo di questo tipo di database è piuttosto conveniente in situazioni in cui i dati hanno
una struttura dinamica. Poiché, come affermato in precedenza, uno degli aspetti dei Big
Data è proprio la variabilità, tale caratteristica è gestita molto bene dai database documentoriented, che quindi si mostrano particolarmente adatti all'immagazzinamento di tipologie
di dati complessi ed eterogenei.
2.1.3 Column-oriented DBMS
Un Column-oriented DBMS è un sistema di gestione di basi di dati che memorizza i dati
delle tabelle come sezioni di colonne di dati piuttosto che righe di dati. Memorizzare
consecutivamente i valori contenuti in ogni colonna consente, per query che coinvolgono
11
pochi attributi selezionati su un gran numero di record, di ottenere tempi di risposta
migliori, in quanto si riduce anche di diversi ordini di grandezza il numero di accessi
necessari alle memorie di massa; è inoltre possibile applicare efficienti tecniche di
compressione dei dati, in quanto ogni colonna è ovviamente costituita da un unico tipo di
dati (numerico, alfanumerico, data, ecc.), riducendo lo spazio occupato ricorrendo a
tecniche di vario genere.
I database che appartengono a questa categoria introducono il concetto di column-family.
Si tratta, in pratica, di un contenitore di colonne che deve essere presente nello schema, ma
le colonne che la costituiscono non devono essere definite a priori. Ogni column-family è
scritta su un file diverso. L’aggiunta di una colonna alla column-family, così come
l'eliminazione, non comporta una ridefinizione dello schema e quindi è trasparente e
immediata.
2.1.4 Graph Database
Un Graph Database memorizza le informazioni attraverso strutture a grafo. Gli elementi
tipici di questo modello sono quindi nodi e archi, ovvero gli stessi di un tipico grafo,
mentre un'interessante operazione è l'attraversamento, che permette di esaminare i nodi e
gli archi in modo sistematico.
Per una trattazione più esaustiva si rimanda al capitolo successivo.
2.2 Vantaggi e svantaggi dei Database NoSQL
I NoSQL database presentano una serie di vantaggi e di svantaggi rispetto ai tradizionali
database relazionali. Di seguito ne vengono elencati alcuni.
Vantaggi:
-
Dato che un elemento contiene tutte le informazioni necessarie non serve usare i
dispendiosi, in termini di performance, JOIN come invece avviene per i database
relazionali.
-
Essendo i dati privi di schema, le applicazioni si possono arricchire di nuovi dati e
12
informazioni senza rischi per l'integrità dei dati.
-
L’aggregazione dei dati e l’assenza di uno schema definito a priori offre l’opportunità
di scalare orizzontalmente i database NoSQL senza difficoltà e senza rischi operativi.
Svantaggi:
-
La mancanza di uno standard universale, come SQL, è un primo difetto di questi
modelli. Ogni database ha infatti le proprie API e il proprio metodo di storing e di
accesso ai dati. Pertanto, risulta palese che se lo sviluppo del database sul quale si basa
un applicativo venisse interrotto, il passaggio ad un altro database non sarebbe
sicuramente una cosa immediata, ma richiederebbe alcuni cambi più o meno radicali
da apportare all’applicativo stesso.
-
Non essendo presente il concetto di transazione, spetta al programmatore il compito di
garantire la coerenza dei dati.
13
Capitolo 3: Graph Database
Una base di dati a grafo, o database a grafo, usa nodi e archi per rappresentare e
archiviare le informazioni. La forza di questo tipo di database è di gestire dati fortemente
interconnessi, proprietà che permette l'operazione di attraversamento (graph traversal) che
stabilisce come passare da un nodo all'altro utilizzando le relazioni tra di essi.
Questi database sono spesso più veloci di quelli relazionali nell'associazione di insiemi di
dati e mappano in maniera più diretta le strutture di applicazioni orientate agli oggetti.
Dipendono meno da rigidi schemi, come quello relazionale, e sono molto più adeguati per
gestire dati mutevoli con schemi evolutivi. Sono adatti a scalare orizzontalmente e non
richiedono le tipiche e onerose operazioni di unione (JOIN).
Un database a grafo può essere visto anche come caso particolare di database orientato al
documento, in cui i documenti rappresentano sia i nodi che le relazioni che interconnettono
i nodi.
3.1 Elementi di teoria dei grafi
Nel parlare di graph database è inevitabile fare riferimento alla teoria dei grafi, ovvero
quella branca della matematica che si occupa dello studio delle proprietà combinatorie,
topologiche e probabilistiche dei grafi.
Un grafo è un insieme di elementi, detti nodi o vertici, che possono essere collegati fra loro
14
=
da linee chiamate archi o lati. Più formalmente, si dice grafo una coppia ordinata
( , ) di insiemi, con
insieme dei nodi ed
insieme degli archi, tali che gli elementi di
siano coppie di elementi di . Due vertici ,
estremi dell'arco; l'arco
connessi da un arco, prendono il nome di
viene anche identificato con la coppia formata dai suoi estremi
( , ).
Un arco che ha due estremi coincidenti si dice cappio, mentre più archi che connettono gli
stessi due estremi danno origine ad un multiarco. Un grafo sprovvisto di cappi e di
multiarchi si dice grafo semplice. In caso contrario si parla di multigrafo. Un multigrafo si
dice finito se entrambi gli insiemi
numero di archi in
di cui
e
lo sono. Il grado (o valenza) di un vertice
è il
è un estremo. Un grafo è regolare se i vertici hanno tutti lo
stesso grado. Un vertice può esistere in un grafo e non appartenere a un arco, in tal caso si
parla di vertice isolato.
Un grafo orientato
(o digrafo, grafo diretto) è un insieme
dei vertici di
è l'insieme degli archi orientati di
e
= ( , ), dove
è l'insieme
. Un arco orientato è un arco
caratterizzato da una direzione. In particolare, è composto da una testa (rappresentata
solitamente dalla punta di una freccia), che raggiunge un vertice in entrata, e una coda, che
lo lascia in uscita. Un grafo non orientato
è un insieme di vertici e archi dove la
connessione i - j ha lo stesso significato della connessione j - i. Un grafo semplice non
contiene archi orientati.
Dati due vertici ,
di un grafo, si dice che
domina
se
è adiacente a tutti i vertici
adiacenti a . Un vertice adiacente ad ogni altro vertice del grafo si dice universale. Un
cono è un grafo con un unico vertice universale.
Un percorso di lunghezza
in
è dato da una sequenza di vertici
,
,…,
(non
necessariamente tutti distinti) e da una sequenza di archi che li collegano
( ,
), ( ,
), … , (
,
). I vertici
e
si dicono estremi del percorso. Un
percorso con i lati a due a due distinti tra loro prende il nome di cammino. Un cammino
chiuso (
=
) si chiama circuito o ciclo.
Infine, dato un grafo
cammino con estremi
= ( , ), due vertici
e .
15
,
∈
si dicono connessi se esiste un
3.2 I grafi nel mondo reale
Un grafo è una struttura espressiva e multiuso che consente di modellare ogni genere di
scenario, come la costruzione di un razzo spaziale, un sistema di strade, le catene di
distribuzione o la produzione di prodotti alimentari, e altro ancora.
Ad esempio, i dati di Twitter vengono facilmente rappresentati come un grafo. In figura
possiamo vedere una piccola rete di utenti. Le relazioni qui sono la chiave per stabilire il
contesto semantico, vale a dire che Billy segue Harry, il quale, a sua volta, segue Billy. Allo
stesso modo, anche Ruth e Harry si seguono a vicenda, mentre Ruth segue Billy, ma non il
viceversa.
Naturalmente, un vero grafo di Twitter è centinaia di milioni di volte più grande di quello
dell'esempio in figura ma, grossomodo, si basa sugli stessi principi. Nella figura successiva
troviamo una estensione del precedente grafo, dove sono inclusi i messaggi pubblicati da
Ruth.
Sebbene semplice, la figura mostra la potenza espressiva del modello a grafo. È immediato
vedere che Ruth ha pubblicato una serie di messaggi. Il messaggio più recente può essere
trovato seguendo una relazione indicata come CURRENT; le relazioni PREVIOUS poi
creano una linea temporale dei post.
16
3.2.1 Una vista ad alto livello dello spazio dei grafi
Negli ultimi anni sono entrati in scena numerosi progetti e prodotti per la gestione,
l'elaborazione e l'analisi dei grafi. Il gran numero di tecnologie che si stanno sviluppando
rende difficile, anche per gli esperti del settore, tenere traccia di questi strumenti e come
17
essi si differenziano. Volendo provare a fare una classificazione, al livello di astrazione più
alto, possiamo dividere lo spazio dei grafi in due parti:
-
Graph Database: tecnologie utilizzate per la gestione di applicazioni orientate alle
transazioni, generalmente accedute in tempo reale; esse sono l’equivalente dei
database OLTP (On Line Transaction Processing) nel modello relazionale.
-
Motori di calcolo per grafi: tecnologie utilizzate per l'analisi dei grafi non in linea,
tipicamente adibite a trattare grossi quantitativi di dati; esse possono rientrare nella
stessa categoria delle tecnologie per l’analisi di enormi moli di dati, come data mining
e OLAP (On Line Analytical Processing).
Nel presente elaborato ci focalizzeremo principalmente sulla prima tipologia.
3.3 La potenza dei Graph Database
Un graph database è un sistema di gestione di basi di dai in linea con i metodi Create,
Read, Update e Delete (CRUD)3 che mostra un modello di dati a grafo. I database a grafo
sono generalmente costruiti per essere utilizzati con i sistemi transazionali (OLTP) e, di
conseguenza, ottimizzati nelle prestazioni per questo genere di operazioni.
Alcuni database a grafo utilizzano un sistema di memorizzazione nativo che è progettato e
ottimizzato per la memorizzazione e la gestione dei grafi. Non tutte le tecnologie, però,
usano un sistema di archiviazione nativo. Alcuni serializzano i dati del grafo in un database
relazionale, orientato agli oggetti o qualche altro generico modello di dati. La figura
riportata di seguito mostra una panoramica di alcuni database a grafo presenti sul mercato,
basati sui loro modelli di archiviazione e di elaborazione.
Le relazioni qui sono proprietà fondamentali, contrariamente ad altri sistemi di gestione di
basi di dati, che richiedono di dedurre le connessioni tra le entità usando artificiose
proprietà come la chiave esterna. Assemblando le semplici astrazioni di nodi e relazioni in
una struttura connessa, un graph database consente di costruire modelli arbitrariamente
sofisticati che mappano minuziosamente un problema di un dominio specifico. I modelli
3
Rappresentano le quattro funzioni di base per la memorizzazione persistente.
18
risultanti sono più semplici e allo stesso tempo molto più espressivi di quelli prodotti
usando i tradizionali database relazionali e gli altri database NoSQL.
Attualmente, i più diffusi modelli di riferimento per l'implementazione dei database a grafo
sono due: il property graph model e il resource description framework (RDF). Il primo fa
riferimento principalmente al progetto Tinkerpop, mentre il secondo è il modello di
riferimento del Web semantico4.
3.3.1 Performance
Uno dei motivi per cui si può propendere alla scelta di un database a grafo, è l'evidente
incremento di prestazioni nel trattare dati strettamente connessi rispetto ai database
relazionali e altri sistemi di archiviazione NoSQL. A differenza dei database relazionali,
dove l'uso intensivo di JOIN produce un peggioramento delle prestazioni al crescere del
4
Termine con cui si intende la trasformazione del World Wide Web in un ambiente dove i documenti pubblicati (pagine
HTML, file, immagini, e così via) sono associati ad informazioni e dati (metadati) che ne specificano il contesto
semantico in un formato adatto all'interrogazione e l'interpretazione e, più in generale, all'elaborazione automatica.
19
dataset, con un database a grafo le prestazioni tendono a rimanere relativamente costanti,
anche se il dataset cresce notevolmente. Questo perché le query sono localizzate a una
porzione del grafo. Come risultato, il tempo di esecuzione per ogni query è proporzionale
solo alla dimensione della parte del grafo attraversata per soddisfare la richiesta, piuttosto
che alla dimensione complessiva del grafo.
3.3.2 Flessibilità
I grafi sono per loro natura additivi, consentendo quindi di aggiungere nuovi tipi di
relazioni, nuovi nodi e nuovi sotto-grafi a una preesistente struttura, senza compromettere le
i dati esistenti e le funzionalità delle applicazioni. Questi aspetti hanno generalmente
implicazioni positive per la produttività degli sviluppatori e i rischi di progetto. Grazie alla
flessibilità del modello a grafo, non occorre modellare in anticipo un dominio in dettaglio
(una pratica spesso ritenuta fondamentale, ma sconsiderata di fronte alle mutevoli esigenze
di business). La natura additiva dei grafi comporta anche una minor esigenza di eseguire
migrazioni, riducendo, in tal modo, il carico di manutenzione e di rischio.
3.3.3 Agilità
I moderni database a grafo forniscono strumenti per eseguire lo sviluppo e la manutenzione
dei sistemi in maniera agile. In particolare, grazie allo schema libero del modello dei dati,
insieme alla natura testabile delle interfacce di programmazione (API) e al linguaggio di
interrogazione dei graph database, essi consentono di sviluppare un'applicazione in maniera
controllata. Allo stesso tempo, proprio perché sono a schema libero, i graph database non
dispongono di quel genere di meccanismi di gestione dei dati tipici dei modelli con un
rigido schema familiari al mondo relazionale. Questo non rappresenta un rischio, bensì
produce un genere di controllo di gran lunga più visibile e perseguibile. Lo sviluppo di
graph database, infine, si allinea bene con le odierne tecniche di sviluppo agile del software,
potendo facilmente evolversi nel tempo in maniera analoga ai sistemi software.
20
3.4 Principali GraphDB
Di seguito si passeranno in rassegna alcuni dei database a grafo attualmente più diffusi. Si
elencheranno alcune delle proprietà che maggiormente li caratterizzano, con particolare
riferimento a Titan, che sarà trattato più approfonditamente nel capitolo successivo.
3.4.1 Neo4j
Neo4j è un database a grafo open source, transazionale (garantisce le proprietà ACID) e
sviluppato interamente in Java. Viene integrato nelle applicazioni permettendone il
funzionamento stand alone5. Rispetto ai tradizionali RDBMS, offre un modello di dati
senza schema, molto flessibile ed espressivo, che permette di maneggiare facilmente
l’incompletezza e facilitare l’inferenza con un’API object oriented. Neo4j è disponibile in
tre modalità: Embedded, Server e Cluster.
Un grafo di Neo4j è costituito da nodi non tipizzati 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, una stringa o un array. Spesso le
applicazioni utilizzano i due linguaggi supportati per le query, ossia Gremlin e Cypher.
Ogni nodo contiene un set di proprietà espresse come “chiave:valore”. Una relazione
connette due nodi, può avere a sua volta delle proprietà e può essere unidirezionale o
bidirezionale.
Alla base delle sue alte prestazioni di attraversamento, d’interrogazione e di scrittura c’è la
5
Proprietà di un oggetto o di un software capace di funzionare da solo o in maniera indipendente da altri oggetti o
software, con cui potrebbe altrimenti interagire.
21
index-free adjancency, ed è uno degli aspetti chiave della sua architettura. Si tratta di una
lista (o tabella), ove ogni suo elemento è composto da un nodo del grafo e dai puntatori ai
nodi connessi ad esso.
Neo4j salva i dati in una serie di store file, contenuti all’interno di un’unica cartella.
Ognuno di questi file contiene al suo interno le informazioni relative ad una singola parte
del grafo. Questa separazione della struttura del grafo facilita il suo attraversamento.
Il linguaggio di interrogazione nativo di Neo4j è Cypher. Si tratta di un linguaggio grafico,
ovvero si basa sulla riproduzione grafica del sotto-grafo che si vuole estrarre . Inoltre esso
consente le classiche operazioni, come creare, modificare, eliminare e interrogare i dati del
database.
3.4.2 InfiniteGraph
Rilasciato per la prima volta al pubblico nel 2010, InfiniteGraph è un database a grafo,
distribuito e implementato in Java. Gli sviluppatori utilizzano InfiniteGraph per trovare
relazioni utili e spesso nascoste in grossi insiemi di dati altamente connessi. Esso è
multipiattaforma, scalabile e progettato per trattare un alto throughput dei dati.
InfiniteGraph è adattato per le applicazioni e i servizi specificamente basati su grafi. Viene
adottato in molteplici campi, come pubblica amministrazione, assistenza sanitaria, finanza
applicazioni di social networking, e altro ancora.
Di seguito sono elencate alcune caratteristiche peculiari.
-
Utilizza multigrafi diretti; un arco è un'entità di rilievo con un'identità indipendente dai
vertici che connette.
-
I metodi di interrogazione utilizzano API per l'attraversamento e la navigazione
22
attraverso i grafi.
-
Le transazioni supportano le proprietà ACID.
-
Supporto al multithreading.
-
Supporto di query in parallelo.
3.4.3 HyperGraphDB
HyperGraphDB è un sistema di archiviazione dati estendibile, multiuso, portabile, opensource e integrabile. È un database a grafo progettato specificamente per progetti di
Intelligenza Artificiale e Web Semantico. Può anche essere utilizzato come database
orientato agli oggetti integrato per ogni dimensione dei dati. HyperGraphDB, come si può
dedurre dal nome, è in primo luogo, un database destinato alla memorizzazione di ipergrafi.
Ciò vuol dire che è incentrato su una rappresentazione più generalizzata dei grafi, in cui un
lato può puntare a più nodi.
Anche se ricade nella famiglia generale delle basi di dati a grafo, è difficile classificarlo
come altri database, in quanto molti dei suoi progetti sono finalizzati alla fornitura dei
mezzi per gestire informazioni multi-strutturare con arbitrari livelli di complessità.
3.4.4 OrientDB
OrientDB si caratterizza per le dimensioni dei database gestibili e per la velocità di
lavorazione dei dati. Infatti, riesce a caricare circa un milione di record in cinque secondi o
anche meno, nonostante il programma sia scritto interamente in Java, mentre la mole di dati
che riesce a gestire, su sistemi distribuiti, è stimata intorno ai 20 milioni di zettabyte.
23
OrientDB riunisce in un unico database molte funzionalità:
-
diverse modalità di archiviazione: document, graph (con supporto allo stack
Tinkerpop), object, key/values;
-
essendo scritto in Java è multipiattaforma;
-
funzionamento embedded, in memory, client/server;
-
rispetto delle proprietà ACID;
-
supporto nativo a JSON e REST.
3.4.5 Titan
Titan è un database a grafo scalabile e ottimizzato per archiviare e interrogare grafi
contenenti centinaia di miliardi di vertici e archi distribuiti su cluster. Si tratta di un
database transazionale, in grado di supportare migliaia di utenti contemporaneamente,
eseguendo complessi attraversamenti dei grafi in tempo reale.
Nel capitolo successivo verranno presentate le caratteristiche di questo database, con alcuni
esempi pratici di utilizzo.
24
Capitolo 4: Titan Database
Titan è progettato per supportare l'elaborazione di grafi talmente grandi da richiedere
capacità di memorizzazione e computazionali molto superiori rispetto a quelle che una
singola macchina è in grado di fornire.
In Titan uno schema può evolversi nel tempo senza interrompere, né compromettere, le
normali operazioni del database. L'estensione di tale schema non rallenta le risposte alle
query e non richiede tempi di inattività del sistema. Tra l’altro, sono disponibili anche
alcune opzioni avanzate di ottimizzazione per ulteriori miglioramenti delle prestazioni.
Ogni arco ha un'etichetta che definisce la semantica della relazione. Sulle relazioni è
possibile definire dei vincoli inerenti la molteplicità, ovvero un numero massimo di archi tra
coppie di vertici.
Le proprietà dei nodi sono coppie chiave/valore. Per esempio la proprietà name='Daniel'
ha chiave name e valore 'Daniel'. Le chiavi fanno parte dello schema di Titan e possono
limitare i tipi di dati consentiti e la cardinalità dei valori. Il nome di ciascuna chiave deve
essere univoco nel grafo, il che vuol dire che esso non può coincidere con quello di un’altra
chiave, né col nome di una label di una relazione. Come gli archi, anche i vertici possono
avere una label, che tuttavia è opzionale e finalizzata solo a distinguere diversi tipi di nodi.
Alcune delle funzionalità principali offerte da Titan sono le seguenti:
-
Scalabilità elastica e lineare per dati crescenti.
-
Distribuzione e replicazione dei dati per garantire migliori prestazioni e una maggiore
25
tolleranza agli errori.
-
Supporto delle proprità ACID e BASE.
-
Supporto per varie applicazioni di memorizzazione (Apache Cassandra, Apache
HBase, Oracle BerkeleyDB).
-
Integrazione nativa con TinkerPop.
-
Supporto nativo a diversi tipi di dati, come Integer, Float, Boolean, String, e altri.
4.1 Benefici di Titan
Di seguito elenchiamo una serie di benefici offerti da Titan:
-
Supporto di un gran numero di transazioni concorrenti; la sua capacità transazionale
aumenta con l’aumentare delle macchine costituenti il cluster.
-
Supporto nativo al modello di dati property graph esposto da Blueprints6.
-
Supporto nativo del linguaggio Gremlin per l'attraversamento dei grafi.
-
Semplice integrazione con il server grafico Rexter.
-
Numerose configurazioni a livello di grafico per l'ottimizzazione delle prestazioni.
4.1.1 Benefici di Titan con Cassandra e HBase
Cassandra è un database management system non relazionale, distribuito con licenza open
source e ottimizzato per la gestione di grandi quantità di dati. È incluso tra i database
NoSQL column family poiché ha un data model ispirato a BigTable. L’integrazione di Titan
con Cassandra offre una serie di benefici.
-
Continuous Availability7 senza alcun single point of failure8.
-
Nessun collo di bottiglia in lettura o in scrittura, in quanto non è presente alcuna
architettura master/slave.
6
Raccolta di interfacce per il modello dati property graph.
Approccio mirato a proteggere gli utenti contro tempi di inattività, qualunque sia la causa, garantendo agli utenti la
continua disponibilità dei propri file.
8
Letteralmente “singolo punto di vulnerabilità”. In un sistema informatico è un componente univoco che in caso di
malfunzionamento o anomalia causa disfunzione dell'intero sistema. A tale concetto viene contrapposto quello di
ridondanza, che prevede l'irrobustimento del sistema attraverso la duplicazione dei dati.
7
26
-
La sua scalabilità elastica consente di introdurre o rimuovere agevolmente macchine
al cluster.
-
Integrazione con Hadoop9.
HBase è un database open source, distribuito e scalabile. Modellato su Big Table e scritto
in Java, appartiene alla famiglia dei database column family. È caratterizzato da una
gestione strutturata dei dati sotto forma di tabelle di grandi dimensioni, in modo da
garantire coerenza dei dati e tolleranza alle partizioni. Come con Cassandra, anche
l’integrazione di Titan con HBase offre una serie di benefici.
-
Stretta integrazione con l'ecosistema Hadoop.
-
Supporto nativo alla strong consistency10.
-
Scalabilità lineare con l'aggiunta di macchine.
4.2 Titan e il Teorema CAP
Quando si utilizza un database, è sempre buona norma considerare il teorema CAP. Titan è
distribuito con tre backend11 di supporto: Cassandra, HBase e BerkeleyDB; in realtà, grazie
alla sua architettura modulare, può supportare anche sistemi di archiviazione di terze parti.
Nel grafico sottostante sono riportati i rispettivi compromessi rispetto al teorema CAP.
9
Framework che supporta applicazioni distribuite con elevato accesso ai dati sotto una licenza libera.
Proprietà volta a garantire che i dati rimangano consistenti su tutto il cluster in ogni momento.
11
L'insieme delle applicazioni e dei programmi con cui l'utente non interagisce direttamente ma che sono essenziali al
funzionamento del sistema.
10
27
4.3 TinkerPop e Gremlin Shell
TinkerPop è un progetto open-source che punta alla realizzazione di uno standard per la
gestione di graph database sulla piattaforma Java, sfruttando anche linguaggi alternativi che
però si integrano perfettamente nella Java Virtual Machine (JVM), come Scala o Groovy. I
componenti di questa architettura sono molti, in particolare si ricordano Blueprints e
Gremlin.
Blueprints è un insieme di interfacce e classi di base per la realizzazione di property graph
in Java; i produttori di graph database che intendono avvalersi della compatibilità con
TinkerPop devono quindi implementare il codice necessario a interfacciarsi con questa
libreria, che rappresenta l’elemento fondante di TinkerPop.
Gremlin è invece un linguaggio specifico progettato per interrogare, analizzare e
manipolare i grafi all’interno dello stack TinkerPop. Può lavorare sia con sistemi basati su
OLTP che con sistemi basati su OLAP.
Gremlin è un linguaggio di programmazione Turing completo, ossia con lo stesso potere
computazionale di una macchina di Turing universale, specializzato nella gestione di
grafi. Questo nuovo linguaggio lavora con un property graph. Oltre a fornire i tipi graph,
vertex ed edge, Gremlin offre operazioni matematiche e istruzioni condizionali specializzate
sui grafi. Il linguaggio consente di eseguire diverse operazioni sul grafo, sue caratteristiche
sono:
-
capacità di eseguire query sul grafo;
-
sintassi piuttosto succinta;
-
possibilità di compiere operazioni complesse;
-
estensibilità attraverso l’API Java.
4.4 Sperimentazione con Titan e Gremlin Shell
Nelle pagine che seguono sono mostrati una serie di esempi di utilizzo pratico di un
database Titan, manipolato tramite la shell Gremlin.
Iniziamo con un esempio banale, in cui, partendo da un nuovo grafo, vengono generati
28
alcuni nodi e relazioni. Vediamo che con l’ausilio del comando
() si
aggiungono vertici con chiavi titolo_film, attore e regista. Dopodiché, con il comando
() vengono aggiunti gli archi che stabiliscono le relazioni tra i nodi, che sono
“interpretazione” e “direzione” del film.
Di seguito si riporta un abbozzo del grafo appena creato.
29
Con il comando Element.values si ottiene il valore, o i valori, del nodo selezionato.
Con il comando Map, invece, è possibile ottenere tutte le chiavi, con i relativi valori, del
nodo scelto o, eventualmente, anche di una lista di alcuni o di tutti i nodi del grafo.
Il comando Order consente di elencare, secondo un ordine, i nodi, in base alla chiave
desiderata. Nell’esempio abbiamo ordinato due volte gli stessi elementi: una volta in base
alla chiave attore e una volta in base alla chiave id.
Come ultimo esempio si vuole prendere in considerazione un grafo leggermente più
complesso, anche se ancora di piccole dimensioni, in quanto costituito solo da alcune
centinaia di vertici e poco più di duemila archi.
30
Dapprima creiamo un nuovo grafo e carichiamo il dataset in formato graphML12.
Nella figura riportata di seguito vengono richiamati i comandi
. .
. .
() e
() che consentono il conteggio, rispettivamente, dei vertici e degli archi. I
semplici comandi
.
e . , invece, consentono l’elencazione di tutti i nodi e di tutti gli
archi del grafo, di cui per brevità, si eviterà di mostrare l’utilizzo.
Con il comando Out si ottiene l’elenco dei vertici uscenti adiacenti al vertice selezionato.
12
Formato file basato su XML per grafi.
31
Con il comando OutE si ottengono gli archi in uscita al vertice selezionato.
Con OutV, invece, si ottiene il vertice da cui esce l’arco selezionato.
Con il comando In si ottengono i vertici adiacenti al vertice selezionato.
32
Con il comando InE si ottengono gli archi entranti nel vertice selezionato.
Infine, con il comando InV si ottiene il vertice in cui entra l’arco selezionato.
Per concludere si vuole mostrare l’utilizzo dell’algoritmo Shortest Path. La ricerca del
percorso più breve tra due vertici può essere realizzata tramite un ciclo. Nel caso in cui ci
siano più percorsi che collegano due vertici, vengono dati in uscita, in ordine di numero di
vertici attraversati, tutti i percorsi o, se specificato, i primi
potrà essere selezionato quello più breve.
33
percorsi trovati e tra questi
Esempio 1. Ricerca dei primi 6 percorsi più brevi tra il vertice 1 e il vertice 3.
Esempio 2. Ricerca dei primi 5 percorsi più brevi tra il vertice 154 e il vertice 41.
Esempio 3. Ricerca dei primi 10 percorsi più brevi tra il vertice 25 e il vertice 200.
Esempio 4. Selezione del primo percorso più breve calcolato tra il vertice 4 e il vertice 55.
34
Conclusioni
In questo elaborato abbiamo messo in luce come il modello relazionale, che fino a pochi
anni fa sembrava un modello insostituibile per la rappresentazione dei dati, nell'era dei Big
Data, ha iniziato a mostrare le sue debolezze di fronte alle dimensioni e alla variabilità delle
informazioni. Infatti, sebbene rimanga ancora il modello più diffuso, il modello E-R non si
è dimostrato il più adatto quando si ha a che fare con domini molto dinamici, caratterizzati
da dati non strutturati e da moli di informazioni con rapidi incrementi che è opportuno
affrontare con sistemi in grado di scalare orizzontalmente, senza compromettere i dati
esistenti. Si è giunti, pertanto, alla nascita dei cosiddetti database NoSQL, che non hanno
segnato la fine dei sistemi relazionali, ma hanno iniziato a diffondersi con successo in tutti
quegli ambienti dove la rigidità dello schema E-R sembrava ponesse un limite all’efficienza
dei sistemi di gestione e archiviazione dei dati. Ci siamo, dunque, concentrati sui graph
database, mostrando come essi siano più performanti dei database relazionali e degli altri
database NoSQL, quando si è di fronte a enormi quantitativi di dati fortemente
interconnessi. Inoltre, essi risultano particolarmente vantaggiosi nei sistemi object-oriented,
in quanto mappano in maniera più diretta tali tipologie di domini. Per concludere, abbiamo
introdotto Titan, un database a grafo distribuito che, oltre ad apportare tutti i benefici insiti
dei graph database, offre anche la possibilità di integrazione con vari backend di supporto,
come Cassandra e HBase, nonché varie API per la creazione e la manipolazione dei grafi.
35
Bibliografia
[1]
I. Robinson, J. Webber, E. Eifrem, Graph Databases, O’Reilly, 2013.
[2]
A. Holmes, Hadoop in Practice, Manning, 2012.
[3]
Z. Majkić, Big Data Integration Theory, Springer, 2014.
[4]
A. Rezzani, Big data. Architettura, tecnologie e metodi per l'utilizzo di grandi basi
di dati, Apogeo, 2013.
[5]
A. Chianese, V. Moscato, A. Picariello, L. Sansone, Basi di dati per la gestione
dell’informazione, McGraw-Hill, 2010.
[6]
http://s3.thinkaurelius.com/docs/titan/1.0.0/benefits.html
[7]
https://it.wikipedia.org/wiki/NoSQL
[8]
https://it.wikipedia.org/wiki/Big_data
[9]
https://it.wikipedia.org/wiki/Base_di_dati_a_grafo
[10]
http://gremlindocs.spmallette.documentup.com/
[11]
https://it.wikipedia.org/wiki/Neo4j
[13]
https://en.wikipedia.org/wiki/InfiniteGraph
[14]
https://it.wikipedia.org/wiki/Grafo
[15]
http://www.kobrix.com/hgdb.jsp
[16]
http://www.programmazione.it/index.php?entity=eitem&idItem=44379
[17]
http://thinkaurelius.github.io/titan/
[18]
https://it.wikipedia.org/wiki/Teorema_CAP
[19]
https://en.wikipedia.org/wiki/Gremlin_(programming_language)
36
Ringraziamenti
Se sono riuscito a superare il mio primo vero traguardo, il mio primo “grazie” lo devo a mio
padre e mia madre, i quali mi hanno dato tutto l'appoggio necessario per il proseguimento
degli studi, senza mai farmi pesare qualche insuccesso avvenuto durante il mio percorso.
Un doveroso “grazie” va al mio amico fraterno Antonio, il cui supporto mi è stato
fondamentale sia durante la mia carriera universitaria, sia durante i periodi bui della mia
vita.
Ringrazio Ciro, Daniele e Gianni , tre compagni, o meglio, tre amici conosciuti durante gli
anni dell’università, per avermi sostenuto e sopportato durante le fasi finali del mio
percorso di laurea.
Voglio ancora ringraziare il Prof. Vincenzo Moscato, per avermi assistito durante l’attività
di tesi e, soprattutto, per avermi dato l’opportunità di approfondire le mie conoscenze
nell’ambito delle Basi di Dati.
Un ringraziamento particolare va anche all’Ing. Giancarlo Sperlì, che mi ha spesso seguito
durante le attività di laboratorio di Basi di Dati.
Infine, voglio ringraziare l’Ing. Roberto Natella, per avermi più volte aiutato a superare
diverse difficoltà durante la preparazione del mio ultimo esame.
37