A LMA M ATER S TUDIORUM • U NIVERSITÀ
C AMPUS
DI
C ESENA - S CUOLA
DI
DI
B OLOGNA
S CIENZE
Corso di Laurea in Scienze e Tecnologie Informatiche
DBMS BASATI SUI GRAFI:
ANALISI E PROTOTIPAZIONE DI NEO4J
Relazione finale in
Laboratorio di Basi di Dati
Relatore
Chiar.mo Prof.
Matteo Golfarelli
Correlatore
Presentata da
Dott. Simone
Matteo Torta
Graziani
Sessione II°
Anno Accademico 2013/2014
1
S OMMARIO
Intro d uzio ne ................................ ................................ ................. 6
Capito lo I Gr ap h DB MS ................................ ............................... 10
1 .1
I DB MS No SQL ................................ ............................... 10
1 .2 I Grap h DB MS ................................................................ .... 11
1 .2.1 Gr ap h Co mp ute Engine ................................ ................... 12
1 .2.2 Grap h DBMS ................................ ................................ 12
1 .2.3 Che co s’è un Grafo? ................................ ....................... 13
1 .2.4 Il Prop er ty Gr ap h Model ................................ ................. 14
1 .2.5 Le po tenzialità d ei Grap h DBMS ................................ ...... 15
1 .2.6 La Modellazio ne d i un Grafo ................................ ........... 16
Capito lo II Neo4j ................................................................ ........ 20
2 .1 Pr esentazio ne ................................................................ ..... 20
2 .2 Architettur a ................................................................ ....... 21
2 .2.1 Stor e File ................................................................ ...... 22
2 .2.2 Cache ................................ ................................ ........... 23
2 .2.3 Transactio n Management ................................ ................. 25
2 .2.4 API ................................ ................................ .............. 26
2 .2.5 Decisio ni Architetturali ................................ .................. 28
2 .3 I l mo dello d ei Dati ................................ .............................. 36
2 .3.1 No di ................................ ................................ ............. 36
2 .3.2 Relazio ni ................................................................ ...... 36
2
2 .3.3 Propr ietà ................................ ....................................... 37
2 .3.4 Labels ................................ .......................................... 37
2 .3.4 Per cor si (P ath) ................................ .............................. 38
2 .4 Gli I nd ici ................................................................ ............ 38
2 .4.1 Schema I nd ex ................................ ................................ 38
2 .4.1 No n -Schema Index (Lucene) ................................ ............ 39
2 .5 Co nstr aint ................................ ........................................... 39
2 .6 Cyp her I l Linguaggio di Interro gazio ne ................................ ..40
2 .6.1 ST ART ................................ ......................................... 42
2 .6.2 MAT CH ................................ ........................................ 42
2 .6.3 RETURN ................................ ...................................... 43
2 .6.4 Altre c lauso le Cypher ................................ ..................... 43
2 .7 L’attraver samento del grafo ................................ .................. 44
2 .7.1 Gli Algoritmi sui Grafi ................................ ................... 44
2 .7.2 Quer y ................................ ........................................... 45
2 .8 La selezio ne d ei dati ................................ ............................ 45
2 .8.1 Tecniche d i selezione ................................ ..................... 45
2 .9 Aggr egazio ne dei dati ................................ .......................... 48
2 .10 I mp ieghi Futur i ................................ ................................ ..49
2 .10.1 Viste Mater ializzate ................................ ..................... 49
2 .10.2 Patter n Mining ................................ ............................. 53
Capito lo III BenchMar king ................................ ........................... 56
3 .1 Setup dei Test ................................ ................................ .....57
3
3 .1.1 S tr uttur a ed or ganizzazio ne dei dati ................................. 57
3 .1.2 Trad uzio ne d ella base d ati ................................ ............... 59
3 .1.3 I Data Set e i Datab ase ................................ ................... 61
3 .1.4 Co nfigur azio ne ................................ .............................. 62
3 .2 Analisi Generale ................................ ................................. 63
Risultati: ................................ ................................ .............. 64
3 .3 Analisi Dettagliata ................................ .............................. 67
3 .3.1 Selettività ................................................................ ..... 67
3 .3.2 N° di Join d i Oracle ................................ ....................... 71
3 .3.3 N° Hop Neo4j ................................ ................................ 77
Capito lo IV Co nclusio ni ................................ ................................ 82
B ib lio grafia ................................ ................................ ................. 85
4
5
Introduzione
I sistemi infor mativi ( SI) so no una co mp o nente centrale delle aziende e
co nsento no d i rivoluzionare i processi prod uttivi co n lo sco po d i migli o rarne l’efficienza e la pr od uttività . Un sistema informativo è co mp o sto
d alle infor mazio ni utilizzate, gestite e p rodo tte da una organizzazione.
Questi dati devo no po ter d escr ivere q ualsiasi sfaccettatura d el mo ndo re ale, e per far si che un sistema informativo gestisca al meglio q ueste info r mazio ni, e sse do vranno essere immagazzinate e d organizzate.
Data la crescente mo le e varietà di info rmazio ni che q uesti sistemi d evo no manipolar e, è nata l’esigenza di appo ggiarsi a sistemi informatici
mu niti d i tecnolo gie d i immagazzinamento d ei d ati semp re p iù ef ficaci e
cap aci di r appr esentare o gni po ssibile aspetto d ella vita reale , a q uesto
scopo so no nate le basi di dati . In informatica , il termine databa se [1], base d i dati o b anca dati (a volte abbreviato co n la sigla DB), ind ica un archivio dati, o un insieme di ar chivi ben strutturati, in cui le informazioni
in esso co ntenute so no str uttur ate e collegate tra loro seco nd o un particol are mo dello lo gico. Il comp ito di reperire e manutenere i d ati di q uesti a r chivi è affidato a delle p ar tico lari tecno lo gie che prendo no il no me d i Data ba se M anag ement Syst em ( DBM S). La gestione d elle informazio ni è la
chiave di vo lta che a per messo all’informatica di avanzare
e svilupparsi
nel cor so d egli anni, per mettendo co sì la nascita d i una innumerevole
q uantità d i tecno lo gie.
Quasi sin d alla nascita dei datab ase , il mo d ello relazio nale è stato sic uramente q uello d i maggior successo e che meglio ha permesso d i rapp resentare e str uttur ar e i dati. Esso co nsent e d i o rganizzare le informazioni
schematizzando le so tto fo r ma d i entità co nnesse da relazio ni. Co n q uesto
mo d ello lo gico è stato po ssib ile d escrivere al meglio q uasi l’intera totalità
d ei casi d ’uso che si p resentavano nel mo ndo reale. Tuttavia, la sua nat ura
gli imp o ne che l’or ganizzazio ne dei d ati segua una serie d i vinco li e regole
che no n co nsento no alla str uttura di archiviazione d i ad attarsi a d ei camb iamenti imp r evisti . Questi vinco li so no la sua più grand e fo rza e al temp o
stesso la causa della sua d ebo lezza.
6
Co n l’avvento d i I nter net agli inizi deli anni ’90 e p iù recentemente co n
l’affer mar si d ei So cial Netwo rk co me Faceboo k e T witter, il mo ndo d ’o ggi
è semp r e p iù co nnesso e semp re p iù tipi d i informazio ni vengo no correlate
tra loro. Quest’ultime sono semp re meno so no soggette a q uei vinco li che
p er mettevano d i d efinire una struttura d i b ase alla q uale attenersi .
Co lo ssi tecno lo gici co me Goo gle, lo stesso Facebo o k e altri co me Eb ay,
hanno un p o ’ ab band o nato la “via del relazio nale ” per appo ggiarsi a d ive rsi tip i mo delli. I dati elaborati e pr od otti da q ueste multinazio nali , sono
sicur amente l’es emp io p iù lamp ante che meglio p uò far co mp rendere le
pr oblematiche che derivano nel gestir e un realtà fatta d i co nnessio ni. In un
mo nd o co sì altamente co nne sso e in co stante evo luzio ne no n po teva che
ver ificar si la nascita di tecno lo gie di immagazzinamento d ei dati capac i di
adattar si a q uesta nuo va era .
I Grap h Datab ase e d i co nseguenza i Grap h DBMS so no sicuramente la
r ispo sta p iù for te che è stata data d al mo ndo dell’info rmatica al nascere di
q ueste nuo ve esigenze. Perciò, il mod ello relazio ne inco mincia a vacillare
e a p erd er e il suo pr imato d i miglior metod o di rappresentazio ne dei d ati, e
nuo ve tecno lo gie inco minciano a p roporsi fortemente co me sua alter nativa.
Dato che il mo ndo co mmerciale è ancora fo rtemente legato agli RDBM S
( Rela tio na l Dat aba se M ana gement Sy stem ), o vvero a q uelle tecno logie
che sfr uttano il mo dello r elazio nale co me lo gica d i base nel salvar e e gestir e le infor mazio ni, e d ato che per o ra so lo le grand i co mp agnie p ossono
p er metter si d i sviluppar e ed effettuare degli stud i accurati sui Graph
DBMS, è assai scar sa la co noscenza generale che si ha di q uest’ultime di
tecno lo gie.
L’o b ie ttivo di q uesta tesi è , app unto, q uello di mettere a co nf ro nto d ue
mo nd i: q uello d ei DB MS relazio nali e q uello dei DBMS a grafo , co n lo
scopo di co mpr end ere meglio q ueste nuo ve tecnolo gie che gio rno dopo
gior no r affor zano la loro presenza sul mercato internazio nale. Per poter
r aggiungere q uesto ar d uo obiettivo , si è deciso d i scegliere co me cavie di
stud io, le d ue tecno lo gie che meglio rapp resentano i lo ro mo ndi: Oracle
p er gli RDBMS e Neo4j p er i Grap h DBMS. I d ue DB MS so no stati so tt opo sti ad una ser ie d i interro gazio ni atte a testare le performance al variare
d i deter minati fatto ri, com e la selettività, il numero di j oin che Oracle effettua, etc.
7
I test svo lti si collo cano nell'amb ito b usiness intelligence e in particol are in q uello dell’analisi O LAP - O n- Line Analytica l Pro cessing . Quest'ultimo è il p arad igma pr incipale imp egnato p er effettuare l’analisi int erattiva e veloce d i gr and i q uantità di informazio ni. In una tip ica sessione
OLAP l'utente r ichied e un insieme d i misure corr ispo ndenti ad una certa
pro spettiva d i analisi e , tramite una serie d i op erazio ni , trasfo rma
l’interr o gazio ne iniziale fino ad arrivare ad un risultato per lui p iù intere ssante. Ovvero, le tecniche OLAP vengo no imp iegate, ad esemp io, per an alizzare i risultati delle vendite d i un’azienda, l’and amento dei co sti d i a cq uisto merci, per misur ar e il successo d i una camp agna p ubb licitaria, etc .
Molto sp esso accade che il d atab ase su cui viene effettuata un’analisi p er
mezzo di tecniche OLAP, pro viene da un co ntesto OLTP - O nline Transa ctio nal Processing .
Gli str umenti OLAP si d ifferenziano d agli OLTP
p er il fatto che i pr imi hanno co me ob iettivo la performance nella ricerca e
il raggiungimento d i un'amp iezza d i interro gazione q uanto p iù grand e po ssibile; i seco nd i, invece, hanno co m e ob iettivo la garanzia d i integrità e
sicurezza delle tr ansazioni.
Il seguito della tesi è così or ganizzato :

I l p rimo cap itolo ha l’obiettivo di fornire d elle info rmazio ni che
co nsentano al lettore d i co mp rend ere il mo ndo dei Grap h DBMS ,
p er p oi affro ntar e al meglio i cap ito li successivi.

Nel seco ndo cap ito lo viene presentato Neo 4j, mettend o in risalto
le caratter istiche pr incipali, la struttura d i base , le strutture dati
d i r ifer mento e il suo linguaggio d i interro gazio ne.

I l terzo cap ito lo p resenta i t est effettuati, i q uali vengo no d iscussi in mo do tale d a mettere in risalto le caratteristiche d ella
nuo va tecno lo gia. I n p artico lare vengo no presentati i d atab ase su
cui so no stati effettuati i test, i risultati dei test e la d iscussio ne
d i q ues ti.

I nfine nel cap ito lo co nclusivo si riassume q uanto già detto pr eced entemente.
8
9
Capitolo I
Graph DBMS
In q uesto cap itolo vengono intro dotti i DB MS No SQL, fornendo al le ttore una panar mo nica sulle loro caratteristiche p rincipali, e le p rincipali
tip olo gie ( sezi o ne 1.1) . Successivamente verrà presentato il mo ndo dei
Grap h DB MS, illustr ando le caratteristiche
e i co ncetti d i base d i q uesto
nuo vo mo do di str uttur are ed or ganizzare le informazio ni (sezio ne 1.2 ) .
1.1 I DBMS NoSQL
Negli ultimi anni è incr ed ib ilmente au mentata la po polarità d elle tecn o lo gie d i immagazzinamento d i info rmazio ni co nosciute co n il no me d i N oSQL, acro nimo che sta p er No t only S QL [7].
Ma co sa so no di preciso
q ueste tecno lo gie? I NoSQL Database Management Syste m so no sistemi
so ftwar e che co nsento no d i immagazzinare e organizzare i dati senza fare
affidamento sul mod ello relazio nale,
so litamente imp iegato d a d atabase
tradizio nali .
I No SQL DBMS so no ino ltre co ntrad distinti d al fatto che no n utilizzano
un sistema trans azio nale ACI D, il q uale garantisce che o gni sua transazi o ne sodd isfi le seguenti pro prietà [6] :

Ato micity - una transazio ne è un’unità di elab orazio ne ato mica, i nd ivisib ile. Ciò significa che do vrà essere eseguita to talmente opp ur e p er niente, senza scind erla in p arti p iù picco le.

Co nsist ency - q uando viene lanciata, una transazio ne tro va il d at ab ase in uno stato co nsistente , al suo co mp letamento il D atabase
do vrà ancor a god er e d i questa proprietà.

Iso lat io n - una tr ansazione do vrà essere isolata co mp letamente d a lle altr e. I n caso di fallimento no n do vrà interferire co n le altre
transazio ni in esecuzio ne .

Dura bility - gli effetti d i una transazio ne che ha terminato correttamente la sua esecuzio ne devo no essere persistenti nel tempo .
10
I nfine, spesso q uesti tipi d i DBMS so no sch ema- less [7] , o vvero no n
po ssiedo no uno schema fisso a cui devo no attenersi, evitando sp esso così
le operazio ni di join e puntano a scalare o rizzo ntalmente.
Le p rincipali catego rie di DBMS No SQL so no [7]:
-
K ey- Va lue store .
-
Document -o riented .
-
Co lumn Fa mily sto re .
-
Gra ph DBM S.
1.2 I Graph DBMS
Numer o si pro getti e pr odo tti per la gestio ne, l’elaborazio ne e l’analisi
d ei grafi so no apparsi negli ultimi anni. Q uesta grand e q uantità d i tecno l ogie r end e d ifficile tener traccia d i q uesti strumenti e co me essi si d iffere nziano, anche per coloro che d a temp o lavorano in q uesto camp o.
T uttavia, il mo ndo d ei Grafi, se visto dall’alto , è po ssibile dived erlo in
d ue macro categor ie:
1 . Tecno log ie impiega te p rincipa lmen te p er “tran sa ctiona l on line
g rap h p ersistence”, tip icamen te accedute per mezzo d i app lic azion i rea ltime . Queste tecno lo gie vengo no chiamate Gra ph
DBM S. Esse so no l’eq uivalente d ei sistemi OLTP d el mo ndo r elazio nale. Questi sistemi so no caratterizzati d a numero se ma
semp lici e veloci transazio ni eseguite , sp esso, in maniera co ncorr enziale [2 ].
2 . Tecno log ie imp ieg ate principa lmen te per l’analisi Offline dei
g ra fi. S olitamen te e seguite come u na serie d i b atch step . Queste
tecno lo gie vengo no chiamate Gra ph Co mpute Eng ine [2].
11
1.2.1 Graph Compute Engine
Un Gr ap h Co mp ute Engine è una tecno lo gia che p ermette d i eseguire
Algo ritmi Co mp utazio nali su Grafi G lobali sopra grandi d ataset [2] . I
grap h co mp ute engine sono pro gettati p er eseguire op erazio ni co me id ent ificare cluster s all’inter no d ei dati, opp ure rispond ere a d elle do mand e c o me “Qual è la med ia della r elazi o ni che p o sseggono gli utenti d i una so cial
netwo r k? ” .
A c ausa dell’impo nenza delle inter ro gazio ni, i grap h co mp ute engine
so no o ttimizzati per scand ir e e processare enormi q uant ità di b locchi d i i nfo rmazio ne.
1.2.2 Graph DBMS
Un Grap h Datab ase M ana gement System [2] è un sistema d i gestio ne
o nline che so ttopo ne un mo d ello dati a grafo , a meto di di Creazio ne, Le ttura, Aggior namento e Cancellazio ne (Create, Read , Update e Delete :
CRUD). I Gr ap h DB MS so no generalmente c o struiti p er sistemi transazi onali OLTP. Di co nseguenza vengo no p ro gettati in mo do da ottimizzare le
prestazio ni e l’integrità d elle op erazio ni transazio nali.
Vi so no d ue co mpo nenti d a tener in mente q uando si si vuo le analizzare
una tecno lo gia di q uesto g enere:
Underlying Storage
Sebbene sia sco ntato pensare che q uesti sistemi p o sseggano o gni loro
co mpo nente pro iettata ver so il mo do d ei grafi,
in realtà so lo q ualche
Grap h DB MS utilizza dei na tive g raph sto rag e , o vvero , po ssied e una p ia ttaforma di salvata ggio d elle informazio ni sottostante nata ed ottimizzata
p er salvare i d ati sotto for ma d i grafo. Diversi grap h DB MS, in effetti, tr ad uco no e salvano le infor mazio ni in mod i d ifferenti , o vvero all’interno di
un database relazio nale, d i un database orientato agli o ggetti, o q ualche a ltro tipo di data sto re.
12
Processing Engine
Le d efinizio ni for nite dal mo ndo dei grafi richiedo no che , p er essere
co nsider ati tali, i Grap h DBMS d ebbano utilizzare l’ind ex- free ad jan cen cy
(q uesto significa che o gni elemento co ntien e un p untato re d iretto ai suoi
elementi adiacenti rendendo co sì le ricerche via ind ice no n necessarie ).
T uttavia, co me detto in preced enza,
è po ssibile espand ere la d efinizione
d i Gr ap h Datab ase Management System a tutti quei DBMS che p ermettano
d i esegui re delle op erazio ni CRUD su un mod ello dati a grafo. Ciò significa che , po ssiamo distinguere i grap h DB MS in due categorie , la p rima tutti
q uelli che sfr uttano la l’ind ex -free adjancency , processing engine nativo
(p iù p er for mante) ; la seco nda q uelli che no n la usano , p rocessing engine
no n nativo .
La figura 1.1 per mette d i avere un’idea d elle tecno lo gie presenti o ggi
sul mer cato [2]
Figur a 1.1: Ser ie di Graph DB MS presenti o ggi sul mecato.
1.2.3 Che cos’è un Grafo?
I Gr ap h DBMS or ganizzano le informazio ni so tto fo rma di grafo, perciò
è naturale chieder si co sa sia un grafo [2].
So no str utture espr essive che ci p er metto no d i mo d ellare tutti i tip i d i
scenari. Un gr afo è una raccolta d i vertici e a rchi , in p aro le semp lici, è un
insieme d i nod i co nnessi d a rela zio ni . I grafi rappresentano le entità co n i
no di, e il modo nel q uale q ueste entità si rapportano co n il mo ndo , co n le
r elazio ni.
13
Esemp io : Le info r mazioni d i T witter p osso no es sere rap presentate co me
un grafo. L’immagine sotto stante rapp resenta una picco la rete d i follo wers .
Figur a 1.2: Grafo che rapp resenta una catena di fo llo wers [2].
Le r elazio ni so no la chiave p er co mp rendere la semanti ca del co ntesto
(d ico no chi segue chi e chi è seguito da chi).Ovviamente , il vero grafo di
twitter è centinaia d i milio ni di vo lte più grande d ell’esemp io . La figura
1 .3 mo str a il po tere espressivo del mo dello a grafo .
Figur a 1.3 : Gr afo che r app resenta una catena d i fo llo wers,
co nl’aggiunta d ei messagi [ 2]
E’ facile no tare che Ruth ha p ub blicato una seq uenza di messaggi. Il
p iù recente messaggio p uò essere tro vato seguendo la Relazio ne CU RRENT; la r elazio ne P REVI OUS verrà creata mentre viene eseguito un po st.
1.2.4 Il Property Graph Model
Esisto no svariate tip ologie d i grafo e il mo nd o d ella teoria dei Grafi
fo rnisce un’infinità di soluzio ni , tuttavia l’attenzio ne verrà po sta su un s olo p artico lar e tipo d i mo d ello, il pro perty gra ph mo del [2] .
14
Un pro perty g ra ph mo del è co sì d efinito :

