Da Big Data ai Graph Database - Facoltà di Ingegneria · Scuola Politecnica e delle Scienze di...

37
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

Transcript of Da Big Data ai Graph Database - Facoltà di Ingegneria · Scuola Politecnica e delle Scienze di...

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

4

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.

5

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

6

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.

7

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.

8

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ù

9

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

10

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;

11

- 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 semi-

strutturati. 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 document-

oriented, 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

12

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

13

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.

14

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

15

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 푢, 푣 connessi da un arco, prendono il nome di

estremi dell'arco; l'arco 푒 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 푉 e 퐸 lo sono. Il grado (o valenza) di un vertice 푣 è il

numero di archi in 퐸 di cui 푣 è 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 퐷 = (푉,퐴), dove 푉 è l'insieme

dei vertici di 퐷 e 퐴 è l'insieme degli archi orientati di 퐷. 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 퐺 = (푉,퐸), due vertici 푢, 푣 ∈ 푉 si dicono connessi se esiste un

cammino con estremi 푢 e 푣.

16

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.

17

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

18

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.

19

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.

20

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.

21

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.

22

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

23

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, open-

source 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.

24

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.

25

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

26

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. 7 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.

27

- 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. 10 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.

28

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

29

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.

30

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.

31

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.

32

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.

33

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 푛 percorsi trovati e tra questi

potrà essere selezionato quello più breve.

34

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.

35

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.

36

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)

37

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.