Un grafo co ntiene nod i e relazio ni.

I nod i po sseggo no d elle prop rietà (copp ie di chiave -valo re).

Le r elazio ni po sseggo no un no me e so no d irezio nate, ed hanno
semp r e un nodo d i partenza e un nod o d i arrivo .

Anche le r elazio ni p ossono avere d elle prop rietà.
Molte p er so ne tro vano il prop erty grap h mod el intuitivo e facile d a c ap ir e. Sebb ene semp lice, p uò essere usato p er d escrivere la stragrand e ma ggior anza d ei casi d ’uso gr afici , in mod o tale che d ia no ind icazio ni utili sui
no str i d ati.
1.2.5 Le potenzialità dei Graph DBMS
Qualsiasi co sa p uò essere mod ellata in un grafo , e i grap h DB MS fornisco d elle potenti ed or iginali tecniche di mo dellazio ne dei dati. Essi o ffrono un mod ello d ati flessibile e agile che p ermette d i adattarsi co ntinu amente all’evo lver si d ella realtà. Ecco q uelle che so no le loro po tenzialità
[2 ].
Performance
Le per for mance dei Grap h DBMS tendo no ad esse re o ttimali q uando i
d ati da archiviare so no altamente co nnessi e la mo le del dataset è estr ema mente grande. Al contrario d egli RDB MS ( Relatio nal Datab ase Man agement System) , la loro natura gli co nsente d i evitare le o nero se op erazi oni d i jo in semp licement e attraversando le relazioni che co nnetto no i nodi.
Flessibilità
I grap h DBMS so no S ch ema-less, in altre p arola no n po sseggo no uno
schema pr efissato al q uale attenersi. La loro natura gli p ermette di adatta rsi all’evo lversi del do minio app licativo senza dover rimo dellare e co nve rtire l’intera b ase dati. Ino ltre, l’aggiunta d i nuo ve relazio ni e no di non
co mpr o mette le interro gazio ni che so no state costru ite per la vecchia ve r sio ne del datab se .
15
1.2.6 La Modellazione di un Grafo
Essendo i Grap h DMB S una tec no lo gia recente, no n esiste ancora una
precisa e b en co nso lid ata tecnica d i mo dellazione. In effetti, si p uò affe r mare che nessuno po ssied e la “ricetta p erfetta ” d ella mod ellazio ne d i uno
schema a gr afo . Esisto no teor ie differenti e a vo lte co ntrastanti s ul come
do vreb be esser e la tecnica d i mo dellazio ne , il p iù delle vo lte essa prevede
la creazio ne uno schema E -R in tutto p er tutto .
Lo schema E -R, p ur essend o la base d i partenza delle tecniche d i mo de llazio ne d i un base d ati r elazio ne, è sicuramente il diagramma che più si
avvicina al p roperty gr aph mo d el.
P ur no n essendo pr esenti teorie b en co nsolid ate, verrà illustrata la p iù
accred itata ed utilizzata d elle tecniche d i mo dellazio ne.
Tecnica di Modellazione di un Grafo
Fa se 1 - Ana lisi : Nelle pr ime fasi dell’analisi, il lavo ro richied e d i
avere un appr occio simile a q uello d el mo d ello relazio nale:
utilizzando
meto di lo -fi (a b assa fedeltà, p oco pro fessio nale) viene d ata una d escrizione appro ssimativa del do minio, ma che p ermetta d i avere un’idea d i c o me
sarà po i str utturato il nostro mo d ello finale . In questa fase viene creato un
mo d ello mo lto simile a llo schema E -R.
Fa se 2 - Arricchimento : Dop o aver fatto ciò , invece d i trasfo rmare le
entità del mo d ello in tabelle , o ssia creando q uello che viene chia mato Mo d ello Lo gico , lo ar ricchiamo , co n l’o biettivo d i prod urre un’accurata ra ppresentazio ne d egli asp etti salienti del do minio. Ovvero , creiamo dal no stro schema E -R,
simile ad un grafo,
un modello a grafo arricchito di
proprietà e r elazio ni che cerchi di d escrivere al meglio il do minio del pr o b lema.
In mo lti casi in aggiunta allo schema “arricchito” , si d ecid e d i no n pro gettare uno schema generalizzato, ma rappresentare un tipico caso d ’uso
che p er metta d i dare una d escrizio ne glob ale del do minio . Ossia, ci si baserà su uno schema che mo str a i valori d elle singo le entità e d elle loro r elazio ni, esattamente il co ntr ar io di q uello che viene fatto per un datab a se
relazio nale, o vvero verrà utilizzata una so tto -istanza d el do minio per d escriver lo al meglio .
16
La modellazione nella pratica: The Movie Graph
Per meglio co mp rend ere q uesta tecnica verrà o ra mo strato un esempio
d i mo dellazio ne.
Do minio: “Si vuole rappresentare il mo nd o cinemato grafico e co me i
var i co mp o nenti pr incipali nella prod uzio ne di un film si relazio nano co n
esso.
Ogni film po ssied e una serie d i attori che interp retano un ruolo , dei
pr od utto ri, r egisti, scr ittori e chi lo ha revisio nato .”
Fa se 1 - Ana lisi: Si cercherà d i rap presentare per mezzo di uno schema
simile all’ entità r elazio ni la str uttura d i b ase d el do minio , esso do vrà ess er e appro ssimativo e or ientato alle relazio ni.
Figur a 1.4: Mo dello simile all’E -R, prodo tto dall’anailisi 1 .
Fa se 2 – Arricchiment o:
Dallo schema nato nella fase p reced ente , ne verrà creato uno nuo vo più
r icco di info r mazio ni e che meglio descriva la natura del do minio app licativo.
Figur a 1.4: Mo dello generalizzato, prodo tto nella fase 2 .
17
La figur a sop rastante mo stra il mo d ello arricchito d i particolari e
p ermette si di avere una visio ne della struttura gene rale d el grafo, ma non
co nsente
di
aver e
una
ver a
co mp rensio ne
”dell’asp etto ”
finale
del
d atabase.
Figur a 1.5: Rapp resentazio ne d i una so tto -istanza del d atabase
Co n q uest’ultimo mod ello si p uò meglio co mprend ere la natura d el d atab ase , anche se viene r appr esentata solamente una so tto istanza del dom inio.
18
19
Capitolo II
Neo4j
In q uesto cap itolo viene descritto nel d ettaglio Neo4j. Inizialmente –
co n la sezio ne 2.1 – viene d ata una d escrizio ne d i massima d ella te cno lo gia, co n l’obiettivo d i for nir e delle co noscenze d i base che permettano d i
affro ntare meglio le parti successive d el capito lo. Nella sezio ne 2.2 viene
d escritta l’architettura della tecno lo gia NoSQL. Co n la 2 .3 vengo no mo strate le caratteristiche d el mo d ello d ati a cui Neo4j fa affid amento .
Con
le sezio ni 2.4 e 2.5, vengo no descritte le strutture dati che il Grap h DB MS
sfrutta p er raggiunger e facilmente le informazioni e per mantenerle in o r d ine. Co n le sezio ni 2.6, 2.7, 2.8 e 2 .9 viene presentato il linguaggio d i i nterro gazio ne di Neo4j, e vengo no descritte alcune funzio nalità d i imp iego
d el linguaggio di interrogazio ni . Infine, co n la sezio ne 2.10 , vengo no pr o po sti d egli imp ieghi futur i nell’analisi OLAP .
2.1 Presentazione
Neo 4j [1] è un Grap h DB MS op en so urce t ransazio nale, prodo tto dalla
so ftwar e ho use Neo Techno lo gy. Po ssied e p rocessing engine e underlying
storage nativi ed è svilupp ato co mp letamente in Java. É ro b usto, scalab ile
e ad alte prestazio ni. È do tato di:

Transazio ni ACI D,

High Availab ility,

p uò memo r izzare miliardi d i no di e relazio ni,

alta velo cità d i interr o gazio ne tramite attraversamenti,

linguaggio d i interr o gazio ne d ichiarativo e grafico .
È un DBMS schema -less, ciò sta a significare che i suoi dati no n d evo no attener si al alcuna struttura d i rif ermento p refissata, ino ltre no n po ssi ed e una po litica di accesso co ntro llata .
20
La ind ex-free adjancency è alla b ase d elle sue alte p restazio ni di attr aver samento, d ’interro gazio ne e d i scrittura, ed è uno degli aspetti chiave
d ella sua ar chitettur a. L’inde x-free adjancency è una lista ( o tabella), o ve
o gni suo elemento è co mpo sto da un no do del grafo e d ai p untatori ai no di
co nnessi ad esso.
Neo 4j salva i d ati d entro d i una serie d i sto re file , co ntenuti all’interno
d i un’unica cartella . Ognuno d i q uesti file co ntiene al suo interno le i nfo r mazio ni relative ad una singo la p arte d el grafo (e.g. nod i, relazioni,
pr opr ietà). Questa sep arazio ne della struttura d el grafo facilita il suo a ttraver samento.
2.2 Architettura
La figura sotto stante mostra l’architet tura d i base d i un server Neo4j.
Figur a 2.1: Architettura interna d i Neo4j.
21
T utti i dati e le infor mazio ni del grafo che il server storicizza e gestisce
vengo no salvate all’inter no d i una serie d i file che p rend o no il no me d i
Sto re F ile, i q uali vengo no memo rizzati all’interno di un’unica cartella,
d etta Ca rtella di Da taba se. Ogni d atabase o gra fo po ssied e una prop ria
Datab a se Dir ector y, e un ser ver p uò gestire una so la di q ueste cartelle per
vo lta. Pr ima di avviar e il ser ver è po ssibile d efinire d a q uale cartella car icare
il
gr afo,
mod ificando
un
dei
file
di
co nfigurazio ne
presenti
nell’albero car telle d el ser ver ( co nf/Neo4j -server.co nf).
Gli Stor e File d i un gr afo so no innumerevo li, ma le informazio ni che ne
d escrivo no la str uttur a e i d ati che esso co n tiene so no essenzialmente tre :
-
n eo sto re.relation sh ip store.db per le relazio ni;
-
n eo sto re.propertysto re.db per le prop rietà;
-
n eo sto re.nodesto re.db per i no di.
2.2.1 Store File
Ogni elemento salvato all’interno degli Sto re File [2] p ossiede una
struttura dati d i memo r izzazio ne co n lunghezza fissa detta Reco rd.
Figur a 2.2 : Struttura del record dei no di.
La figura so prastante mo stra la struttura di un reco rd d ello Store File
d ei nod i, il q uale è lungo 9 b yte . Il p rimo b yte rappresenta un flag che i nd ica se il r eco rd è imp iegato o meno p er salvare i dati d i un nodo , i sucessivi q uattro b yte rappresentano l’ID d ella prima relazio ne co nnessa al n odo , i r estanti b yte rap presentano l’ID della prima proprietà del nodo.
Il flag-b yte è un d enominato re co mune d ei record d egli Store File d i
Neo 4j . Esso co nsente a Neo 4j di riciclare gli ID : q uando viene creato un
no do, se è pr esente un recor d no n utilizzato, esso verrà imp iegato per sa lvare i dati del nuo vo nodo , altr imenti verrà cr eato un nuo vo record da p o sizio nare in fo ndo al file . La lunghezza fissa d ei record p ermette a Neo4j
d i effettuare d elle ri cerche velo cissime: q ual ora si vo glia ricercare il nodo
22
co n id 1 00 b aster à scorr er e i primi 900 b yte d el file.
Figur a 2.3 : Str uttura del record delle relazio ni.
I r eco rd delle r elazio ni so no lunghi 33 b yte. Ogni record co ntiene gli ID
d el nodo d i partenza e d i arrivo, il p un tatore al tipo d i relazio ne , i
p untato ri ai record della preced ente e p ro ssima relazio ne d el no do di
p ar te nza e d i arrivo. Gli ultimi 4 b yte co ntengo no l’ID della prima
pr opr ietà della relazio ne.
Figur a 2.4 : Struttura del record delle p roprietà
I record delle propr ietà so no anch’essi lunghi 33 b yte e so no co mp o sti
d al p untator e al tipo di p roprietà,
dal p untatore all’ind ice, dall’Id d ella
successiva prop rietà dell’elemento a cui ap partiene e da un b lo cco d i m emo r izzazio ne. Quest’ultimo p arte co nterrà il valore assunto d alla p ropri età d el nodo o d ella relazio ne solo q ual ora si trattasse d i valori d i p ic cole
d imensio ni, nel caso d i lunghe stringhe ed array, i valori verranno salvati
in uno Store File a par te.
Questa sudd ivi sio ne fisica d ei d ati e il mod o in cui so no memo rizzati
all’inter no d egli Stor e File è la chiave che sta alla b ase delle alte prest azio ni di attraver samento d i q uesto DBMS.
2.2.2 Cache
Neo 4j [3] po ssied e d ue cache d i d iversa tipo lo gia :
-
File System Cach e ;
-
Ob ject Cach e ;
23
La File System cache agisce sugli Sto re File, caricando si in memo ria
po rzio ni d i e ssi. Ogni Stor e File viene d iviso in un nu mero semp re uguale
d i parti, tutte della stessa grandezza. La politica d i rimp iazzo d elle porzi o ni d i file è simile alla LRU ( La st Recen tly Used ).
L’Obj ect Cache agisce ad alto livello, essa mantiene in memo ria po r zio ni d i grafo che so no state caricate precedentemente dal file sytem e no n
so no so tto for ma di r ecord d egli Sto re File , ma in una che co nsente d i migliorare la velocità d i attraver samento del grafo . Per la precisio ne il co ntenuto di q uesta cache so no o gge tti (Objects) co n una rappresentazio ne
orientata a so stenere le AP I di Neo4j e gli attraversamenti del grafo. Le
op erazio ni d i lettur a po sso no essere d alle 5 a 10 vo lte più veloc i risp etto a
q uell e d ella File System Cache . Neo 4j p ermette d i ab ilitare o men o q uesta
cache, semp re agendo sui file d i co nfigurazio ne del server. L’Object Cache
è co mp o sta a sua volta da d ue cache:
-
References Ca che ;
-
High-Perfo rma nce Ca che .
La pr ima cer cherà d i utilizzare la maggior p arte d elle Ja va Virtua l Machin e Heap Memo ry messa a dispo sizio ne, ed imp iega una po litica d i ri mp iazzo LRU. Questa cache sfr utta le porzio ni di me mo ria in co mune co n le
altre app licazio ni d ella stessa J VM, q uindi essa sarà in co stante “co mp et izio ne” p er lo sp azio . Ciò sta a significare che verrà to lta de lla memo ria a
tutti q uegli o ggetti che co n lei co nd ivido no la J VM , ad esemp io : o ggetti
intermed i pro dotti dalle Query Cyp her (il linguaggio di interro gazio ne di
Neo 4j), altr e app licazioni cr eate dall’amministrato re del server, altre ap p licazio ni pr odo tte d allo stesso server Neo4j.
L’High-P er for mance Cache è d ispo nib ile so lamente nella versio ne enterprise
del ser ver . Ad essa viene ad ib ita una porzio ne d i memo ria della
J VM co mp letamente d edicata, però d i dimensio ne massima limitata. Questa
cache car ica in me mo r ia po rzio ni di grafo fino ad raggiungere il limite
massi mo , una vo lta r aggiunto sarà essa a rimp iazzare gli o ggetti, invece d i
affidarsi al Gar bage Co llectio n d ella J VM.
L'o verhead d el la
High-
Perfor mance cache è mo lto più picco lo risp etto alla Reference s Cache, così
co me i temp i di inser imento e d i ricerca .
Infine, è po ssib ile usufruir e d ella cache del sistema o perativo che o sp ita
il server Neo4j, anche q uesta vo lta mo d ificando i file di co nfigurazio ne.
24
2.2.3 Transaction Management
I l Transactio n Manage ment e il Transactio n Lo g, racchiudo no in se tu tti q uei meccanismi che hanno il co mp ito di garantire le p roprietà ACID alle tr ansazio ni d i Neo 4j.
T utte le op erazio ni che vengo no effettuate sul database, dall’accesso al
gr afo all’utilizzo d i un ind ice, ve ngo no eseguite all’interno d i una trans azio ne. Le transazio ni di Neo 4j so no d i tipo “ fla t n ested tra nsaction s ”, ovvero o gni transazio ne p uò racchiudere al suo interno una transazio ne ann id ata (di livello inferio re), la q uale se no n co mp letata correttamente p uò
co mpo rtare il ro llback della transazio ne madre a cui ap partiene e di tutte
le altre tr ansazio ni da cui d ipende q uest’ultima.
Qui so tto viene ripor tato un tip ico ciclo d i iterazio ne [3] che d escrive il
mo d o in cu i lavo rano le tr ansazio ni:
1) I nizio della tr ansazio ne.
2) Esecuzio ne delle operazio ni sul datab ase.
3) Segnalazio ne dell’avvenuto successo o meno d ella transazio ne.
4) Fine della tr ansazio ne.
E’ fo nd amentale co mp letare una transazio ne p erché , fino al suo co mp l etament o, essa no n rilascerà i lock (b locchi) acq uisiti sugli o ggetti d el d at ab ase, e no n lib er erà la memo ria della J VM occupata da tutti q uegli o ggetti
che vengo no mod ificati, creati e cancellati. E’ bene sudd ividere le grandi
transazio ni in altr e più p icco le in mo do tale da no n esaurire la J VM Heap
Memo r y a d ipo sizio ne d el server.
I l Transactio n Lo g è un p rocesso che gestisce un “d iario ”, all’interno
d el q uale vengo no annotate tutte le mo d ifiche app ortate dalle transazio ni.
Questo co mpo nente d i Neo4j è fo nd ament ale q ual ora si vo glia mantenere
il prop rio d atabase in una stato co nsistente e coerente anche in caso di una
Failur e, la q uale co stringe Neo 4j ad eseguire un ro llb ack . Il Transactio n
Lo g p uò esser e ab ilitato o meno mo d ificando i file d i co nfigurazio ne del
ser ver.
25
2.2.4 API
Anche se il filesystem e le infrastrutture di caching so no mo lto affasc inanti, i pr o gr ammato ri raramente interagisco no d irettamente co n esse, ma
preferisco no appo ggiar si ad altri strumenti, q uest ’ultimi so no le API [2 ].
Le Ap plica tion Prog ra mming In terface - API so litamente so no una serie di
proced ur e / lib rer ie messe a disp osizio ne del pro grammatore , le q uali gli
p ermetto no d i interagire co n un tecnolo gia sfruttando un linguaggio di
pro grammazio ne o altro, senza do ver co no scere e gestire i meccanismi i nterni della tecno lo gia in q uestio ne.
Neo 4j mette a d ipo sizione d iverse API, e la scelta d i imp ie gare una i nvece che un’altr a dipende dal tipo d i utilizzo che se ne vuo le fare d i q uesta
tecno lo gia.
Kernel API
Al p iù b asso livello d ello stack delle AP I di Neo4j, si tro va il Kernel
Tran sa ction Even t Heand ler . Questa API co nsent e al pro grammatore d i i nteragire co n il ciclo d i vita delle transazio ni e cap tarne gli eventi, perme ttend o gli di mo d ificare e gestir e il risultato che una transazio ne p rod urrà.
Un tip ico caso d ’uso è quando si vuo le evitare che i nod i vengano elimin ati fisicamente , a livello d i r ecord dello Store File, ma si intende eliminarli
so lo d al p unto di vista
lo gico, in mo do tale d a p oterne re cup erare i dati
anche in un seco nd o momento .
Core API
La Cor e API d i Neo4j, chiamata anche Beans AP I, è una J ava Ap i imp erativa che co nsente al pr o gr ammato re di esp orre il grafo a primitive di
creazio ne, mo d ifica, eliminazio ne ed interro gazio ne
tramite co d ice J ava.
Questa AP I p uò essere realmente veloce, ma a patto che colui che la utili zza co no sca in mo do appro fo nd ito la struttura del grafo, la q uale do vrà e ssere r ipr opo sta all’interno d el cod ice Java. Questo sta a significare che,
imp iegando la Cor e API, il pro gramma che ne nascerà sarà mo lto più vu lnerabile alle var iazio ni d el do minio app licativo che si presentano co n il
p assar e d el temp o.
26
Traversal API
La Traver sal API è una Java API d ichiarativa . Al co ntrario della Core
AP I, co n la q uale b iso gna rip roporre la struttura d el grafo all’interno del
codice Java, co n la Traversal API è po ssib ile interro gare il grafo semp l icemente
ind icando
i
vico li
generali
che
p ermetto no
di
limitare
l’attraver samento. Ciò sta a significare che, invece di indicare nel cod ice
d i pro gr amma zio ne i p ar tico lari tip i di no di, relazio ni e proprietà che si
vo glio no estrar re , è possibile co struire le interro gazio ni semp licemente
po nend o co me limiti d ell’attraversamento, la struttura generale d el so tto gr afo d i inter esse. Co n q uesta API è po ssibile co struire interro gazio ni più
generalizzate, ma meno p erfo rmanti.
Cypher
Cyp her è il linguaggio di interro gazio ne nativo di Neo4j. Esso è un li nguaggio gr afico , o vvero si b asa sulla riprod uzione grafica d el so tto -grafo
che si vuole estrarre . Esso co nsente d i creare, mod ificare, eliminate e inter ro gare i dati d el database.
I l sotto -grafo rip rodo tto nelle q uery viene chiamato p attern , e per pr o d urlo no n ser vo no str umenti partico lari , ma basta seguire delle semp lici
r ego le che p er metto no d i d i segnarlo imp iegando i caratteri ASCII ( i cara tter i presenti sulla tastiera).
I n ger go tecnico la r iprod uzio ne grafica del sotto -grafo viene chiamata
“t hing s like t his ”, è una frase che trado tta significa “ co se co me q uesta ”.
Già si p uò meglio co mpr end ere il co ncetto che sta alla base d i d ella costr uzio ne delle q uer y Cyp her. P iù avanti verrà d escritto in maggio dett aglio q uesto linguaggio d i interro gazio ne.
Altre API
Oltr e alle API appena descritte, Neo4j ne mette a d ispo sizio ne altre di
d iver sa natura. La REST API è sicuramente la p iù impo rtante tra q uelle
no n menzio nate p reced entemente. Essa fo rnisce una serie d i funzio nalità
r ichiamabili p er mezzo di richieste http d i tipo POST e GET. Su di essa si
b asa l’inter faccia W eb REST ful che co nsente all’amministr ato re d i visi o nare
lo
stato
d el
server
e
d i eseguire
divers i
tip i d i o perazio ni,
d all’esecuzio ne d i SCRIPT Cyp her, alla creazio ne d i ind ici.
27
2.2.5 Decisioni Architetturali
Quando si vuo le co str uire un sistema b asato su un grap h DBMS, vi sono
d iverse decisio ni ar chitettur ali che d evo no essere effettuate [2] . Queste
d ecisio ni d ip endo no d al pr odo tto finale che si vuo le o ttenere . Neo4j forn isce una q uantità di so luzio ni che permetto no d i sod disfare gran parte d elle
esigenze.
Attualmente mo lti DB MS vengo no eseguiti co me app licazio ni server a
se stanti, le q uali vengono acced ute per mezzo d i altri so ftware co struiti
co n librerie client. Neo4j è un DBMS inusuale, perché è p o ssib ile incorp o ralo all’inter no dei so ftwar e client opp u re eseguirlo nella maniera classica,
in altr e p aro le in mod alità ser ver.
Embedded Mode
In mod alità Emb edd ed, Neo 4j viene eseguito all’interno del processo
d ell’app licazio ne che si sta costruend o. Emb edd ed Neo4j è l’id eale per
co mp uter d esktop opp ur e Hard wa re Device , add irittura p uò essere imp ieg ato per co str uire una propr ia app licazio ne che funga da server d i database.
Ved iamo o ra q uali so no i vantaggi forniti da q uesto tipo d i architettura .
Vantaggi:
Low Lat ency: I temp i d i r ispo sta da parte del d atabase s o no chiarame nte
rap id issimi ,
visto
che
q uest’ultimo
è
una
p arte
integrante
d ell’app licazio ne.
Scelta delle API: I n q uesta mod alità è d ispo nibile la to talità delle API ,
p er cr ear e ed interro gare i d ati: le Core API, il traversal frame wo rk, e il
linguaggio d i interr o gazio ne Cyp her.
Tra nsazio ni esplicit e: Utilizzando le Core API, è po ssib ile co ntro llare
il ciclo di vita tr ansazionale , eseguendo arb itrariamente una co mp lessa s eq uenza d i co mand i a car ico del d atab ase, tutto all’interno d i una singo la
transazio n e. Le Java API co nsento no di mette re a nud o il ciclo d i vita della
transazio ni, p er mettendo di aggiungere una p erso nale gestio ne delle tra nsazio ni via evento, in mod o tale da po ter aggiungere d elle lo gica add izio nale ad o gni transazio ne.
28
Na med Indexes: L’E mb edded Mode fo rnisce una co ntro llo co mp leto
sulla creazio ne e la gestio ne d i ind ici muniti d i no me. Questa funzio nalità
è anche dispo nib ile grazie alla web -based REST interface; Cyp her no n ne è
cap ace.
Quando si esegue Neo4j in mo dalità Emb ed ded è b uo na rego la tener
co nto anche d elle seguenti no te.
J VM o nly : Neo4j è un datab ase basato sulla Java Virtual Machine
(J VM ). Diver se delle sua API so no, tuttavia, ac cessibili so lamente per
mezzo d el linguaggio base della JVM, in altre paro le il Java.
Co mpo rta mento della Ga rbag e Collectio n: Quando viene eseguito in
Emb edded Mode, Neo4j
è so ggetto al co mp ortamento d ella Garbage Co l-
lectio n ( GC) dell’app licazio ne che lo o sp ita. Lunghe p ause do vute al GC si
r ifletto no sui temp i di rispo sta delle q uery. Ad dirittura, p uò cap itare a vo lte, che q uando una istanza in Emb ed ded mod e fa parte d i un cluster Neo4j
High Availab le ( HA), una lunga p ausa d a parte del GC p uò ind urre il cl uster a rieleggere il p ropr io master (q uest’ultima parte risulterà p iù chiara
una volta che verr à affr ontata l’architettura Neo4j HA).
Data ba se lif e cycle : L’applicazio ne ho st è respo nsab ile del co ntro llo
d el ciclo di vita del d atabase. Il so ftware che incorpo ra il datab ase Neo4j
d eve essere in gr ado di lanciare e stop pare il d atabase in mo do coretto,
co ntro llando le var ie prob lematiche che ne derivano .
Server Mode
Neo 4j Ser ver è la mo dalità più co mune mente utilizzata attualmente . Il
cuor e di un database Neo4j server è un istanza di tipo Emb edded. Ecco a lcuni dei benefici d er ivanti da q uesto mod alità di esecuzio ne.
Vantaggi
REST API: I l ser ver è mu nito di una ricca REST API che p ermetto no ai
client d i sp ed ire r ichieste in formato J SON per mezzo d el proto co llo
HTTP. Le rispo ste vengo no restituite all’interno di do cumenti JSON arri cchiti co n Hyper media Lin ks che metto no in risalto ulteriori caratteristiche
d el d ataset. So no mo ltep lici le funzio nalità messe a d ispo sizio ne dalla
REST API, ma il suo p iù grande vantaggio è q uello d i potervi accendere
p er mezzo d i una semp lice app licazio ne bro wser, co me Firefo x, Chro me o
I nter net Exp lor er.
29
Plat form Independence: Dato che le informazio ni co ntenute nel server
vengo no acced ute p er mezzo di do cumenti J SON sp editi attraverso l’HTTP,
le ap plicazio ni client posso no essere co struite su q ualsiasi tipo d i p iatt afo rma, b asta p o ssed ere delle librerie client HTTP.
Scaling Independence: Quando neo4j viene eseguito in mo dalità server
po ssiamo aumentare o d iminuir e il numero d i comp o nenti del cluster ind ip endente dal tipo d i applicazio ne.
Iso la ment o da l co mpo rta mento del GC delle a ltre a pplica zio ni: In
mo d alità ser ver, Neo4j è pro tetto d all ’influenza che po trebb e avere la Garb age Co llectio n ( GC) di q ualsiasi altra app licazio ne. Ovviamente, essendo
Neo 4j una tecno lo gia recente e b asata sulla JVM, anco ra prod uce q ualche
“garba ge” ( sta a significare che, nel mo mento in cui si co nclud e un q ua lche tipo d i pr oced ur a inter na al datab ase, la memoria no n viene co mp let amente r ilasciata d a q uesti pro cessi interni ). Nel corso del tempo l’imp atto
d i Neo4j sul garbage collector è stato att entamente mo nitorato , e d urante
lo sviluppo è stato ottimizzato p er rendere minimo o gni effetto.
Quando si esegue Neo4j in mo dalità Emb ed ded è b uo na rego la tener
co nto anche d elle seguenti no te.
Netwo rk Ov erhea d: Vi è un certo o verhead d i co municazio ne pe r o gni
richiesta http . Dopo la pr ima r ichiesta, la co nnessio ne TCP rimane ap erta
fino alla chiusur a d a p arte del client.
Per -request t ra nsa ctiona l: Ogni richiesta da p arte d el client viene es eguita co me una singo la tr ansazio ne, ato micamente separata d alle altre.
T uttavia, la REST API for nisce un sup porto per l’esecuzio ne d i op erazioni
in b atch (o vvero l’esecuzio ne “acco rpata” d elle op erazio ni).
Clustering – Neo4j High Available
Qualor a si vo glia gar antir e che il proprio sistema sia in grado d i fornire
un ser vizio di er o gazio ne dei d ati co ntinuo , senza failu re po in t e in grado
d i bilanciar e e gestire un’eno r me mo le d i richieste, Neo 4j High Available
(HA) è la r ispo sta a q uesta esigenza [3]. Neo4j HA è stato pro gettato per
rend ere semp lici, le tr ansazio ni d a una singola macchina ad un una ma cchina multip la, senza dover camb iare la tipo lo gia d elle istanze che and ra nno a co mp orr e il cluster .
30
Co nsid er iamo
un
istanza
di
d atab ase
Neo4j
esistente ,
presente
all’inter no d i una sin go la macchina, già p opo lato e co nfigurato a do vere .
Per r ep licare tale app licazio ne in una macchina multipla (o cluster) ,
l’unico camb iamento r ichiesto è q uello di camb iare un semp lice parametro
d i co nfigurazio ne d ell’istanza . Sia Neo 4j stand alo ne che HA, imp lement ano la stessa inter faccia, e no n richiedo no ulterio ri mo difiche.
Neo 4j HA è in grado d i fornire le seguenti funzionalità:
1.
For nisce una fa ult- to lera nt d ata ba se a rchitecture , nella q uale d i-
ver se istanze ,
chiamate “S lave”, vengo no co nfigurate per p oter esse re
l’esatta cop ia di una singo la istanza, detta “Master”. Questo permette al
sistema utente finale d i essere co mp letamente funzio nale sia lettura che
in scr ittur a in caso d i un had ware failure , in altre p aro la nel caso una
macchina che co mpo ne il cluster si “ro mp a”.
2.
For nisce una ho rizo ntally sca ling read -m o stly a rchitecture che
p er mette al sistema di gestire meglio il carico di lettura d i una singo la
istanza d i datab ase Neo4j.
Ogni co mp o nente d i un cluster Neo4j po ssiede al suo interno una co pia
d ell’inter o database. Risp etto ad altre imp o stazio ni ma ste r- sla ve replic atio n, Neo4j è in grad o di gestire le richieste di scrittura su tutte le macch ine, co sicché no n ci sia il biso gno di rindirizzare specificatamente le r ichieste al master.
Co me è stato accennato in precedenza, un d atabase Emb edd ed p uò far
p ar te di un cluster , co me se fo sse una versio ne server. Infatti, un cluster
Neo 4j p uò ess er e co mposto sia d a istanze in Server M od e che in Emb edd ed
Mode . Questa architettur a “ibrida” è co mune in q uegli scenari
in cui un
imp r esa vuo le r end er e il prop rio sistema co mp letamente integrato (Ente rpr ise I ntegratio n) ; i rego lari aggio rnamenti che vengo no eseguiti sule
istanze Emb edded d i Neo4j, vengo no a loro vo lta app licati sui server.
31
Come opera Neo4j HA
Un c luster Neo4j HA o pera co rporativamente e ogni istanza d i d atab ase
co ntiene la lo gica necessaria al fine d i coord inarsi co n gli altri memb ri del
cluster. All'avvio un'istanza d i database Neo4j HA cercherà di co nnettersi
a un cluster esistente sp ecificato in fase d i configurazio ne. Se il cluster
esiste, l'istanza si unir à co me uno slave . In caso co ntrario , verrà creato il
cluster e l'istanza diventerà il suo master. Quando Neo4j viene eseguito in
HA mo d e, il cluster che ne nascerà sarà semp re co mpo sto da alme no un
singo lo master e zero slave .
Scrittura
Quando si esegue un'operazio ne d i scrittura su uno slave , o gni azio ne
sarà sincro nizzata co n il master, e do vranno essere acq uisiti locks (b lo cchi) sia sul master che sullo slave . Nel mo mento in cui viene esegui to il
co mmit della transazio ne , sar à innanzitutto co mp letata sul master e po i, in
caso di successo , sullo slave . P er garantir e la coerenza, i dati d ello slave
do vranno esser e semp re in linea co n q uelli del master prima di eseguire
un'o p erazio ne d i scr ittu ra. È il pro to collo d i comu nicazio ne tra lo slave e
il master che co nsente di mantenere il sistema in uno stato di co erente, in
mo d o che gli aggio r namenti vengano ap plicati auto maticamente a uno slave che co munica co n il suo master .
Le transazio ni di scri ttura che vengo no eseguite d irettamente sul mas ter
saranno eseguite co me se q uest’ultimo fo sse in
no n-HA mo de (no rmal-
mente) . I n caso d i successo della transazio ne, essa verrà inviata ( p ushed
o ut) ad un numer o co nfigur ab ile di slave (d i d efault uno). Questa pro cedura viene fatta co n “ottimismo ”, o vvero, q ualora l’op erazio ne d i rep lica dei
d ati fallisca , è co munq ue gar antita la d urab ilità delle informazio ni , dato
che so no p resenti all’inter no dell’istanza master . Scrivere d irettamente sul
master aumenta co m unque i rischi d i p erd ita delle transazio ni no n ancora
co mp letate, è b uo na regola co m unicare solamente co n gli slave .
32
Gestione delle Failure
Ogni vo lta che un’istanza Neo4j no n è p iù d isponib ile, ad esemp io p er
via d i un guasto hard war e o interruzio ni d ell a rete, le altre istanze del cl uster so no in grado d i rilevarlo e segnalarlo come temp oraneamente failed . Una istanza d i d atab ase che d iventa d ispo nib ile do po l’indisp o nibilità
verr à auto maticamente inserita nel cluster. Se il master viene meno , un altro memb r o (il più adatto ) sarà eletto da sla ve a master do po che il q u o r um sar à stato r aggiunto all'interno del cluster. Quand o il nuo vo master
avrà
camb iato
il
suo
ruo lo
informerà
tutti
i
gli
altri
co mpo ne n-
ti. Nor malmente un nuovo master viene eletto e d iviene attivo nel giro di
po chi seco nd i e d urante q uesto period o nessun a op erazio ne di scrittura può
avvenir e, esse vengo no b loccate e in rari casi viene lanciata un'eccezio ne. L'unica volta che q uesto accade è q uando un vecchio master ha appo r tato d ei camb ia menti pr ima d i d iventare ind ispo nibile, e i camb iamenti non
so no stati rep licati su nessun altro memb ro d el cluster . Se il nuo vo master
viene eletto ed esegue mod ifiche prima che il vecchio ritorni attivo , ci sar anno d ue " d iramazio ni" del database do po il p unto in cui il vecchio master è divenuto ind ispo nibile . Il master d ecad uto si p orterà via il pro prio
d atabase ( la sua “diramazio ne”) e scaricherà una copia co mp leta d el nuovo
master, per po i diventar e dispo nib ile co me slave.
Tutto questo può essere riassunto:

Operazio ni di scr ittura po sso no essere eseguite su q ualsiasi istanza
d i d atab ase di un cluster.

Neo 4j HA è fault tolerant e p uò co ntinuare ad operare sia che risult ino o ffline una serie d i macchine opp ure che ne rimanga anche solo
una attiva .

Gli schiavi sar anno sincro nizzati auto maticamente co n il master d ur ante le o per azio ni d i scrittura.

Se il master diviene o ffline (viene meno) un nuovo master sarà eletto
auto maticamente.

I l cluster gestisce automaticamente le istanze che d ivengo no ind ispo nib ili (per esemp io a causa d i p roblemi d i rete), e fa in mod o di
accettar li co me memb ri d el cluster anche q uando so no di nuo vo d ispo nib ili.

Le transazio ni so no atomiche, coerenti e d urevo li , e po i eventua lmente prop agate ad altri slave.
33

Gli aggior namenti degli slave so no co erenti per natura, ma po sso no
esser e co nfigur ati p er essere “sp inti ottimisticamente” d a un master
d urante il co mmit.

Se il master diviene o ffline , q ualsiasi operazio ne d i scrittura in es ecuzio ne ver rà b loccata e verrà eseguito il rollback. Inoltre tutte le
nuo ve tr ansazio ni verranno bloccate o fallite fino a q uando un nuo vo
master tor nerà d ispo nibile.

Le letture so no HA e la cap acità d i gestire i carichi di lettura scalano
co n l’aumentar e d elle istanze d i d atab ase che comp o ngo no il cluster .
Arbiter (arbitro)
So no p ar tico lar i istanze d i server Neo4j. Gli arbitri p o sso no essere co nsiderati co me partecipanti al cluster e il loro ruo lo è q uello d i prendere
p arte alle elezio ni d i un master co n l'unico scopo di ro mp ere i legami che
b loccano il pro c esso d i elezio ne del master.
Scenario: Abbiamo un cluster
in cui si dispo ne d i un gruppo d i d ue
istanze d i datab ase Neo 4j e un'istanza arb itro supp lementare, il cluster a ncora god e d ella tolleranza d i un singolo guasto d i una delle tre istanze.
Load Balancing
Quando viene costr uito un cluster, biso gna co nsiderare d i bilanciare il
carico del tr affico delle r ichieste che lo attraversa, in mo do d a aiutarlo a
massi mizzar e il thro ughp ut (r end imento ) e
rid urre la latenza. Neo4j non
po ssiede un Load Balancer nativo, perciò il co mp ito del b ilanciamento è
addo ssato co mp letamente d elle infrastrutture che co mp o ngo no la rete. Dato
che le inter ro gazio ni vengo no sp ed ite via HTTP, viene co llocato tra la rete
esterna il cluster un Ser ver Pro xy che funge da Bilanciatore d i Carico.
Questo ser ver si limiter à a direzio nare le richieste d i lettura verso gli slave
e q uelle d i scrittura ver so il master.
34
Cache Sharding
Un altro metodo, sfr uttato d a Neo4j p er b ilanciare il carico d i lavoro, è
q uello di imp iegare la tecnica chiamata Cach e S ha rd ing . Questa tecnica si
b asa sul fatto che le q uer ies vengo no eseguite più velo cemente, se la po rzio ne del gr afo d i interesse è ancora salvata all’interno
d ella memo ria
centr ale. I l cache Shard ing co nsiste nel direzio nare le richieste verso q uei
no di del cluster che co ntengo in memo ria centrale i so tto grafi che servo no
a sodd isfar le.
Estensioni
Le estensio ni co nsento no d i eseguire del cod ice Java all’interno d el
ser ver. L’utilizzo delle estensio ni p ermette d i estend ere la REST API o p p ure di rimp iazzarla co mp letamente.
Le estensio ni prendo no la forma di JAX- RS ann ota ted cla sses . Una
J AX-RS è una Java API co struita p er risorse REST ful, in altre p aro le è un
AP I co str uita p er il linguaggio Java nata p er interloq uire co n un architett ur a d i tipo RE ST .
Dato
che
le
estensio ni
permetto no
di
eseguire
del
codice
J ava
all’inter no dell’istanza server, l’utilizzo di q ueste potrebb e avere q ualche
imp atto sul co mp or tamento d el G ab arge Co llectio n del server.
Vantaggi
Tra nsazio ni Co mplesse : Le estensio ni perme ttono d i eseguire arb itr ar iamente una co mp lessa seq uenza di op erazio ni all’interno di un’unica
transazio ne.
Scelta delle API: Ogni estensio ne viene incorpo rata all’interno d el cu or e d el ser ver d i datab ase sotto forma di riferimento . Questo ci p ermette d i
aver e un accesso to talità delle API (Core API, traversal framewo rk, graph
algo rithm p ackage, e Cyp her) p er poter sviluppare un’estensio ne perso n alizzata.
Inca psula ment o: Siccome o gni estensio ne è nasco sta all’interno d elle
REST ful inter face, è p ossibile acc resce o mo d ificare la lo ro imp lement azio ne a p iacimento .
35
Forma t o delle Rispo st e: Co nsento no di co ntrollare il formato d elle r ispo ste.
2.3 Il modello dei Dati
In Neo4j [3] le unità fo nd amentali che co mp o ngono un grafo so no i nodi
e le relazio ni.
2.3.1 Nodi
I nod i vengo no so litamente imp egnati per rappresentare le entità, ma a
seco nd a della sfer a delle relazio ni p o sso no essere utilizzati p er sco pi d ifferenti.
A p ar te prop rietà e relazio ni , i no di po sso no anche essere etichettati
co n zer o o più Label.
2.3.2 Relazioni
Le relazio ni tr ai nod i so no una parte chiave dei database a grafo. Ci
p ermetto no d i tr o vare le infor mazio ni co nnesse. Co me per i nod i, le rel azio ni po sso no avere le p rop rietà.
Caratteristiche:
-
Una relazio ne c o nnette due no di, e po ssied e semp re un nodo d i p a r tenza e uno d i arr ivo .
-
Una relazio ne ha semp r e una direzio ne
-
Le r elazio ni po sso no essere attraversate in entramb e le d irezio ni.
Ciò significa che no n vi è b iso gno di aggiungere d elle relazio ni d up licate co n direzio ne o ppo sta.
-
Un nodo p uò esser e r elazio nato co n se stesso.
-
Le r elazio ni po sso no essere di un tipo (T yp e).
36
2.3.3 Proprietà
Sia nod i che r elazio ni po sso no avere delle pro prietà. Le proprietà so no
d elle cop pie chiave valor e, d o ve la chiave è una stri nga. Il valore delle
pr opr ietà p uò esser e sia un tipo d i p rimitiva che un array d i un tipo di pr imitiva. Per esemp io: String, int a int[].
I l valor e NULL no n è valid o per le pro prietà. Il valo re NULL p uò ess er e imp lementa ta co n l’assenza d ella prop rietà (o vvero della chiave).
2.3.4 Labels
Una label è un “named grap h co nstruct ” , viene usata per raggrup pare i
no di in sotto insiemi; tutti i nod i etichettati co n la stessa label fanno parte
d ello stesso insieme.
Diver se q uer y po sso no lavorare co n q uesti insiemi invece che con
l’inter a totalità del gr afo , rendendo le interro gazio ni più facili d a scrivere
e p iù efficienti. Un nodo p uò essere etichettato co n un d iverso numero di
Lab els, inclusa nessuna, rend endo le così un aggiunta op zio nale al grafo .
Le label vengo no usate q uando si vo glio no definire co nstraint
e a g-
giunger e ind ici sulle p roprietà.
Un esemp io : Lab el: User  p uò essere imp iegata p er etichettare tutti
q uei nodi che r appr esentano un utente. In q uesto mo d o, si p uò chied ere a
Neo 4j di eseguir e delle op erazio ne solo sui quei nod i utente, co me ad
esemp io cercar e tutti gli utenti co n un d ato no me.
T uttavia, le label po sso no essere imp iegate p er altri scop i . Per esemp io,
po sso no esser e aggiunte o tolte in fase di runtime, o vvero p o sso no essere
imp iegate p er mar care temp o raneamente i nod i, per ind icar ne uno stato. Si
p uò cr ear e un label “Offli ne” per marcare tutti i telefo ni o ffline, opp ure
“Happ y” p er gli animali felici, e co sì via.
I l massimo numer o di lab el che po sso no essere presenti nel datab ase s o no 2 miliard i, perchè po sseggo no o gnuna un id, i q uali so no d i tipo int.
37
2.3.4 Percorsi (Path)
Un p ath è uno o più no di co nnessi d a relazio ni, tip icamente recuperab ile
d a una q uer y. I l p er cor so p iù corto po ssibile ha lunghezza zero ed è co st ituito da un so lo no do senza relazio ni uscenti o in arrivo (un nodo a se). Un
p ercor so ha lunghezza 1 se è co stituito da d ue nod i co nnessi da una rel azio ne, opp ure un no do co n un relazio ne che co nnette se stesso .
2.4 Gli Indici
Gli ind ici so no p ar tico lar i strutture d ati che co nsento un rap ido accesso
ad un so tto insieme del database . Neo4j co nsente d i ind icizzare i dati, ma al
co ntrar io di mo lte altr e tecno lo gie, esso po ssiede d ue categorie d i ind ici:

Schema Index ,

No n- Schema Index ( Lucene Ind exes) .
2.4.1 Schema Index
Le per for mance vengo no aumentate creando gli schem a index, i q uali
aumentano la velocità di ricerca d ei nod i nel d atab ase. Una vo lta sp ecific ata q uale prop rietà di una deter minata Lab el è da ind icizzare, Neo4j man terrà i tuoi ind ici aggior nati e in linea co n l’evol versi d el grafo. Alcune op erazio ni d i r icer ca d ei nod i attr averso recenti p rop rietà ind icizzate , si mo streranno una significante sp inta d el rend imento .
Gli Schema I ndex in neo4j so no “even tua lly ava ilab le ” (d ispon ib ili con
il tempo ).
l’op erazio ne
Sta a
significar e
che q uando
viene
creato
un ind ice,
viene eseguita immed iatamente (hai sub ito un risco n-
tro /risultato ), o vvero viene cr eato immed iatamente. L’indice, però, viene
po polato in b ackgro und e no n è sub ito d ispo nib ile per le interro gazioni.
Co n il te mp o d iventer à online, e q uando verrà comp letamente po polato sarà pro nto p er esser e utilizzato dalle q ueries.
Se q ualco sa do vesse and are storto co n l’indice, esso finirebb e in un
“failed state”. Quando fallisce, no n p uò essere imp iegato p er velo cizzare
le q uer y. Per sistemar lo, biso gna cancellarlo (DROP) e ricrearlo (CRE ATE). E’ b uo na nor ma t enere so tto o sservazio ne i lo gs p er avere indizi r iguardo ai fallimenti.
38
Per tener traccia dello stato degli ind ici biso gna utilizzare le API a d ispo sizio ne ( shell, too ls, etc), perché co n Cyp her no n è po ssibile farlo.
Gli Schema I nd ex vengono definiti per mezzo d el linguaggio Cyp her :
CREATE INDEX ON
:name-of-label(proprety-name)
Co n q uesto co mmand o viene creato un indice sull’attrib uto
sfruttando
l’etichetta ind icat a.
2.4.1 Non-Schema Index (Lucene)
Neo 4j co nsente d i imp lementare gli ind ici “co municando ” d irettamente
co n il co mp o nente che for nisce il servizio d i d efinizio ne e co struzio ne d egli ind ici. Questo co mp o nente prend e il no me d i Lucene (neo4j -lucene index). Lucene è integr ato all’interno dello stand ard do wnlo ad d i Neo4j e
p er mette la definizio ne di d iverse tipo lo gie di indici.
La cre azio ne d egli ind ici No n -Schema viene effettuata p er mezzo di
chiamate POST alla REST API di Neo4j e, al co ntrario degli Schema Ind ex, essi no n verr anno mantenuti aggiornati d al DB MS, ma sarà co mp ito
d ell’amministr ator e aggiungere e to gliere i nod i e le relazio ni d a indici zzar e.
I No n-Schema I ndex sono mo lto importati perché vengo no imp iegati
d alla clausola ST ART d i Cyp her.
2.5 Constraint
Neo 4j co nsente d i tenere i d ati “in ord ine”. Lo fa utilizzand o le co nstraint, le q uali p er metto no di sp ecificare le rego le che i dati do vranno risp ettare. Ogni camb iamento che violerebb e q ueste rego le verrà NEGAT O.
39
Neo 4j co nsente d i r affor zar e l ’integrità dei dati co n l’uso d elle co nstraints. La unique co nst raint s è l’unica fornita per ora d a Neo 4j . Essa
viene imp iegata per assicurar si che il valore d i una proprietà sia unica per
tutti i nod i co n una sp ecifica LABEL. La uniq ue co nstraint no n significa
che tutti i nod i del grafo co n la Label ind icata, devo no per forza po ssedere
la prop rietà sp ecificata, la q uale do vrà essere uniq ue (univoco), ma che
tutti i no di d ella Lab el d i interesse che po sseggo no anche la pro prietà su
cui è stato co str uita la co nstr aint, do vranno attenersi alle regole d el vinc olo. O vvero, la co nstr aint no n vinco la la to talità dei nodi , ma solo q uel so ttoinsieme di essi, che sodd isfano le sue caratteristiche. Quindi, i nod i senza la pro prietà o/e la label specificata nella co nst raint no n so no so ggetti a
q uesta r ego la.
Aggiunger e co nstraints è un’op erazio ne ato mica che richied e d el temp o
– tutti i d ati esistenti devo no essere visio nati prima d a Neo4j , il q uale ,
una volta ver ificati i d ati, p uò rendere la co nstraint “o n” (attiva). Aggiungendo una co nstr ai nt di unicità su una proprietà, verrà aggiunta anche un
Schema I ndex. Eliminando la co nstraint si eliminerà anche l’ind ice; se si
vo rrà mantener e l’ind ice sulla proprietà, do vrà essere ricreato . Si po sso no
avere p iù di una uniq ue co nstraint p er una data LAB EL.
2.6 Cypher
Il Linguaggio di Interrogazione
Cyp her ([ 2], [3] ) per mette agli utenti ( o ad una app licazio ne che ag isce p er co nto dell’utente) d i inte rro gare il d atab ase cercando i dati che
corrispo nd o no ad una sp ecifica struttura . In termini d a p ro fano, chied i amo al database di “ cerca re tu tti queg li ogg etti simili o ch e a sso mig liano “
un cer to p atter n. Il patter n è la struttura di riferimento a cui si do vrà attenere la q uer y nella ricerca d elle informazio ni . Precedentemente è stato a ccennato q uesto co ncetto che pr end e il no me d i “things like this ”, e il modo
cui viene d escritto il patter n asso miglia al disegnar lo , usando caratteri
ASCII [es: “(a) -[:Re l] ->(b) ” ] .
40
Figur a 2.5: Rapp resentazio ne a grafo d i tre amici recipro ci (tratta da
“The Gra ph Dat abase ” d i Ian Rob iso n e J im Wabber). .
Questa str uttur a descr ive tre amici recipro ci. Qui so tto vi è il corrisp e ttivo disegno ASCII che viene usato d a Cyp he r per rappresentare la strutt ur a.
(a)-[:KNOWS]->(b)-[:KNOWS]->(c) ,
(a)-[:KNOWS]->(c)
Questo patter n descr ive un pa th (p ercorso), che co nnette (a) a (b), (b ) a
( c), e (a) a (c). So no stati imp iegato una serie d i trucchi per girare intorno
al fatto che una q uer y a so lo una dimensio ne (la lettura d el testo d a sin istra a destr a), mentre un diagramma a grafo p uò essere strutturato in p iù d i
una d imensio ne . I n q uesto caso è stato separato il p attern p rincipale in d ue
so tto -patter n per mezzo d i una virgo la. N el co mp lesso , i pattern di Cyp her
seguo no natur almente il mo d o in cui d isegniamo i grafi sulla lavagna o su
un fo glio d i carta. I l mo do i cui vengo no disegnati i pattern co n i caratteri
ASCI I è fo nd amentale p er le q uery Cyp her.
Una q uer y d i Cyp her si ancor a a una o p iù p arti d i un pattern in uno
sp ecifico p unto del gr afo ( il p unto d i partenza ), p er po i flettersi verso le
p ar ti no n anco rate che si tro vano attorno , p er cercare d ei risco ntri locali.
I n par ole più co mp r ensib ili, data una q uery co n una struttur a d i esemp io
(p atter n) , Cyp her sceglie uno o più p arti d i q uesta struttura, co n le q uali
stab ilir e i p unti d i par tenza nel grafo d a cui far iniziare la ricerca, la q uale
si svilupp a cercando r isco ntri nell’intorno d i q uesti p unti (o vvero si flette
ver so i p unti no n ancorati).
41
La po sizio ne d i par tenza, “a ncho r p oint” (p unto d i ancoraggio) , p uò essere tro vate in più mod i. Il meto do p iù co mune è l’utilizzo d i un ind ice.
Neo 4j usa gli ind ici co me ser vizio d i d eno minazio ne; ed è lo strumento di
ricerca della po sizio ni di par tenza, basato su uno o p iù valori delle pr oprietà d i una d eter minata Lab el o tipo di relazione, da cui poi far iniziare
la ricerca .
Co me mo lti linguaggi d i interro gazio ne, Cyp her è co mp o sto da clauso le.
Le p iù semp lici q uer y so no co mp oste da lla clauso la ST ART, seguita da
MAT CH e RETURN. Nell’esemp io seguente una q uery Cyp her usa q ueste
tre clausole p er sco vare i recip roci amici d ell’utente Micheal.
START a = node:user(name:’Michael’)
MATCH (a)-[:KNOWS]->(b)-[:KNOWS]->(c),(a)-[:KNOWS]->(c)
RETURN b , c ;
2.6.1 START
ST ART specifica uno o p iù p unti d i p artenza – no di o relazio ni – nel
grafo . Questi p unti d i partenza so no ottenuti p er mezzo d i ricerche su un
No n- Schem a Ind ex, o più rar amente , co n un accesso diretto ad un no do o
una relazio ne p er mezzo d i I D. Nella q uery di esemp io precedente, abb iamo cercato un nodo di partenza p er mezzo di un ind ice chiamato user. E’
stato chiesto all’ indice d i tro vare un nod o co n una p roprietà na me che assume il valor e M ichea l. I l valor e d i rito rno di q uesta ricerca è vincolato da
un iden tificatore , che pr end e il no me “a ”. L’identificatore co nsentirà di
far rifer imento al nodo di p ar tenza all’interno de lla no stra q uery.
2.6.2 MATCH
Questa è le p ar te di d escrizio ne p er esempio . Usando i caratteri ASCII
p er rapp resentar e no di e r elazio ni, d isegniamo i d ati a cui siamo interess ati. Vengo no usate le par entesi to nd e p er ind icare i nodi, e co ppie d i trattini
( -) , per disegnare le r elazio ni ( - - > e <- -). I segni maggiore(>) e min o re(<),
ind icano
la
direzio ne
della
re lazio ne.
In
mezzo
ai
trattini,
all’inter no delle par entesi q uadre e prefissato dai d ue p unti, è p resente il
no me del tipo d i relazio ne.
42
Questo p atter n p otr ebb e, in teo ria, ricorrere mo lte volte all’interno d el
gr afo ; co n un gr a nd e set d i user, po trebbero esser e presenti diversi so tto gr afi co rrispo nd enti a questo p attern. P er circo scrivere la q uery dobb iamo
anco rar la ad una o più p arti d el grafo. Lo abb i amo fatto co n la clausola
ST ART , la q uale ricerca un nodo all’interno del grafo – il nodo che rappr esenta Michael . Questo nodo è stato vinco lato all’identificatore a; ed è
stato riutilizzato ( tr aspor tando lo) all’interno della clausola MAT CH. Così
facendo abb iamo ancorato il no stro pattern ad uno specifico p unto nel gr afo .
2.6.3 RETURN
Questa cla uso la specifica q uali nod i, relazio ni e p roprietà nei d ati r isco ntrati do vranno essere restituiti al client.
2.6.4 Altre clausole Cypher
Le altr e clauso le che po ssiamo usare in una q uery Cyp her so no:
 WH ERE: For nisce d ei criteri p er filtrare i risultati d ei risco ntri.
 CREATE a nd CREATE UNIQUE : Crea nod i e relazio ni.
 DELETE : Rimuo ve no di, relazio ni e pro prietà.
 SET: Sets i valo ri delle proprietà.
 FORECH: For nisce un’azio ne d i aggio rnamento per o gni nod o di
una lista.
 UNION : Unisci i r isultati di d ue o p iù q uery (introdo tto in Neo4j
2 .0).
 WITH: Manipola il risultato d i una sotto -q uery prima che venga p a ssata alla restante p ar te della q uery.
 O PTIO NAL M ATCH : Molto simile alla clausola match, la d iffere nza sta nel fatto che , se no n vengo no effettuati risco ntri, l’OPTIONAL
MAT CH r estituirà il valore NULLs per rappresentare q uelle p arti
mancanti del p atter n. L’OPTIONAL MAT CH po trebb e essere co ns id era to l’eq uivalente del SQL o uter -jo in d el mo ndo Cyp her.
Cyp her , for nisce una ulteriore mo ltitudine d i co strutti che no n no n ver r anno elencati, ma che p ermetto no d i listare un so tto insieme d i nod i per
po i lavor arci co me se fossero le tuple d i una tabella.
43
2.7 L’attraversamento del grafo
Attr aver sar e un gr afo significa visitare i suoi nod i, seguendo le relazi o ni co nnesse da q ualche regola. In mo lti casi so lo un so tto grafo è visitab ile, laddo ve vengo no tro vati i nod i e l e relazio ni che ci interessano .
Neo 4j mette a d ispo sizio ne d ue tecniche che permetto no di perco rre il
grafo in cer ca dei suo i nod i e d elle sue relazio ni.
2.7.1 Gli Algoritmi sui Grafi
La pr ima co sa che viene in mente q uando si vuo le attraversare un grafo,
è sicur amente q uella d i imp iegare uno d ei tanti algo ritmi d i attraversame nto forniti d a l mo ndo d ella teoria dei grafi, Neo4j no n viene meno a q uesto
primo a ppro ccio.
Grap h Algo rithms
[3] p er Neo4j è un comp o nente che co ntiene
l’imp lementazio ne di alcuni d ei p iù co muni algoritmi su grafi.
Include algor itmi co me:

Shor test paths,

all p aths,

all simp le paths,

Dij kstra,

A*.
T utti q uesti algor itmi p osso no essere tro vati all’interno del co mpo nente
neo4j-g ra ph-a lgo, il q uale è p resente nello standard Neo4j do wnlo ad .
Nota : Ci so no altr i algor itmi che p osso no essere usati sui grafi più p iccoli (es. calco lo della centralità, betwenn ess, clo seness, accentraty, etc).
Questi algo ritmi no n so no stati p ro gettati p er essere utilizzati in grafi mo lto grand i, ma p o sso no r isultare utili in alcuni scenari. Essi risiedono
all’inter no d el p ackage o rg.neo4j.gra pha lgo.impl.centrality
go no co nsider ati una prod uzio ne di q ualità.
44
e no n ven-
Neo 4j possiede una serie di b uild -in algoritmi su grafo . Essi vengo no
eseguiti su un nod o d i partenza (start node). Gli algoritmi po sso no essere
utilizzati sfr uttando le varie API messe a d ispo sizio ne d i Neo4j, d a lle
REST API alle q uer y Cyp her.
2.7.2 Query
Un'altr a tecnica d i attraversamento del grafo messa a d ispo sizio ne d a
Neo 4j so no le q uer y stesse . Le interro gazio ni Cyp her co nsento no d i selezio nar e so ttoinsiemi del grafo presente nel datab ase. Questa selezio ne avviene, co me è stato d etto in preced enza, per mezz o di un p attern che ripr od uce una str uttura pr esente all’interno d el database. Ciò significa che, a nche se si effettuano d elle q uery di selezio ne, in effetti no n si fa altro che
p ercorr e il grafo per tr ov are tutti q uei so ttoinsiemi che rispecchi ano il pa tter n d ato gli in inp ut .
Questo co ncetto sarà la chiave d i volta d ella pro ssima sezio ne .
2.8 La selezione dei dati
Cyp her for nisce una mo ltep licità d i clauso le che p ermetto no d i interro gare il datab ase .
La maniera in cui vengo no imp iegate q ueste clauso le co nsento no d i d efinire d iverse tecniche di selezio ne, che influiranno , po sitivamente o neg ativamente, sulle pr estazio ni d elle q uer y.
2.8.1 Tecniche di selezione
Per affro ntare al meglio q uesta p arte si è d ec iso d i utilizzare un mo de llo d i r ifer imento, a cui so ttoporre una serie di q uery SQL e p oi analizzare
le cor resp ettive q uer y Cyp her.
La co no scenza della struttura dei mo delli no n è un problem a d i rilievo
visto che le q uer iy che verranno prese in esame no n saranno co mp lesse dal
p unto d i vista lo gico, infatti no n verranno effettuati grand i join tra le t ab elle , e la str uttur a dei mo d elli è facilmente intuibile d irettamente d alle
interr o gazio ni stesse.
45
Si pr end a in co nsider azio ne la seguente q uery SQL:
SELECT FT.*
FROM FACT500K FT, CITY c
WHERE FT.CITY = c.IDCITY
AND c.CITY = 'Alameda';
La tabella FACT500 K co ntiene all’interno una serie d i d ati statistici
sudd ivisi p er città, etnia, sesso, occupazio ne e anno .
La q uer y d i esemp io esegue un semp lice jo in tra la tabella FACT 500 K e
la tabella CITY. L’inter ro gazio ne estrarrà tutte le tuple d a FACT 500 K che
co ntengo no i d ati statistici d ella città di Alameda.
La sudd etta q uery p o-
trebbe essere tr ado tta nelle seguente q uery Cyp her:
MATCH (FT:Fact500k)-[:IN_CITY]->(c:City)
WHERE c.CITY = ‘Alamenda’
RETURN FT
La str uttura d el grafo è facilmente d ed ucibile. I nodi etichettati
“Fact500 k”, che cor rispo ndo no alle tup le della tabella FACT500 K, sono
co nnessi ai nod i co n lab el “City” p er mezzo di una semp lice relazio ne .
Chiaramente i nod i etichettati “City” corrispo nderanno ai record d ella t ab ella CITY.
I risultati d ella q uer y SQL e della q uery Cyp her so no p resso ché id ent ici, no n si po sso no co nsid erare uguali p erché le chiavi primarie ed imp o rtate no n so no p resenti in un d atabase a grafo , al co ntrario d el relazio nale.
In q uesta prima interro gazio ne Cyp her, si p uò no tare che la struttura di
rifermento all’inter no della clauso la MAT CH non presenta alcuna selezi o ne esplicita, a p ar te la for ma del pattern. Ciò significa che p rima verranno
estratti tutti i Fact p resenti nel d atabase, co n annessi tutti i nod i Città co llegati p er mezzo d ella relazio ne “IN_ CITY” , e po i successivamente verrà
effettuata la scher matur a dei r isultati in b ase al pred icato d i selezio ne pr esente nella clausola W HERE.
Chiaramente dal p unto di vista prestazio nale, la q uery ap pena d escritta
risulta assai o ner osa, visto che il mo tore d i datab ase di neo4j do vrà prima
p ercorr e il d atab ase p er estrar re tutti i so tto -grafi che corrispo nd o no a l
p attern p er car ic ar seli in me mo ria centrale, e successivamente scand irli
seq uenzialmente p er eliminar e tutti q uei risco ntri che no n sodd isfano il
pred icato d i selezio ne.
46
Nel caso di gr and i d ataset, q uesto tipo d i app roccio grava talmente ta nto sulle r isor se, d a rischiare d i saturare tutta la me mo ria RAM ad ibita al
ser ver Neo4j (q ualor a no n sia stata ded icata un’enorme q uantità d i mem o r ia).
Un’altr a q uer y Cyp her corrisp o ndente alla q uery SQL p otrebb e essere la
seguente:
MATCH (FT:Fact500k)-[:IN_CITY]->(c:City{CITY: ‘Alamenda’})
RETURN FT
I n q uesto caso il p red icato d i selettività è presente all’interno del p a tter n,
ciò sta a significar e che no n verranno caricati in memo ria centrale
tutti i Fact pr esenti nel d ataba se, ma la cernita verrà effettuata a livello di
attr aver samento d el grafo . In q uesto mo do si eviterà d i so vraccaricare la
me mo r ia RAM, e d i rid ur re notevo lmente i temp i di esecuzio ne della q u er y. Anche in q uesto caso N eo4j do vrà scand ire seq uenzialmente tutti i fact
pr esent i nel database p er poi scartare q uelli ch e no n gli interessano.
La pro ssima q uer y Cyp her suppo ne che sia stato creato un indice sulla
pr opr ietà “CITY” dei nod i etichettati “City”, q uesto p erché verrà effettuata
la ricerca imp iegando la clauso la ST ART:
START c=node:City(CITY=’Alameda’)
MATCH (c)<-[:IN_CITY]-(FT:Fact500k)
RETURN FT
Dato che è stato imp licitamente imp iegato un indice utilizzando la cla uso la
ST ART,
l’interrogazio ne risulterà
sicuramente
p iù p erformante.
L’eno r me aumento d elle prestazio ni no n è do vuto so lamente al fatto che è
stato ut ilizzato l’indice p er eseguire la q uery, il merito è d a attrib uire s o pr attutto alla lo gica della clausola ST ART.
Co me è stato d etto in precedenza , la clauso la START esegue una prima
r icer ca in base al pr ed icato d i selezio ne ind icatogli. Questi nodi verran no
imp iegati co me p unti di partenza ( an cho r po int) d a cui far pro tendere la
r icer ca vera e p ropr ia. In q uesto mo do , Neo4j no n do vrà scand ire tutti i
fact pr esenti all’inter no d el datab ase , ma si do vrà solamente limitare ad a ttraver sare tutte q uelle relazio ni che parto no dalle Citta estratte inizialme nte e che gli co nsento no raggiungere i Fact di interesse.
47
Ved iamo o ra un’ultima quer y:
START c=node(773)
MATCH (c)<-[IN_CITY]-(FT:Fact500k)
RETURN FT
In q uest’ultima interro gazio ne si p uò no tare che il “nodo ancora” viene
scelto d irettamente sp ecificando gli l’id del nodo. Il nodo ancora sarà solo
uno (co me nel caso precedente) e d a esso p artirà la ricerca. L’utilizzo d egli id p er mette di aumentare ulteriormente la velo cità di esecuzio ne delle
no stre q uer ies. O gni q ualvo lta si vuole effettuare una ricerca mo lto grande,
l’utilizzo d i q uesti id entificato ri univoci è un buo n escamo tage. T uttavia,
l’imp iego degli id imp lica che si co no sca a p riori l’id d el nodo di intere sse.
2.9 Aggregazione dei dati
L’estrazio ne d i infor mazio ni aggregate p er un certa chiave d i lettura è
una d elle co mp o nenti fond amentali dei linguaggi d i interro gazio ne. Per po ter mo str are nel mo do cor retto co me Cyp her o ffre q uesta funzio nalità, si è
d eciso di ado ttar e il metod o d ella so tto -sezio ne 2 .8. Ovvero esp orre d elle
q uery SQL, p er poi mo str are le corrisp ettive interro gazio ni Cyp her.
Si co nsid er i la seguente q uer y SQL:
SELECT C.CITY, COUNT(FT.CITY)
FROM CITY C, FACT500K FT
WHERE C.IDCITY = FT.CITY
GROUP BY C.CITY;
L’interro gazio ne
co nsente
di
co ntare
q uanti
record
d ella
tabella
FACT50 0K corr ispo ndo ad o gni valo re d ell’attrib uto CIT Y della tab ella
CITY. Nella clausola GROUP B Y viene indicato per q uali attrib uti d elle
tab elle si vuole effettuar e l’aggregazio ne. Invece la funzio ne di aggreg azio ne, in q uesto caso COUNT(), indica q ual è il valore aggregato che deve
calco lare la q uer y. Cypher o ffre soluzio ni mo lto simili al GROUP BY
d ell’SQL, o vver o le f unzio ni di agg reg azio ne e le no n- aggrega te expre ssio n. La pr ecedente q uer y SQL p uò essere trado tta nella seguente q uery
Cyp her .
MATCH (c:City)-->(ft:Fact500k)
RETURN c, count(ft);
48
Vi so no d ue espr essio ni d i rito rno – n, e co unt(f t). La prima , n, è una
funzio ne d i no n aggregazio ne ( no n-aggregate expressio n ), essa sarà la
chiave d i r aggr upp amento . L’ultima, co unt(ft) , è l’esp ressio ne d i aggr egazio ne. I n q uesto mod o il so tto grafo estratto dalla q uery viene d iviso in
d iffer enti b ucket, dip end enti d alla chiave d i raggruppamento . La funzione
d i raggr upp a mento lavorerà su q uesti b ucket , da cui calco lerà il valo re aggr egato .
2.10 Impieghi Futuri
La seguente sezio ne del cap itolo avrà princip almente il co mp ito di p r o po rre degli imp ieghi futur i d ella tecno lo gia No SQL nell’analisi OLAP.
2.10.1 Viste Materializzate
Una v ista ma t eria lizzata [1] è un o ggetto d elle b ase d i dati che co nti ene i risultati d i una q uery. Le viste materializzate po sso no essere richiam ate dalle interro gazio ni SQL co me una q ualsiasi vista o tab ella, e so litame nte co ntengo no i d ati d elle tab elle o unio ne d i tabell e già aggregati, in q u esto caso di parla d i viste di aggregazio ne.
Le viste mater ializzate so no state imp lementate p er la prima vo lta da
Oracle: d alla ver sio ne 8i. Neo4j no n po ssiede q uesto tipo di o ggetto , tutt avia, p er q uesta tesi, si è tentato d i prod urne uno del tutto simile, che p otesse in q ualche mo do miglio rare le prestazio ni del DB MS No SQL.
Nodi Aggregati
Si suppo ne di vo ler ottenere la so mma d ell’attrib uto PERWT in b ase a llo Stato e gr uppo Etnico d i app artenenza. P er ottenere q ueste informazio ni,
b iso gnerà eseguire la seguente q uery Cyp her:
MATCH (f:Census)-[:IN_CITY]->(:City)-[:IN_STATE]->(s:State),
(rg:RaceGroup)<-[:IN_RACEGROUP]-(:Race)<-[:IN_RACE]-(f)
RETURN id(s), id(rg), sum(f.PERWT);
49
Figur a 2.6 : Rappr esentazio ne d ell’attraversamento ch e viene effettutato
in assenza
La q uer y ap pena d escritta deve effettuare ben 4 Hop, p er poter restituire il
risultato r ichiesto .
Si sup po ne invece, di aver creato p reced entemente dei nod i di tipo
:Census che co ntengo no al loro interno la so mma d i PERWT a ggregato per
Stato e gr uppo etnico. E si suppo ne che q uesti nod i, invece d i essere co nnessi ai nod i d imensio nali di b aso livello, cioè :City e :Race, verrano d irettamente co llegati ai nod i dimensio nali per cui è stata fatta l’operazio ne
d i raggr up pamento, o vvero :State e :RaceGro up . Questi p artico lari nodi
verranno da ora in po i chiamati Nod i Agg reg ati.
Sfruttando i no di aggr egati basterà limitare l’attraversamento alla se mp lice selezio ne di q uesti p ar tico lari nodi.
MATCH (s:State)<--(f:Census)-->(rg:RaceGroup)
RETURN id(s), id(rg), sum(f.PERWT);
50
Figur a 2 .7: Rappr esentazio ne dell’attraversamento che viene effettu atoin pr esenza dei nod i aggregati.
Co str uendo invece i Nod i Aggregati è po ssibile ottenere lo stesso
r isultato scrivendo una query che ha la met à degli Hop .
Quind i, l’idea di base è q uella d i co struire delle q uery Cyp her che po ssano
fo r nire delle viste d i taglio, le q uali co ntengo no i d ati dei nod i :Census
aggr egati p er un deter minato livello di specializzazio ne delle dimensio ni.
Co n i risultati fo r niti da q ueste interro gazio ni, verranno po i creati dei nodi
d i tipo Census che invece d i essere co nnessi ai nod i d imensio nali d i basso
livello (es. :City, : Race, ;Occupatio n, :Sex e :Year), saranno collegati d ir ettamente ai nod i dimensio nali di livello superiore (es. :State, :Branch,
:Racegro up, :sex e :Year) . Quind i, o gniq ualvo lta si desidererà o ttenere d ei
valo ri aggregati in b ase ad un maggiore livello di raggrup pamento, invece
d i per corr e il grafo fino a raggiungere i nod i :Census co nnessi ai nod i dimensio nali di b asso livello, b asterà estrarre i nodi :Census creati in seco ndo il cr iter io app ena descritto.
51
Implementazione
Il seguente scr ip t co nsente d i creare i Nodi Aggregati, eseguendo una
vista d i taglio che r aggrup pa i Census in base al seco ndo l ivello di aggr egazio ne.
MATCH (f:Census)-[:IN_CITY]->(:City)-[:IN_STATE]>(s:State{STATE:'FL'}),
(f)-[:IN_RACE]->(:Race)-[:IN_RACEGROUP]>(rg:RaceGroup{RACEGROUP:'White'}),
(f)-[:IN_OCCUPATION]->(:Occupation)-[:IN_BRANCH]->(b:Branch),
(f)-[:IN_SEX]->(sex:Sex),
(f)-[:IN_YEAR]->(y:Year)
WITH s, rg ,b,sex,y, sum(f.PERWT) as per, sum(f.COSTELEC) as
cost
CREATE (g:Census{PERWT:0, COSTELEC:0})
MERGE (g)-[r1:IN_STATE{IDSTATE:-1}]->(s)
MERGE (g)-[r2:IN_RACEGROUP{IDRACEGROUP:-1}]->(rg)
MERGE (g)-[r3:IN_BRANCH{IDBRANCH:-1}]->(b)
MERGE (g)-[r4:IN_YEAR{IDYEAR:-1}]->(y)
MERGE (g)-[r5:IN_SEX{IDSEX:-1}]->(sex)
ON CREATE SET g.PERWT = per,
g.COSTELEC = cost,
r1.IDSTATE = s.IDSTATE
r2.IDRACEGROUP = rg.IDRACEGROUP,
r3.IDBRANCH = b.IDBRANCH,
r4.IDYEAR = y.IDYEAR,
r5.IDSEX = sex.IDSEX
RETURN g;
Per creare i Nod i aggr egati anche p er il terzo livello d i aggregazio ne,
o vvero :Regio n, :Mr n, :Sub Catego ry, :sex e :Year, basterà mo d ificare la
prima p ar te d ello scr ip t, in cui è p resente l’interro gazio ne che effettua il
calco lo dei d ati aggr egati.
Vantaggi
-
M ig lio ra ment o delle p erforma nce: Man mano che sale il livello di
aggr egazio ne aumenta anche il co ntrib uto fornito d ai Nod i Aggr egati. Effettuare delle q uery su q uesti p artico lari Nodi co mpo rta la
d iminuzio ne del numer o d i Nod i e relaz io ni da attraversare.
52
-
Riduzio ne della co mplessità delle interrog azioni: essendo Noe4j
una tecnolo gia assai giovane, il pro prio ottimizzato re no n raffinato
q uanto q uello d i altre come Oracle. Ciò significa che l’imp iego d egli
Hint
all’interno
d elle
q uery,
è
fo nd amentale
affinché
un’interro gazio ne po ssa fo rnire il risultato vo luto in temp i ragio n evo li. Diminuendo la co mp lessità d ei pattern delle q uery, cala anche
lo sfor zo che d eve effettuare il pro grammato re p er scrivere una
q uer y ottimizzata.
Svantaggi
-
Aument o delle risorse Ha rdware: aggiungere i nod i aggregati s ignifica aggiunger e Nodi e Relazio ni al grafo d ella base d ati, e p iù è
gr and e il d atab ase che Neo 4j deve gestire più è alta la richiesta di
r isor se hard war e da do ver ded icare alla tecnolo gia.
-
M anut enzio ne : la manutenzio ne dei nod i aggregati no n è facile da
gestir e.
Ogniq ualvolta
che
un
nodo
:Census
viene
mod ific a-
to/aggiunto opp ure eliminato, o pp ure accade la stessa co sa p er i
no di d imensio nali, bisogna aggio rnare d i co nseguenza tutti nodi
aggr egati che d ipendo no d a q ueste mod ifiche. Ciò significa che vi è
un enor me sfo rzo sia d a parte della tecnologia, sia da p arte
d ell’amministr ator e che d eve scrivere il cod ice che andrà a gestire i
var i camb iamenti.
-
M eta dat a : per po ter sfruttare i nod i aggregati il p ro grammato re
d eve p er for za co no scere l’intera struttura della base dati e lo stato
in cui si tro va.
2.10.2 Pattern Mining
Gli algo ritmi d i data mining co nsento no d i ricercare ed estrarre p ettern
d al d atabase. Nel data mining un pa ttern è una rappresentazio ne sintetica
e r icca di semantica di un insieme di d ati; esprime in genere un mod ello
r icorr ente nei d ati, ma può anche esp rime r e un mod ello eccezio nale.
Mentr e la maggior par te d egli app rocci di data mining ricercano i pa tter n all’inter no d i una singo la tabella,
il multi -relatio nal data mining
( MRDM) co nsente di estrarre i pattern che coinvo lgo no p iù tab elle d i un
d atabase r elazio nale.
53
Nel mo ndo OLAP estrarr e le informazio ni imp licite che interessano più
d i una tab ella significa effettuare d elle o nero se op erazio ni d i join. Per
q uesto mo tivo, d ato che i Grap h Database so no nati co n lo scop o d i riso lvere q uesto p rob lema, si vuole presentare co me la tecno lo gia No SQl p uò
affro ntare il mutli -r elatio nal data mining.
Si vuo le co ntar e q uanti Census co llegano o gni vo lare d i un livello d i
una d imensio ne, esemp io City, verso o gni altro valore livello d i un’altra
d imensio ne, esemp io : Occupatio n, Branch, Race, Category, Sex, etc .
Estr arr e q uesto tipo d i informazio ni d a un Grap h d atab ase, significa
co ntar e o gni perc or so che collega un d eterminato un nod o d imensio nale
verso un altro nodo dimensio nale. Esemp io : City e Branch. La seguente
q uery calco la il numer o d i per corsi che co llegano o gni nodo d imensio nale
:City ad un nodo d imensio nale :Sex.
START c=node:CityIdx("CITY:*")
MATCH p=(c)-[*2]-(s:Sex)
RETURN c, s, count(DISTINCT p);
54
55
Capitolo III
BenchMarking
Nei capito li p reced enti è stato d escritto Neo 4j e il mo ndo a cui app a r tiene . I n q uesto cap itolo vengo no mo strati i risultati dei test effettuati su lle d ue tecno lo gie. Nella pr ima p arte (3 .1) viene presentata l'imp o stazione
d ei test e i relativi dataset utilizzati . Successivamente, viene mo strata
un’analisi generalizzata ( sezio ne 3.2 ), co n lo scopo di evid enziare gli
aspetti, del Gr ap h DB MS, che suscitano maggior interesse. Infine , varranno analizzati d ettagliatamente q uesti asp etti (sezio ne 3.3 ) .
Per meglio co mp rendere le po tenzialità d ella tecno lo gia No Sq l, essa
verrà affiancata al suo p iù gr and e rivale: Oracle. Oracle è un DB MS di
proprietà dell’o mo nima multinaz io nale Americana. E’ un DB MS Relazio nale scr itto in C ed è forse il più utilizzato al mo nd o. Questo pro dotto è un
mo d ello di q ualità ed eccellenza a cui mo lte comp agnie fanno riferimento,
ed al co ntrario d i Neo4j , è stato affinato nel corso d i svariate decine di
anni.
Effettuare un co nfro nto tra d ue tecno lo gie co n un storia co sì d iversa e
co n d iver si livelli di matur ità, è q uasi sicuramente un azzardo, p erò dato
che so no i lead er d ei loro mo nd i è sicuramente il mod o miglio re p er co mprend ere la r ivo luzio ne tecno lo gica che ha co lp ito mo lte multinazio nali
nell’ultimo d ecennio.
Lo sco po d i q uesta tesi no n è fare un p arago ne che po ssa in q ualche
mo d o p ro muo ver e una tecno lo gia invece che un’altra, ma semp licemente
so ttopor le ad una serie di test ed analizzar ne i risultati . Per po ter eseguire
d ei test su delle tecnolo gie che immagazzinano ed organizzano info rm azio ni è fo nd amentale p osseder e un b anca d ati da so ttopo rre ai d ue DB MS.
Il d atab ase che è stato scelto si chiama IP UMS .
56
3.1 Setup dei Test
Per i test è s tato imp iegato un estratto d i un d atabase OLAP: IPUM S.
Int egra ted Public Use M icro data Series (IPUM S) [8] è l’archivio d ati
sulla p opo lazio ne a livello ind ivid uale p iù grande al mo ndo . Esso è co mpo sto da una ser ie d i camp io ni stat istici d ella p opo lazio ne d egli Stati Uniti
( IPUMS-USA) o della pop olazio ne mo n d iale (IPUMS -Internatio nal).
Per
la p recisio ne, IP UMS( -USA) è stato co struito co n i d ati forniti dai c ensimenti Amer icani effettuati dal il 1980 e al 2 000. Questo database p ermette
d i eseguire un accurata analisi sui camb iamenti a lungo termine della p opo lazio ne statunitense e mo nd iale, grazie alla grande q uantità e q ualità di
infor mazio ni che esso r acchiud e.
Essendo un dataset co mp o sto d a un’enorme mo le d i d ati, d i svariato g enere, esso p er metterà d i effettuare d ei test d i q ualità che po ssano in q ua lche mo do far luc e sui meccanismi che so no al la b ase delle interro gazioni
d i Neo4j Grap h DBMS..
3.1.1 Struttura ed organizzazione dei dati
La figur a so tto stante lo schema co ncettuale d i IP UMS mo dellato utili zzando il for malismo Data Fact Mo del [4 ]:
Figur a 3.1: Schema co ncettuale IP UMS
57
Ogni camp io ne statistico d ella p opo lazio ne è rappresentato d ell’entità
CENSUS, ed è classificato seco ndo la citt à d i p ro venienza, l’anno in cui è
stato censito , l’etnia di ap par tenenza, il sesso, e l’o ccup azio ne . Queste
cinq ue categor ie in ger go tecnico vengo no chiamate d imen sion i.
I valor i di o gni d imensio ne so no strutturati in gerarchie, d efinendo così
aggregazi o ni a d iversi livelli di dettaglio . Per esemp io, o gni città , rap presentata d all’attr ib uto “CITY” , app artiene ad un p artico lare stato (ST ATE)
d i una d eter minata r egio ne ( REGION) (ALLCITY è un campo padre che
rappresenta la totalità delle città). Grazie a q uesta organizzazio ne è po ss ib ile rispo nd er e a delle do mand e co me “q ual è la med ia d egli stip end i della
po polazio ne d i un d eterminato stato o pp ure d ell’intera regio ne ?”, evitando
co sì, d i limitare l’analisi alla so la città o all’intera nazio ne.
Lo schema mo str ato precedentemente no n è il vero aspetto d ella strutt ura della b ase d ati IP UMS, ma è uno schema che pro veniente dal mo ndo
OLAP . Il mod ello lo gico utilizzato è invece detto “star schema”.
Figur a 3.2: Star Schema d i IP UMS
58
Lo schema d ella figura 3 .2 è il vero aspetto di IP UMS. La sua struttura
è nata e co ncepita p er il mo nd o relazio nale ed è co mp o sta da un a grande
tab ella, detta Fact Table (Tab ella d ei fatti) in cui o gni tupla co ntiene i dati
statistici d ella pop olazione raggruppati p er città, sesso , oc cupazio ne, etnia
e anno di censimento , reperib ili per mezzo delle cinq ue ta belle dimen siona li.
I no ltre , q uest’ultime tab elle so no in p rima fo rma no rmale (1- NF),
o vvero i d ati d escrittivi vengo no ripetuti in o gni tup la . Anche se in 1 -NF,
il database è in un stato coerente e co nsistente.
Le tab elle d imensio nali vengo no mantenute deno rmalizzate perché le
pr estazio ni d egli RDBMS calano q ual o ra si effettua un join tra d ue grand i
r elazio ni e q uando si aumentano il numero d i join. Il co ncetto appena d escritto è in effetti la vera mo tivazio ne per la q uale so no nati i Graph
DBMS.
3.1.2 Traduzione della base dati
I l pr imo passo p er r aggiungere il fine ultimo d i q uesta tesi è stato q ue llo trasporr e la b ase dati su lla nuo va tecno lo gia, o vvero è stato trado tto
IP UMS dalla sua for ma relazio nale ad una a grafo.
Figur a 3.3: Mo dello a Grafo d i IPUMS, nato d allo Star Schema.
59
La figura 3 .3 mo str a la str uttura generale d i IPUMS nella sua forma a
grafo . La pr ima differenza che si no ta tra il mo dello relazio nale e q uello a
grafo è che le “tabelle dimensio nali so no state normalizzate ”, creand o p er
o gni livello gerar chico un nod o co n un p ropria Lab el. Un’altra d ifferenza
so no gli ID, so no stati aggiunti d ei camp i che fungo no d a id entificatori
univo ci (IDCITY, I DSTATE, I DREGION , etc), i q uali vengo no imp iegati
d a un pro gramma, cr eato appo sitamente, p er ritrasformare la base dati a
grafo in una relazio nale ed assicurarsi che la trad uzio ne dei dati sia avvenuta co rrettamente.
Co n q uest’ultimo app unto è po ssibile notare la vera e più grande d iff erenza tr a lo schema relazio nale e q uello a grafo : l’assenza d elle FOREING
KEY. Una gr ap h d atabase no n ne cessita la presenza delle chiavi imp ortate,
d ato che nasce co n l’id ea d i eliminare q uesto “limite ”. Qual ora so rga la
necessità d i r eper ir e le info r mazio ni in b ase al mod o co n cui si relazio nano
tra di esse, no n sar à più necessario effettuare le o nero se op erazio ni di join
tra le tab elle, ma baster à semp licemente “percorrere” la relazio ni che co nnetto no i vari nod i d el grafo.
IP UMS è un d at abase comp o sto da milio ni d i record, ma dato che Neo4j
è una tecno lo gia mo lto esigente d al p unto di vista d elle risorse hard ware, è
stato deciso di no n lavorare co n to talità d ei d ati d i IPUMS ma so lo co n un
so tto insieme d i essi. I no ltre, per stud iare megl io q uesta nuo va tecno lo gia
so no stati cr eati d ue d iver si d ataset d i IPUMS, i q uali so no id entici dal
p unto d i vista str utturale , p erò d ifferisco no nella q uantità d i d ati che co ntengo no, il pr imo po ssied e 500 '000 nodi/tup le Census/Fact, il seco ndo un
milio ne. Effettuando i test su q uesti d ue d ataset è po ssib ile stud iare co me
Neo 4j scali all’aumentar e d elle informazio ni d a gestire, ino ltre co nsente
analizzar e se e q uale d ei d ue DB MS riesce a scalare meglio.
Per po ter effettuare l’op erazio ne d i co nversio ne/cre azio ne della b ase
d ati è stato cr eato un pro gramma appo sito , il q uale ha la capacità d i co ll egarsi ad un ser ver Or acle, estrarne i dati e co nvertirli nella co rrispettiva
struttura a grafo ed inserir li a ll’interno di un server Neo 4j.
60
3.1.3 I Data Set e i Database
I test co nsisto no nel prend ere no ta d ei temp i di esecuzio ne d i una serie
d i Quer y ( sia Sq l che Cyp he r ), le q uali so no state eseguite su d ue d ataset.
Per o gni dataset è stato co struito un Datab se che presentasse gli ind ici e
uno che no n gli presenta sse, p er un totale d i q uattro tip i d i base d ati p er
tecno lo gia:
1) IPUMS500 K : è il no me dato alla b ase dati IPUMS che p ossiede
50 0 '00 0 elementi d i tipo Census. Questo database no n p revede la
pr esenza d i ind ici.
2) IPUMS500 K IDX: po ssiede gli stessi id entici dat i d ella preced ente
b ase dati, ma al co ntrario d i q uest’ultima, su di esso so no stati cre ati degli ind ici.
3) IPUMS1M : i dati d elle sue tabelle/nod i d imensionali so no gli stessi
d i IPUMS500 K, ma al contrario di q uest’ultimo co ntiene l suo inte r no un milio ne di Census (circa) . Su d i esso no n so no stati costruiti
ind ici.
4) IPUMS1M IDX: analo gamente ad IPUMS500 K IDX, q uesto d atabase
è la cop ia di IP UMS1 M, su cui so no stati co struiti d egli ind ici.
Ad o gni esecuzio ne delle q uery so no stati semp re svuotate le me mo rie d elle d ue tecno lo gie. Ovvero , ad Oracle è stata liberata la memo ria cache e il
po ol SQL co ndiviso , per mezzo del seguente scrip t:
alter system flush buffer_cache;
alter system flush shared_pool;
I nvece, per q uanto riguard a Neo 4j, dato che no n esisto co mand i di scripting che per mettano d i liberare la memo ria cache, p rima di eseguire o gni
singo la interro gazio ne è stato riavviato il server.
Una vo lta segnati i temp i d i esecuzio ne d elle query , so no stati effettuati
d egli stud i per ricavar ne d elle co nsiderazio ni che po ssano in q ualche mo do
far luce sulle caratter istiche di Neo4j, e in generale dei Grap h DB MS .
61
3.1.4 Configurazione
I test so no stati eseguiti su una macchina co n le seguenti caratterist iche:
-
Processore : I ntel® Core™ i5 -M4 30 @2.27 GHz 1° Generazio ne , co n
3 MB d i cache d i livello 2 .
-
Mem o ria RAM : 8Gb (2 x SO -DIMM DDR3 SDRAM d a 409 6Mb )
-
Sistem a Op era tivo : W indo ws 7 Pro fessio nal 64 bit .
-
Disco Rig ido : SAT A d a 64 0 GB a 5.4 00 rp m .
Su q uesto co mp uter è stato installato un server Oracle 11 g v2 :
-
Installa zio ne di T ipo : Enterprice Editio n
-
Set d i Ca ratteri : Pr edefinito (W E8 MSWIN1252)
-
SID: ORA11 GMATP C
Neo 4j no n necessita d i una installazio ne vera e pro pria, in effetti il se r ver co nsiste in una cartella co ntenente tutta la struttura necessari a alla sua
esecuzio ne. Per lo svilupp o d i q uesta tesi è stato imp iegato Neo4j Enterprice Edit io n v ersio ne 2 .0 .1 . Per sfruttare il più p o ssib ile le sue po tenzialità è stata abilitata la High -Performance Cache e la funzio nalità d i lo gging. I noltr e, p er effettuare dei test accurati che no n pregiud icassero ne ssuna d elle d ue tecno lo gie, al server Neo4j e al ser ver Orale so no stati d ed icati lo stesso ammo ntare d i memo ria , e dato che Neo4j necessita di una
d eterminata q uantità di RAM b asata sulla mo le d i dati che deve gestire, la
scelta d ell a q uantità d i me mo r ia d a ded icare ai s erver è stata effettuata b asando si sulle r isor se hard war e di base richieste d a Neo4j. Il calco lo delle
risorse d a d edicare al ser ver Neo4j è stato fatto per mezzo del web tool
presente
sul
sito
della
NeoTecnolo gy
all’i ndirizzo
http://www.neo techno lo gy.co m/hard ware -sizing/.
Ta belle della me mo ria dedicata a i server:
MEMORIA IPUMS 500K
MEMORIA IPUMS 500K IDX
SGA+PGA
1400 Mb
Oracle
SGA+PGA
1400 Mb
Oracle
MEM JVM
1400 Mb
Neo4j
MEM JVM
1400 Mb
Neo4j
RAM
MACCHINA
8Gb
Macchina
Fisica
RAM
MACCHINA
8Gb
Macchina
Fisica
Tab ella 3.1 .a
Tab ella 3.1 .b
62
Tab ella 3 .1.a / 3.1 .b: Ammo ntare di memo ria dedicata ai server Oracle e
Neo 4j al mo me nto d ell’esecuz io ne d ei test sui d atabase IPUMS 500 K e
IP UMS 500 K I DX.
MEMORIA IPUMS 1M
MEMORIA IPUMS 1M IDX
SGA+PGA
2800 Mb
Oracle
SGA+PGA
2800 Mb
Oracle
MEM JVM
2800 Mb
Neo4j
MEM JVM
2800 Mb
Neo4j
RAM
MACCHINA
8Gb
Macchina
Fisica
RAM
MACCHINA
8Gb
Macchina
Fisica
Tab ella 3.2 .a
Tabella 3.2.b
Tab ella 3 .2.a / 3.2 .b: Ammo ntare di memo ria dedicata ai server Oracle e
Neo 4j al mo mento d ell’esecuzio ne d ei test su i d atabase IP UMS 1M e
IP UMS 1M I DX.
3.2 Analisi Generale
La pr ima serie d i interrogazio ni, a cui so no s tate so ttopo ste le d ue te cno lo gie, è nata co n lo scop o d i fornire dei dati quantitativi che po ssano in
q ualche mo do d ar e un’idea d el co mpo rtamento dell a nuo va tecnolo gia .
QUERY
Aggregazioni
Selezione
Predicato di
selettività
1
City
nessuna
1
2
Region
nessuna
1
3
Region
5 Region su 10
4
City, Race
nessuna
1
5
Region, Mrn
1
6
Region, Mrn
nessuna
5 Region su 10,
3 Mrn su 10
7
8
9
10
City, Race,
Occupation
Region, Mrn
Category,
Region,
Category,
Mrn
State, Mrn, Sex
Branch, Year,
0,5
0,15
nessuna
1
nessuna
1
5 Region su 10,
3 Mrn su 10,
5 Categpry su 10
5 State su 1112,
5 Branch su 27
0,075
0.000833
Tab ella 3 .3 : Tab ella che rip orta le caratteristiche principali d elle 10
q uer y co n cui è stata effettuata la prima analisi delle tecnolo gie .
63
I l pr edicato d i selettività è stato calcolato suppo nendo che il numero
d elle relazio ni che co nnet to no i vari nod i :Census ai nod i d imensio nali , e
analo gamente il numer o d i r eco rd d ella Fact Tab le per valo re d imensio nale, sia b ilanciato .
Risultati:
IPUM S 500K IDX
QUERY
Tempi
ORACLE
(secondi)
Tempi
NEO4J
(secondi)
N°
Elem.
Output
JOIN
Oracle
N°
HOP
(Neo4j)
Predicato
di
Selettività
Rapporto
Tempi
1
2
3
4
5
6
7
8
9
10
1,104
2,238
2,541
2,045
2,462
2,159
15,874
2,500
2,621
2,494
18,491
21,044
13,12
29,204
33,595
19,905
224,391
51,839
30,938
45,661
1077
10
5
22740
38
10
347735
269
36
57
1
1
1
2
2
2
3
3
3
5
1
3
3
2
6
6
3
9
9
13
1
1
0,5
1
1
0,15
1
1
0,075
0,00083
16,75
9,40
5,16
14,28
13,65
9,22
14,14
20,73
11,80
18,31
Tab ella 3 .4: Tab ella che r ipor t a i risultati dei test es eguiti su IPUMS 500K
IDX
IPUM S 500K
QUERY
Tempi
ORACLE
(secondi)
Tempi
NEO4J
(secondi)
N°
Elem.
Output
JOIN
Oracle
N°
HOP
(Neo4j)
Predicato
di
Selettività
Rapporto
Tempi
1
2
3
4
5
6
7
8
9
10
2,041
2,663
2,336
2,837
2,529
2,420
16,578
3,110
2,572
3,109
66,019
53,805
120,491
69,226
80,746
51,734
226,239
55,766
36,562
50,061
1077
10
5
22740
38
10
347735
269
36
57
1
1
1
2
2
2
3
3
3
5
1
3
3
2
6
6
3
9
9
13
1
1
0,5
1
1
0,15
1
1
0,075
0,00083
32,34
20,21
51,58
24,40
31,93
21,38
13,65
17,93
14,21
16,10
Tab ella 3.5 : Tabella che riporta i risultati d ei test ese guiti su IP UMS
50 0K .
64
IPUM S 1M IDX
QUERY
Tempi
ORACLE
(secondi)
Tempi
NEO4J
(secondi)
Num.
Elem.
Output
JOIN
Oracle
N°
HOP
(Neo4j)
Predicato
di
Selettività
Rapporto
Tempi
1
2
3
4
5
6
7
8
9
10
2,822
2,791
2,520
3,872
3,077
2,723
32,720
3,256
3,266
2,931
37,48
48,812
31,152
47,039
57,003
38,486
375,232
113,934
72,756
107,268
1077
10
5
30166
39
10
550430
286
37
72
1
1
1
2
2
2
3
3
3
5
1
3
3
2
6
6
3
9
9
13
1
1
0,5
1
1
0,15
1
1
0,075
0,00083
13,28
17,49
12,36
12,15
18,52
14,13
11,47
34,99
22,27
36,59
Tab ella 3 .6: Tab ella che riporta i risultati dei test eseguiti su IPUMS 1M
I DX.
IPUM S 1M
QUERY
Tempi
ORACLE
(secondi)
Tempi
NEO4J
(secondi)
Num.
Elem.
Output
JOIN
Oracle
N°
HOP
(Neo4j)
Predicato
di
Selettività
Rapporto
Tempi
1
2
3
4
5
6
7
8
9
10
4,055
4,530
4,013
5,126
4,775
4,261
33,787
4,821
4,533
4,160
91,634
119,809
259,741
153,139
109,004
108,179
377,06
110,026
67,696
104,522
1077
10
5
30166
39
10
550430
286
37
72
1
1
1
2
2
2
3
3
3
5
1
3
3
2
6
6
3
9
9
13
1
1
0,5
1
1
0,15
1
1
0,075
0,00083
22,60
26,45
64,73
29,88
22,83
25,39
11,16
22,82
14,93
25,13
Tab ella 3.7 : Tab ella che r iporta i risultati dei test eseguiti su IPUMS 1 M.
Ai temp i d i esecuzio ne d elle varie q uery, so no stati affiancati dei valor i che ripo r tano le c aratteristiche principali d elle interro gazio ni:

Num. Elem. O utput: Numero d i elementi di o utp ut restituiti
d alla q uer y.

Jo in ORACLE: Numero d i Jo in che Oracle d eve effettuare per
po ter es tr arr e il r isultato richiesto d alla q uery SQL.

N° Ho p (Neo4j ): E’ un valo re che indica il numero di relazio ni
d i cui è co mp o sto il pattern d ella q uery Cyp her.
65

Selett ività: Viene ind icato il pred icato d i selettività d elle q uery.
I l valore è ind icativo ed è stato calcolato presupp o nendo che il
d ataset no n pr esenti situazio ni ano male.
Inoltr e, per o gni singo la interro gazio ne è stato calco lato il rapp orto fra
il tempo d i esecuzio ne della q uery SQL e q uella Cyp her.
Maggio re è il valor e che assume q uesto d ato, maggio re è la cap acità di
Oracle d i affro ntare meglio l’esecuzio ne dell’inte rro gazio ne risp etto a
Neo 4j.
Discussione dei risultati
Dai r isultati o ttenuti è già p o ssib ile fare delle p icco le co nstatazio ni.
Dalle q uer y 2 e 3, 5 e 6 , 8 e 9, si p uò no tare che a parità d i join d a parte di
Oracle
e
Ho p
( numer o
di
r elazio ni
di
cui
è
co mp o sto
il
p attern
d ell’inter ro gazio ne Cypher) da p arte di Neo4j, al diminuire d el predicato
d i selettività, d iminuisce anche il rap porto dei temp i. Ovvero , Neo4j q ua ndo effettua una r icerca mir ata su un so tto gruppo d i d ati, tende a “guad agnare ter reno ” nei co nfro nti d i Oracle. E’ inoltre p o ssib ile o sservare che il
miglio ramento è assai più mar cato nei database in cui so no presenti ind ici,
q uesto per ché nelle q uer y Cyp her (Neo4j) imp iegate in q uesti DB è stata
utilizzata ( q uasi su tutte) la clausola ST ART, la q uale co nsente d i migli orare co nsid erevolmente le prestazio ni d i una q uery all’aumentare d ella s elettività.
Un altro asp etto degno di no ta è il co mp ortamento che assumo no i risu ltati man mano che il numer o d i J oin d i Oracle aumenta . Si co nsid erino le
q uery 1, 4 e 7 . I risultati mo strano un co nsiderevo le abb assamento d ei ra p po rti d ei temp i all’aumentare d el numero d i join che Oracle è co stretto ad
eseguir e per po ter for nire il r isultato finale. La Tabella d ei risultati che ripo rta i d ati di IP UMS 1M mo stra u n aumento sostanziale del rappo rto dei
temp i p er la q uer y n°4, do vuto ad un peggio ramento delle prestazio ne di
Neo 4j.
Questo so stanziale calo è prob ab ilmente do vuto ad un p iano di
esecuzio ne no n o ttimale.
66
I nfine, un ulter ior e caso d i stud io è co me varia i l rapporto d ei temp i in
funzio ne d el n° d i Hop ( salti) di cui è co mp o sto il p attern delle q uery d i
Neo 4j. Per studiare q uesto co mpo rtamento so no stati messi a co nfro nto i
r appo rti dei temp i d elle q uery N° 2, 5 e 8. Queste q uery so no caratterizzate
d al so stanziale aumento d i salti da una q uery all’altra. E’ d a so tto lineare il
fatto che il numer o d i hop che le q uery Cyp her so no co strette ad effettuare
p er ottener e il r isultato, è assai sup eriore risp etto al numero di join che i nvece Oracle deve far e p er otte nere il medesimo risultato.
3.3 Analisi Dettagliata
I n base alle o sser vazio ni effettuate sui risultati d elle precedenti q uery,
si è deciso d i stud iare più app ro fo nditamente i tre co ncetti chiave che ha nno interessato la preced ente discussio ne dei risultat i o vvero:
1) La selettività.
2) I l numer o d i Jo in delle query SQL .
3) I l numer o d i Hop delle query Cyp her.
Perciò so no state cr eati tre grupp i d i q uery, uno p er o gni caso d i studio,
co mpo sti d a tre interro gazio ni ciascuno . Le q uery app artenenti allo stesso
caso d i stud io po ssiedo no la stessa struttura di base, ma differisco no dalle
interr o gazio ni in un solo aspetto, che d ipende d al ca so d i studio stesso. Ad
esemp io , p er la selettività, le tre q uery andranno a toccare le stesse tabe lle/tip i d i nodi, ma d iffer iranno n el pred icato d i selettività, il q uale do vrà
esser e via via sempr e p iù picco lo .
3.3.1 Selettività
I l p rimo gr uppo è nato co n l’ob iettivo di studiare il co mportamento de lle d ue tecno lo gie all’aumentare d ella selettività. P er far si che i temp i di
esecuzio ne d ip endessero solamente dal p red icato di selettività e no n d a a ltr i fattor i, le tr e q uer y so no state strutturate in mo d o tale da effettuare il
mino r numero di join/ho p, senza però do ver scrivere al tempo stesso
un’interro gazio ne estremamente lunga .
67
Perc iò la str uttur a d i base è la seguente:
SELECT C.REGION, sum(FT.PERWT)
FROM CITY C, FACT500K FT
WHERE C.IDCITY = FT.CITY
AND (Selettività)
GROUP BY C.REGION;
L’interro gazio ne sq l è stata tradotta nelle seguenti q uery Cyp her:
Ser ver Neo4j co n indici
Server Neo4j senza ind ici
START
r=node:RegionIdx(Selettività)
MATCH (f:Census)-[*3]->(r)
RETURN id(r), sum(f.PERWT);
MATCH
(f:Census)-[*3]->(r:Region)
WHERE Selettività
RETURN id(r), sum(f.PERWT);
La seguente tab ella mo str a le caratteristiche princip ali de lle q uery.
ID
Aggregazioni
Predicato
di Selettività
Descrizione
1
Region
0,5
selezione 5 Region su 10
2
Region
0,3
selezione 3 Region su 10
3
Region
0,1
selezione 1 Region su 10
Tab ella 3.8 : Car atteristiche d elle interro gazio ni.
IPUM S 500K IDX
QUERY
Tempi
ORACLE
(secondi)
Tempi
NEO4J
(secondi)
Num.
Elem.
Output
JOIN
Oracle
N°
HOP
(Neo4j)
Predicato
di
Selettività
Rapporto
Tempi
1
2
3
1,6347
1,6865
1,5489
17,486
14,461
9,971
5
3
1
1
1
1
3
3
3
0,5
0,3
0,1
10,7
8,58
6,44
Tab ella 3.9 : Risultati del g r uppo d i q uery eseguite su IPUMS 500 K .
68
IPUM S 500K
QUERY
Tempi
ORACLE
(secondi)
Tempi
NEO4J
(secondi)
Num.
Elem.
Output
JOIN
Oracle
N°
HOP
(Neo4j)
Predicato
di
Selettività
Rapporto
Tempi
1
2
3
1,6318
1,8533
1,7294
99,621
88,343
62,525
5
3
1
1
1
1
3
3
3
0,5
0,3
0,1
61,05
47,67
36,15
Tab ella 3.1 0: Risultati del grupp o d i q uery eseguite su IPUMS 50 0K ..
IPUM S 1M IDX
QUERY
Tempi
ORACLE
(secondi)
Tempi
NEO4J
(secondi)
Num.
Elem.
Output
JOIN
Oracle
N°
HOP
(Neo4j)
Predicato
di
Selettività
Rapporto
Tempi
1
2
3
3,6099
3,2853
3,4696
29,269
26,021
17,651
5
3
1
1
1
1
3
3
3
0,5
0,3
0,1
8,11
7,92
5,09
Tab ella 3.1 1: Risultati del grupp o d i q uery eseguite su IPUMS 1 M IDX .
IPUM S 1M
QUERY
Tempi
ORACLE
(secondi)
Tempi
NEO4J
(secondi)
Num.
Elem.
Output
JOIN
Oracle
N°
HOP
(Neo4j)
Selettività
Rapporto
Tempi
1
2
3
1,7755
2,017
1,7316
240,319
174,462
118,466
5
3
1
1
1
1
3
3
3
0,5
0,3
0,10
135,353
86,496
68,414
Tab ella 3.1 2: Risultati del grupp o d i q uery eseguite su IPUMS 1 M ..
I r isultati co nfer mano quello che è stato d etto in preced enza. A p arità
d el numer o d i Jo in da p arte d i Oracle e Ho p d i Neo4j, al diminuire del
pr ed icato d i selettività d iminuisce anche il rappo rto d ei temp i, o vvero
Neo 4j no n solo miglio ra le proprie performance q ualora si effettua una r icer ca mirata, ma r isulta avere un appro ccio p iù efficacie d i q uello utilizz ato d al pro prio r ivale.
69
I seguenti gr afici p er metto no di farsi un’idea miglio re.
12
R
11
a 10
p
9
p
8
o
7
6
r
5
t
4
o
Rapporto Tempi
(Predicato di Selettività)
1
10,697
8,108
IPUMS 500K IDX
IPUMS 1M IDX
2
8,575
7,920
3
6,437
5,087
Query
Figur a 3.4 : Grafico che mo stra il rappo rto d ei temp i d elle q uery esegu ite su IP UMS 500 K I DX e IP UMS 1M IDX.
R
a
p
p
o
r
t
o
160
140
120
100
80
60
40
20
IPUMS 500K
IPUMS 1M
Rapporto Tempi
(Predicato di Selettività)
1
61,050
135,353
2
47,668
86,496
Query
3
36,154
68,414
Figur a 3.5 Gr afico che mo str a il rapp orto dei temp i d elle q uery eseguite
su IPUMS 50 0K e IPUMS 1 M .
E’ d a no tare che, i valori d ei rapporti dei temp i d ei database in cui no n
vi so no ind ici so no mo lto p iù alti risp etto a q uelli in cui so no presen ti.
Questa so stanziale d iffer enza d ip ende dal fatto che per le q uery Cyp her
scritte p er le basi d ati in cui so no stati co struiti gli ind ici, è stata imp ieg ata la clauso la ST ART. I meccanismi d i q uesta clausola so no uno dei ma ggiori p unti di for za di Neo4j.
70
I noltr e, nel pr imo grafico , i rapporti d ei temp i del d atabase IPUMS 1M
I DX so no p iù b assi rispetto a q uelli d el suo fratello p iù p icco lo IPUMS
50 0K I DX. I nvece, nel gr afico che ripo rta i valori d ei rappo rti dei temp i
d ei d ue database senza ind ici avviene esattamente il co ntrario.
Questo
co mpo rtamento d ip end e semp re dal fatto che, per uno so no state imp iegate
d elle q uer y munite della clauso la ST ART, p er l’altro no. Ciò sta signific ar e che, la clausola ST ART no n solo co nsente di miglio rare le prestazio ni,
ma co nsente a Neo4j di scalare efficacemente. Co munq ue, ind ifferent emente d alla clausola START , il Grap h DBMS risulta essere p iù efficacie
o gniq ualvo lta ti tenta d i recuperare un p icco lo so tto grup po d i dati su cui
po i o per ar e.
3.3.2 N° di Join di Oracle
I L seco ndo gr uppo d i q uery è stato sviluppato con lo scopo di verificare
se
Neo4j
guadagna
realmente
terreno
nei
co nfro nti
di
Oracle
all’aumentar e dello stesso numero d i join da p arte dell’RDBMS, e hop da
p ar te d el Grap h DB MS. Per evitare che altri fattori p o tessero influire sul
co mpo rtamento d ell’inter ro gazio ne e d i co nseguenza sui temp i di esec uzio ne, le q uer y del seco ndo grupp o so no caratterizzate d a aggregazio ni che
inter essano so lamente il livello p iù basso d i sp ecializzazio ne delle tabelle
d imensio nali, o vver o le Città p er i luo ghi, la Razza p er l’etnia, e co sì via.
Esemp io :
SELECT C.IDCITY, R.IDRACE, sum(FT.PERWT)
FROM FACT500K FT, RACE R, CITY C
WHERE R.IDRACE = FT.RACED
AND C.IDCITY = FT.CITY
GROUP BY C.IDCITY, R.IDRACE;
Ser ver Neo4j co n indici
START c=node:CityIdx("CITY:*")
MATCH (c)<--(f:Census)-->(r:Race)
RETURN id(c), id(r), sum(f.PERWT);
Server Neo4j senza ind ici
MATCH
(c:City)<--(f:Census)-->(r:Race)
RETURN id(c), id(r), sum(f.PERWT);
71
La seguente tab ella mo str a le caratteristiche princi p ali delle q uery.
ID
Aggregazioni
N° Join
Oracle
Descrizione
1
City
1
Join tra FACT e CITY
2
City, Race
3
Join tra FACT e CITY
Join tra FACT e RACE
3
City, Race,
Occupation
3
Join tra FACT e CITY
Join tra FACT e RACE
Join tra FACT e
OCCUPATION
Tab ella 3.1 3: Car atteristiche d elle interro gazio ni.
IPUM S 500K IDX
QUERY
Tempi
ORACLE
(secondi)
Tempi
NEO4J
(secondi)
Num.
Elem.
Output
1
2
3
2,1544
3,223
27,7889
20,539
1077
54,186 22740
197,094 347735
JOIN
Oracle
N°
HOP
(Neo4j)
Predicato
di
Selettività
Rapporto
Tempi
1
2
3
1
2
3
1
1
1
9,53
16,81
7,09
Tab ella 3.1 4 : Risultati del gr upp o d i q uery eseguite su IPUMS 50 0K.
IPUM S 500K
QUERY
Tempi
ORACLE
(secondi)
Tempi
NEO4J
(secondi)
Num.
Elem.
Output
1
2
3
1,7768
2,5381
28,4372
51,495
1077
80,5329 22740
225,264 347735
JOIN
Oracle
N°
HOP
(Neo4j)
Predicato
di
Selettività
Rapporto
Tempi
1
2
3
1
2
3
1
1
1
28,98
31,73
7,92
Tab ella 3.1 5: Risultati del gr upp o d i q uery eseguite su IPUMS 50 0K.
IPUM S 1M IDX
QUERY
Tempi
ORACLE
(secondi)
Tempi
NEO4J
(secondi)
Num.
Elem.
Output
JOIN
Oracle
N°
HOP
(Neo4j)
Predicato
di
Selettività
Rapporto
Tempi
1
2
3
3,245
3,8145
31,6489
48,661
93,147
324,34
1077
30166
550430
1
2
3
1
2
3
1
1
1
14,99
24,12
10,25
Tab ella 3.1 6 : Risultati del gr upp o d i q uery eseguite su IPUMS 1 M I DX.
72
IPUM S 1M
QUERY
Tempi
ORACLE
(secondi)
Tempi
NEO4J
(secondi)
Num.
Elem.
Output
1
2
3
1,7359
2,5913
33,5415
100,839 1077
149,245 30166
387,146 550430
JOIN
Oracle
N°
HOP
(Neo4j)
Selettività
Rapporto
Tempi
1
2
3
1
2
3
1
1
1
58,09
57,60
11,54
Tab ella 3.1 7 : Risultati del grupp o d i q uery eseguite su IPUMS 1 M.
Anche in q uesto caso i risultati co nfermato q uello che è stato detto ne lla discussio ne dei r isultati d ella sezio ne 3.2 . All’aumentare del numero d i
Jo in che Oracle deve effettuare per o ttenere il risultato richiesto d alla q u er y, e a p ar ità d i hop d i cui è co mp o sto il pattern d ell’interro gazio ne C yp her, il rapp or to d ei temp i cala.
I seguenti gr afici co nsento no di app rezzare meglio q uesto fatto.
Rapporto Tempi
(N° Join Oracle)
30
R
a
p
p
o
r
t
o
25
20
15
10
5
IPUMS 500K IDX
IPUMS 1M IDX
1
9,534
14,996
2
16,812
24,419
N° Join Oracle
3
7,093
10,248
Figur a 3.6 : Grafico che mo stra il rappo rto d ei temp i d elle q uery esegu ite su IP UMS 500 K I DX e IP UMS 1M IDX .
73
Rapporto Tempi
(N° Join Oracle)
R
a
p
p
o
r
t
o
70
60
50
40
30
20
10
0
IPUMS 500K
IPUMS 1M
1
28,982
58,090
2
31,730
57,595
3
7,921
11,542
N° Join di Oracle
Figur a 3.7 : Grafico che mo stra il rappo rto d ei temp i d elle q uery esegu ite su IP UMS 500 K e IPUMS 1M.
Anche se tend enzialmente r isultata vero ciò che è stato d etto in preced e nza, si nota l’imp ressio na nte imp ennata d ei rap porti d ei temp i d elle q uery
n°5 , eseguita sui d atab ase in cui vi so no indici. Questo d rastico aumento
no n è d o vuto ad un peggior amento d a p arte d i Neo4j, il q uale risulta ma ntenere lo stesso co mp or tamento in tutti i casi, bensì è causa to d a il modo
co n cui Oracle affro nta l’esecuzio ne d i q uesta particolare interro gazione.
Per o gnuna, d elle tre quer y, eseguite sul basi d ati co n gli indici, Oracle
crea un p iano d i esecuzio ne che no n ha nulla che fare co n q uello delle a ltre. Al co ntrar io p er le q uer y eseguite sui database in assenza di indici
Oracle assume p iù o meno lo stesso app roccio per tutte e tre le interro g azio ni.
P iù p recisamente, accade che per i datab ase in cui no n vi so no ind ici,
Oracle esegue semp re i jo in in cascata accedendo a lle tab elle per mezzo di
un FULL SCAN, per ciò i join vengo no eseguiti senza l’ausilio d i ind ici
che co nsento d i raggiungere rapid amente i record da asso ciare. Ciò signif ica che il co sto d i esecuzio ne d i una q uery eseguita sui database senza ind ici, cresce linear mente co n l’aumentare dei join. Neo4j, invece, esegue le
op erazio ni d i asso ciazione dei d ati semp licemente percorrendo le relazioni
che co nnetto i var i nodi d ella base d ati, q uind i anche se no n ci so no ind ici
d i sup por to alla sue interro gazio ni, rie sce co munq ue ad effettuare q uesta
op erazio ne in manier a o ttimale.
74
Nel caso dei database in cui so no stati co struiti gli ind ici la situazio ne
camb ia. P er la q uer y n°4 , Oracle no n d eve far altro che effettuare un Join
tra la tabella CITY e la tab ella FACT. Per fa ciò, usufruisce del NESTED
LOOP, po nendo co me relazio ne esterna la tabella d ei dati statistici e come
inter na
q uella
d elle
città,
p erò
prima
di
porle
in
join
effettua
l’aggregazio ne dei d ati d irettamente q uand o acced e alla FACT Tab le, e
sfr utta l’ind ice p er raggiungere rap id amente i record d ella tab ella dime nsio nale.
P iano di esecuzio ne q uery 4 :

SELECT STATEMENT
o HASH (GROUP BY)
o NESTED LOOPS (JOIN)

VIEW

HASH (GROUP BY)

TABLE ACCESS FULL – FACT TABLE

INDEX (UNIQUE SCAN) – CITY
NO TA: L’o per azio ne d i raggrupp amento effettuata q uando viene es eguito l’accesso seq uenziale alla tab ella dei FACT è un escamo tage di Or acle che gli co nsente di effettuare l’op erazio ne d i GROUP B Y senza do ver
p erò pr ima accedere alla tabella delle città. Ovvero , Oracle è talment e “intelligente” da cap ir e che, raggrupp are per IDCITY della tabella CITY , o p p ure per la chiave CITY d ella tab ella d ei FACT è la stessa co sa, p erciò d ecid e d i creare un vista intermedia co n già i dati raggruppati per IDCITY.
I n effetti il co sto d ella q uer y risulta limitarsi a q uesta o perazio ne di a ggr egazio ne e cr eazio ne della vista.
Quind i, a par te l’escamo tage del gro up b y, no n vi è nulla di strano. Il
co sto d ella q uer y per il d atabase IP UMS 500 K IDX è pari a 1339, invece
p er IP UMS 1 M I DX è 2548 .
Nel ca so d ella q uer y n° 5 , Oracle per evitare d i p erd ere co lp i do vuti al
crescer e d el numer o d i jo in decid e d i affro ntare la q uery co n un appro ccio
totalmente d iffer ente:
75
P iano di esecuzio ne q uery n°5 :

SELECT STATEMENT
o HASH (GROUP BY)
o MERGE JOIN

Sort (JOIN)

VIEW

HASH (GROUP BY)

HASH JOIN
o INDEX FULL SCAN - RACE
o TABLE ACCESS FULL – FACT TABLE

Sort (JOIN)
 INDEX (FAST FULL SCAN) – CITY
In q uesto caso , p rima viene effettuato il Join tra la tab ella FACT e la
tab ella RACE, dop o d i che viene eseguito il join tra il r isultato intermedio
nato d al pr ecedente join (a cui è stato effettuata una prima op erazio ne di
raggruppamento) e la tabella CITY, sula q uale è stato effettuato un accesso
rap ido via ind ice. P erciò Or acle no n esegue dei jo in in cascata, ma trova
altre alter native per evitare che d i inco mb ere nel problema che nasce dal
principio stesso d i Join tr a tabelle. Il co sto finale d ell’interro gazio ne è
26 65 p er IPUMS 500 K IDX, e 481 1 p er IP UMS 1M IDX.
P iano di esecuzio ne q uery n°6 :

SELECT STATEMENT
o HASH (GROUP BY)
o HASH JOIN

INDEX (FAST FULL SCAN) – OCCUPATION

VIEW

HASH (GROUP BY)

HASH JOIN
o INDEX FULL SCAN - CITY
o VIEW

HASH (GROUP BY)

HASH JOIN

INDEX FULL SCAN - RACE
 TABLE ACCESS FULL – FACT TABLE
Per q uanto r iguarda l’ultima delle tre q uery, la numero 6, avviene
l’inevitab ile. Ovver o Oracle no n p iù fare a meno d i po rre i jo in tra le t ab elle in cascata. I n q uesto caso si avrà un co sto d i 885 8 per IPUMS 500 K
IDX e 1757 6 p er IP UMS 1M IDX.
In definitiva, si p uò notare che finché il numero d i jo in è b asso, Oracle
riesce in q ualche mo do a co ntenere i co sti, q uando il numero diviene el evato , no n è p iù in grad o d i limitarli. Al co ntrario Neo4j, riesce in o gni c aso a co ntener e l’attr aversa mento del grafo so lo a q uei nod i e q uelle relazio ni che d avvero interessano la q uery, p er ciò riesce a guadagnare terreno
nei co nfro nti d ell’RDB MS.
76
3.3.3 N° Hop Neo4j
L’ultimo gr uppo è stato strutturato in mod o tale d a po ter stud iare q uanto il
nu mer o di ho p d i cui sono co mpo sti i p attern delle q uery Cyp her, po ssano
influire sulle per for mance. A q uesto sco po è stato scelto d i co ncentrare le
q uer y su un’unica dimensio ne, in q uesto modo le tre q uery d i cui è co mp o sto q uesto gr uppo, andranno a “to ccare” gli stessi Census, eliminando la
var iante d ella q uantità d i dati che le varie interro gazio ni andr anno ad
estr arr e. I noltr e, co n q uest’ultimo set d i q uery è po ssib ile anche studiare
co me r eagisce l a tecno logia No SQL, man mano che il livello d i aggreg azio ne aumenta.
ID
Aggregazioni
N° Hop
Neo4j
Descrizione
1
City
1
(City)<--(Census)
2
State
2
(State)<--(City)<--(Census)
3
Region
3
(Region)<--(State)<--(City)<--(Census)
Tab ella 3.1 8: Caratteristiche d elle interro gazio ni.
IPUM S 500K IDX
QUERY
Tempi
ORACLE
(secondi)
Tempi
NEO4J
(secondi)
Num.
Elem.
Output
JOIN
Oracle
N°
HOP
(Neo4j)
Predicato
di
Selettività
Rapporto
Tempi
1
2
3
2,1544
1,8901
2,2029
20,694
22,935
24,367
1077
52
10
1
1
1
1
2
3
1
1
1
9,61
12,13
11,06
Tab ella 3.1 9: Risultati del grupp o d i q uery eseguite su IPUMS 50 0K.
IPUM S 500K
QUERY
Tempi
ORACLE
(secondi)
Tempi
NEO4J
(secondi)
Num.
Elem.
Output
JOIN
Oracle
N°
HOP
(Neo4j)
Predicato
di
Selettività
Rapporto
Tempi
1
2
3
1,7294
1,494
1,9672
50,939
50,996
54,773
1077
52
10
1
1
1
1
2
3
1
1
1
29,46
34,13
27,84
Tab ella 3.2 0 : Risultati del grupp o d i q uery eseguite su IPUMS 50 0K.
77
IPUM S 1M IDX
QUERY
Tempi
ORACLE
(secondi)
Tempi
NEO4J
(secondi)
Num.
Elem.
Output
JOIN
Oracle
N°
HOP
(Neo4j)
Predicato
di
Selettività
Rapporto
Tempi
1
2
3
3,245
3,1327
3,0636
35,756
45,864
45,443
1077
52
10
1
1
1
1
2
3
1
1
1
11,02
14,64
14,83
Tab ella 3.2 1: Risultati del gr upp o d i q uery eseguite su IPUMS 1 M IDX.
IPUM S 1M
QUERY
Tempi
ORACLE
(secondi)
Tempi
NEO4J
(secondi)
Num.
Elem.
Output
JOIN
Oracle
N°
HOP
(Neo4j)
Selettività
Rapporto
Tempi
1
2
3
1,7359
1,6783
2,0982
97,454
103,225
105,909
1077
52
10
1
1
1
1
2
3
1
1
1
56,14
61,50
50,48
Tab ella 3.2 2 : Risultati del gr upp o d i q uery eseguite su IPUMS 1 M.
Per q uest’ultimo caso di studio è meglio affro ntare in mod o distaccato
la d iscussio ne dei r isultati d elle q uery che so no state eseguite sui d atabase
co n ind ici e q uelle no .
Da taba se co n ind ici
Il pro ssimo gr afico mo stra che all’aumentare d el numero di Ho p , d i cui
so no co mp o sti i patter n d elle q uery, cresce anche il rap porto d ei temp i.
Rapporto Tempi
(N° Hop Neo4j)
R
a
p
p
o
r
t
o
16
15
14
13
12
11
10
9
8
IPUMS 500K IDX
IPUMS 1M IDX
1
9,605
11,019
2
12,134
14,640
3
11,061
14,833
N° Hop
Figur a 3.8 : Grafico che mo stra il rappo rto d ei temp i d elle q uery e seguite su IP UMS 500 K I DX e IP UMS 1M IDX.
78
La cr escita è causata d a un so lo fattore : lo schema d i IP UMS d i Oracle
no n è no r malizzato, perciò l’RDB MS è d eve effettuare un so lo join per
tutte e tr e le inter ro gazio ni , inoltre in presenza di ind ici effettua q u esti
join in mo do o ttimale . T uttavia, è da no tare una caratteristica d ei risultati
o ttenuti. Ovvero, a nche se i rapporti dei temp i aumentano , la crescita non
co sì marcata, e le mo tivazio ni che so no alla base d i q uesto fatto so no 2.
P er prima co sa, le q u ery Ne o4j accedo no via ST ART clauso le ai no di d imensio nali, d ai q uali fanno partire l’attraversamento , e p er co struire d elle
interr o gazio ni che no n do vessero essere influenzate da altri fattori o ltre
q uello del caso di studio, è stato scelto di salire la struttura gerarchica di
una delle cinq ue dimensio ni . Questo significa che la prima q uery farà pa rtire la prop ria ricerca d ai 1112 nod i :City, la seco nda dai 53 d i tipo :State
e la terza d ai 1 0 :Region. Questo avvantaggia Neo 4j, proprio p erché man
mano che si sale la str uttura d iminuisco i nod i ancora d i p artenza.
I n seco ndo luo go, il mo tivo p er cui il rap porto d ei temp i cresce liev emente, interessa il pro cesso d i caching delle info rmazio ni p iù utilizzate.
Le q uer y, q uando vengono eseguite p er la prima volt a (o vvero in assenza
d i dati in me mo r ia cache) , p er fornire l’o utp ut devo no creare e caricare in
me mo r ia tutti gli o ggetti utili . Questo p rocesso di creazio ne e mantenime nto in me mo r ia centrale d i q uesti o ggetti è fo ndamentale affinché Neo4j
po ssa incr eme ntar e le prop rie prestazio ni al p resentarsi di successive r ichieste. Però se la mo le d i dati da do ver caricare è alta, si ha una d imin uzio ne della velocità di restituzio ne d ell’o utp ut. Ritornando al caso di st ud io, man mano che aumentano gli ho p d elle q uery si sale anche l’albero
gerarchico d ella dimensio ne, q uind i le interro gazio ni fornisco no un minor
nu mer o d i elementi di outp ut, perciò d evo no caricare in memo ria meno o ggetti, e d i co nseguenza è più rapid a la restituzio ne dell’o utp ut.
79
Da taba se sen za In d ici
Rapporto Tempi
(N° Hop Neo4j)
65
60
55
50
45
40
35
30
25
20
R
a
p
p
o
r
t
o
IPUMS 500K
IPUMS 1M
1
29,455
56,140
2
34,134
61,506
3
27,843
50,476
N° Hop
Figura 3.9 : Grafico che mo str a il rapp orto dei temp i delle q uery eseguite
su IPUMS 50 0K e IPUMS 1 M.
I risultati o ttenuti per i d atabase in cui no n vi so no gli indici mo strano un
camb io totale d i direzione. All’aumentare del numero di Hop d iminuisce il
rappo rto dei temp i. Questo accade perché il mo tivo per il q uale Neo4j p e rd eva ter reno , er ano i join di Oracle effettuati co n l’ausilio d egli ind ici.
Perd uti gli ind ici, Oracle è co stretto ad accedere alle tabelle p er mezzo d i
uno FUL SCAN T AB LE, perciò i sui jo in no n sono p iù ottimizzati. Al co ntrario Neo4 j, co ntinuerà ad r elazio nare i dati semp licemente attraversando
il grafo.
In definitiva, dai r isultati si p uò co nstatare che Neo 4j gestisce in mo do
eccellente gli attr aver samenti.
Le agg rega zion i
I rappor ti dei temp i ci per metto no d i co nstatare che maggiore è il live llo di aggr egazio ne, miglior e è la reazio ne d el la tecno lo gia No SQL. Questo
accad e per ché, le aggr egazio ni di alto livello tendo no a fornire meno el ementi di o utp ut, e co me è già stato rib ad ito diverse vo lte in p reced enza,
p iù è limitato l’o utp ut e miglio re è il temp o d i rispo sta del Grap h DB MS.
80
81
Capitolo IV
Conclusioni
I test eseguiti metto no in luce una serie di co mpo rtamenti di cui si è
amp iamente d iscusso nel pr ecedente cap ito lo d ei te st, tuttavia no n è stato
anco ra fatto notare l’aspetto p iù eclatante: l’enorme d ivario tra i temp i di
esecuzio ne d i Oracle q uelli d i Neo4j.
Questo abisso tr a i temp i d elle d ue tecno lo gie è do vuto alla base dati
imp iegata p er i test. IPUMS è un datab ase n ato è strutturato p er il mo ndo
OLAP – Relazio nale. Ciò significa che la struttura è stata co ncepita per far
fro nte ad o gni po ssib ile d ebo lezza d egli RDB MS. Un esemp io eclatante è il
fatto che le tab elle dimensio nali so no de normalizzate. Ino ltre è stato
str utturato p er poter eseguir e po che op erazio ni d i estrazio ne d elle info rmazio ni che inter essano grandi q uantità d i d ati alla volta. Al co ntrario,
Neo 4j è un DB MS transazio nale, q uindi nasce co n l’idea di gestire una
enorme mo le di tr ansazio ni che vanno a to ccare so lo un p icco lo so tto gru p po d i dati. Oltr etutto, non è un base d ati in cui le relazio ni ne fanno d a p adro ne, anche se è vero che ci so no 5 relazio ni p er o gni record della Fact
Tab le. T uttavia, le r elazio ni tr a le tab elle so no tutte d el tipo 1 a N. I Graph
DBMS so no
stati progettati per
far
fro nte al prob lema
che
nasce
d all’inter ro gare b asi d ati la cui struttura è co mp osta d a tante e grandi ent ità co nnesse da una vasta gamma di relazio ni d el tip o N a N. In poche p aro le IP UMS no n è un database altament e co nnesso , ma è l’esatto co ntrario .
Un altro ar go mento che è stato menzio nato raramente nei p reced enti
so tto -cap ito li, è la sca lab ilità . Dai risultati o ttenuti, si no ta che i rappo rti
d ei temp i delle q uer y eseguite sulle b asi d ati IPUMS da un milio ne d i C ensus, so no q uasi semp re p iù alti rispetto a q uelli ottenuti dai temp i di es ecuzio ne delle q uer y lanciate su IP UMS 500 K. Tutto ciò, ind icherebbe che
la cap acità d i Or acle nel gestire maggio ri info rmazio ni è miglio re risp etto
a q uella d i Neo4j. T uttavia, q u esto d ato ind ica so lamente che Oracle è in
grado d i scalare meglio all’aumentare d ella mo le d i informazio ni di cui è
co mpo sta la basi dati risp etto a Neo4j, so lo per questa tipo lo gia di d ata base.
82
Co me è stato d etto più e più vo lte in preced enza, IPUMS è u n d ateset nato
e str uttur ato p er il DBMS d ella tipo lo gia d i Oracle, q uind i risulta o vvio
che in q uesto caso , Or acle è in grado di scalare meglio risp etto a Neo4j.
I n gener ale, d ai risultati o ttenuti, no n è possibile affermare che gli
RDBMS siano in gr ado d i scalare si meglio rispetto ai Grap h DBMS, e v icever sa.
I n o gni caso , anche se i temp i di esecuzio ne so no a sfavore d ella tecn o lo gia No SQL, i rapp or ti d ei temp i co nfermano tutto ciò che viene d ichiar ato sulle potenzialità dei Grap h DBMS:
-
So no efficaci q u alo ra si effettua una ricerca mirata.
-
So no o ttimizzati p er percorrere le relazio ni che co nnetto no le i nfo r mazio ni.
Si co nsider i Ebay, il q uale sfrutta proprio Neo4j co me p iattaforma di
immagazzinamento e gestio ne dei d ati, e si co nsideri l’esemp io degli a r ticoli che vengo no p ropo sti ad un tip ico utente d ella p iattaforma web amer icana. Questa lista d egli articoli viene so litamente ricavata, dagli artico li
che ha ricercato in pr eced enza l’utente, d agli articoli asso ciati a tutti q ue lli che so no stati visio na ti dall’utente nelle preced enti ricerche e dagli art icoli della stessa categor ia che hanno suscitato l’interesse d ella maggior
p ar te degli utenti d i Ebay.
A un Gr ap h DBMS gli bastereb be ricercare il Nod o che rappresenta
l’utente d i interesse, effettuando co sì una ricerca mirata all’interno di
un’eno r me mo le d i info rmazio ni, e co ntare il numero maggiore d i relazio ni
che co nnetto no l’utente d i Eb ay agli articoli visio nati, per poi da li verif icar ne tutti gli altr i ar ticoli asso ciati e co ntemporaneamente, in b ase alla
catego ria d i ar tico lo , effettuare una stima d egli artico li co n il maggior n umer o di relazio ni che li co nnetto no ai no di utenti.
I nvece, un RDB MS do vrebb e mettere in jo in d iverse vo lte, la tabella
d egli articoli e q uella degli utenti, delle categ orie e co sì via, tutte tabelle
estr emamente gr and i in un co ntesto co me q uello d i Ebay, finendo per so cco mb ere.
Quind i, r isulta chiaro il perché q uesto nuo vo mo d o d i organizzare e
str utturar e le infor mazioni stia p rend endo pied e all’interno d ei grandi c olo ssi tecnolo gici.
83
84
Bibliografia
[1 ]
Wikipedia . ( http ://www. wi kip ed ia.it)
[2 ]
I an Robiso n, J im Wab ber. The Graph Da taba se . O’Reilly Med ia
I nc., 201 3.
[3 ]
Manu ale On lin e d i Neo4 j v2.0 M . ( Febbraio - Marzo 2014)
( http ://do cs.neo4j.org/chunked /stab le/)
[4 ]
M. Go lfarelli, S. Rizzi. Da ta Wa rehou se Design: Mo dern Princip les
an d Method olo gie s. McGraw-Hill, 20 09.
[5 ]
Sǎso D žero ski. J ŏ zef . Artico lo : Mu lti- Rela tiona l Da ta Mining: An
In trod uctio n . Stefan Institute Jamo va 39 , SI -1 000 Lj ublj ana, Slo v enia.
[6 ]
R. A. Elmasr i, S.B. Navathe. S istemi d i ba si d i da ti - Complemen ti .
Pear so n, 20 05.
[7 ]
NOS QL Data ba ses . http://www.no sq l -d atab ase.o rg/
[8 ]
Minneso ta Pop ulatio n Center . Integ ra ted pub lic use microda ta s eries (2008 ). http://www.i p ums.org
85

PREMIO

Fagiolata 2014.indd - Pro Loco

scarica il pdf - Mondo di bimbi

La pazza vestita da frate1 Da circa 5 anni era venuta a Roma ed

[Link] Donne con i piedi per terra

informazioni

Scarica PDF

Discorso del Santo Padre Francesco alla