Okrem pomerne štandardných spôsobov ukladania dát do databázy typu SQL, prípadne noSQL existujú ešte aj iné, menej známe typy ukladania dát. Jedným z nich, ktorý si dnes v skratke rozoberieme sú grafové databázy. Konkrétne sa pozrieme na grafovú databázu Neo4J.
Grafové databázy ukladajú dáta vo forme grafu. Nejedná sa o graf, ktorý poznáme napr. z Excelu :) ale ide o matematickú reprezentáciu grafu.
Graf je abstraktný matematický objekt daný množinou vrcholov V (starší názov:uzly) a množinou hrán E medzi dvojicami vrcholov. Grafy študuje matematická disciplína teória grafov a sú obvykle abstrakciou reálnych problémov či štruktúr. Typickým príkladom je modelovanie cestnej siete ako grafu, kde vrcholy sú mestá a hrany zastupujú cesty.
Ako to už zvyčajne pri dátach býva, tento typ reprezentácie dát je vhodný len v niektorých konkrétnych situáciách. Nedá sa povedať, že je univerzálne vhodný v každej situácii. Vhodný je práve na údaje, medzi ktorými sa nachádza určitý vzťah. Ako príklad si môžeme uviesť napr. rodostrom. V ňom uzly reprezentujú konkrétny ľudia a hrany medzi uzlami sú informácie, kto je v akom príbuzenskom vzťahu s kým. Ja som si ale ako dnešný priklad zvolil iná scenár: Osoby, spoločnosti v ktorých pracujú a mestá, v ktorých sa tieto spoločnosti nachádzajú. Nech máme trochu väčšiu variabilitu typov uzlov a hrán. Príklad grafu:
Už z rýchleho pohľadu na graf je možné identifikovať entity a vzťahy medzi nimi. Juraj, Marek a Vojtech pracujú v spoločnosti bart.sk, Anna a Zuzana v spoločnosti Ness a Robert, Mária, Milan, Peter pracujú v spoločnosti IBM. IBM aj NESS spolupracuje s bart.sk, ale nespolupracujú navzájom. Bart.sk, Ness aj IBM sa nachádzajú v Košiciach, IBM sa okrem toho nachádza aj v Bratislave.
Keby sme chceli podobnú štruktúru dát uložiť v SQL databáze, potrebovali by sme vytvoriť samostatnú tabuľku pre každý typ uzla a následne pre každý vzťah typu Many-to-Many ďalšie tabuľky. Na vyhľadanie napríklad toho, ktorý ľudia pracujú v spoločnosti, ktora sa nachádza v Košiciach by sme potrebovali napísať dosť komplexný dotaz, ktorý by JOINoval veľké množstvo tabuliek.
V grafovej databáze to vieme spraviť veľmi jednoduchým a na prvý pohľad ľahko čitateľným dotazom:
[pastacode lang=“markdown“ manual=“MATCH%20(a)-%5Br%3APRACUJE_V%5D-%3E(b)-%5Bp%3ANACHADZA_SA%5D-%3E(c)%0AWHERE%20c.name%20%3D%20’Kosice’%0ARETURN%20a.name%2C%20c.name“ message=““ highlight=““ provider=“manual“/]
Dotaz nájde všetky osoby a, ktoré pracujú v spoločnosti b, ktoré sa nachádzajú v meste c, pričom mesto c musí byť Košice. Dotaz je nielen jednoduchý na čítanie ale aj extrémne rýchly na vykonanie. Keďže grafové databázy sú optimalizované na takéto použitie tak si vedia poradiť aj s miliónmi uzlov a ešte väčším počtom hrán.
Neo4j
Neo4J patrí medzi najznámejšie a najpopulárnejšie grafové databázy. Vydaná bola v roku 2007. Na prácu s databázou sa používa dopytovací jazyk Cypher. Príkazy sa dajú posielať buď cez HTTP protokol ako REST alebo cez binárny protokol bolt.
Jazyk Cypher bol navrhnutý špeciálne pre Neo4j pričom využíva prvky známe z SQL a teda, kto vie pracovať s SQL, nebude mať problém si tento nový dopytovací jazyk osvojiť.
Vytváranie uzlov a hrán
Uzly vieme vytvárať pomocou príkazu CREATE. Pri vytváraní vieme zadať typ uzla a jeho vlastnosti. Napríklad príkaz:
[pastacode lang=“markdown“ manual=“CREATE%20(n%3APerson%20%7B%20name%3A%20’Andy’%2C%20age%3A%2028%20%7D)“ message=““ highlight=““ provider=“manual“/]
Vytvorí nový uzol typu Person a nastaví mu meno Andy a vek 28.
Hrany medzi uzlami vieme tiež vytvoriť príkazom CREATE. Buď vytvoríme rovno aj nové uzly alebo použijeme existujúce.
[pastacode lang=“markdown“ manual=“MATCH%20(a%3APerson)%2C(b%3APerson)%0AWHERE%20a.name%20%3D%20’A’%20AND%20b.name%20%3D%20’B’%0ACREATE%20(a)-%5Br%3ARELTYPE%5D-%3E(b)“ message=““ highlight=““ provider=“manual“/]
Tento príkaz vytvorí novú hranu typu RELTYPE medzi existujúcimi osobami s menom A a B.
Vyhľadanie uzlov / hrán
Uzly a hrany vieme vyhľadať príkazom MATCH. Jednoduchý príklad na nájdenie uzla typu Person s menom Peter:
[pastacode lang=“markdown“ manual=“MATCH%20(n%3APerson)%0AWHERE%20n.name%3D%22Peter%22%0ARETURN%20n“ message=““ highlight=““ provider=“manual“/]
Hrany vieme tiež vyhľadať veľmi jednoducho. Napríklad nasledujúci príkaz nájde hrany (vzťahy) medzi osobami Peter a Jano:
[pastacode lang=“markdown“ manual=“MATCH%20(n%3APerson)-%5Br%5D-%3E(m%3APerson)%0AWHERE%20n.name%3D%22Peter%22%20AND%20m.name%3D%22Jano%22%0ARETURN%20r“ message=““ highlight=““ provider=“manual“/]
Nastavenie indexov
Ako každý databáza, aj Neo4j umožňuje nastaviť indexy, ktoré následne urýchľujú dotazy. Indexy sa nastavujú pre konkrétne vlastnosti uzlov. Keď je uzol napr. typu Person, tak index môže byť napríklad na vlastnosti name, wage, age. A následné dotazy ktoré pracujú s menom, platom alebo vekom osoby môžu byť týmito indexami urýchlené. Samozrejme treba indexy nastaviť rozumne, len tam, kde sú naozaj potrebné, lebo každý index zvyšuje nároky na úložisko ako aj čas pri zápisoch a úpravách uzlov.
Index je možné vytvoriť jednoducho príkazom:
[pastacode lang=“markdown“ manual=“CREATE%20INDEX%20%5Bindex_name%5D%0AFOR%20(n%3ALabelName)%0AON%20(n.propertyName)“ message=““ highlight=““ provider=“manual“/]
Keď chceme index vytvoriť pre viac hodnôt v rámci jednej entity tak použijeme príkaz:
[pastacode lang=“markdown“ manual=“CREATE%20INDEX%20%5Bindex_name%5D%0AFOR%20(n%3ALabelName)%0AON%20(n.propertyName_1%2C%0A%20%20%20%20n.propertyName_2%2C%0A%20%20%20%20%E2%80%A6%0A%20%20%20%20n.propertyName_n)“ message=““ highlight=““ provider=“manual“/]
Nájdenie najkratšej cesty v grafe
Nájdenie najkratšej cesty v grafe je veľmi častý problém v rámci teórie grafov. Príkladov použitia môže byť hneď niekoľko. Napríklad nájdenie najkratšej cesty medzi dvoma mestami alebo zistenie koľko ľudí na Facebooku sa nachádza medzi mnou a prezidentom USA. V prípade nájdenia najkratšej cesty medzi mestami sa jedná o tzv. ohodnotený graf. To je graf, ktorého hrany majú definovanú nejakú číselnú hodnotu, napr. počet kilometrov.
Na druhý príklad, nájdenie najmenšieho počtu spojení medzi 2 ľuďmi na FB stačí neohodnotený graf, respektíve každé prepojenie medzi dvoma spriatelenými ľudmi na FB má hodnotu 1.
Neo4J nám umožňuje veľmi efektívnym spôsobom nájsť najkratšiu cestu medzi dvoma uzlami v grafe. Využíva na to dobre známy Dijkstrov algoritmus.
Príklad dotazu pre najkratšiu cestu:
[pastacode lang=“markdown“ manual=“MATCH%20(start%3ACity%7Bname%3A%22Bratislava%22%7D)%2C%20(end%3ACity%7Bname%3A%22Kosice%22%7D)%0ACALL%20algo.shortestPath.stream(start%2C%20end%2C%20%22cost%22)%0AYIELD%20nodeId%2C%20cost%0AMATCH%20(other%3ACity)%20WHERE%20id(other)%20%3D%20nodeId%0ARETURN%20other.name%20AS%20name%2C%20cost“ message=““ highlight=““ provider=“manual“/]
Nájdenie minimálnej kostry grafu
Nájdenie kostry grafu je ďalší z bežných problémov v oblasti grafov. Problém spočíva v tom, nájsť takú množinu hrán, že existuje medzi každou dvojicou vrcholov existuje práve jedna cesta. Minimálna kostra znamená, že súčet hodnôt hrán bude najmenší možný. Ako príklad si môžeme uviesť napríklad že chceme prepojiť všetky mestá na slovensku internetom, teda každá dvojica miest si medzi sebou bude vedieť poslať správu. Keď si ako hodnotu hrany určíme vzdialenosť tak minimálna kostra grafu bude znamenať, že vybudovaná sieť bude najkratšia možná a teda náklady na postavenie siete budú minimalizované.
Nájdenie minimálnej kostry ohodnoteného grafu v Neo4j:
[pastacode lang=“markdown“ manual=“MATCH%20(n%3APlace%20%7Bid%3A%22D%22%7D)%0ACALL%20algo.spanningTree.minimum(‚Place’%2C%20’LINK’%2C%20’cost’%2C%20id(n)%2C%0A%20%20%7Bwrite%3Atrue%2C%20writeProperty%3A%22MINST%22%7D)%0AYIELD%20loadMillis%2C%20computeMillis%2C%20writeMillis%2C%20effectiveNodeCount%0ARETURN%20loadMillis%2C%20computeMillis%2C%20writeMillis%2C%20effectiveNodeCount%3B“ message=““ highlight=““ provider=“manual“/]
Kde sme v praxi využili grafovú databázu
U nás v spoločnosti sme grafové databázy zatiaľ využili len pri pár príležitostiach. Najväčším projektom bolo asi vyhľadávanie kombinovaných leteniek medzi mestami. V grafovej databáze sme mali uzly typu: Mesto, Letisko, Let.
V jednom meste sa mohol nachádzať ľubovoľný počet letísk. Let mal spojenie s počiatočným letiskom a s koncovým letiskom. Problém spočíval v nájdení možných spojení medzi 2 mestami v ohraničenom termíne na maximálny počet prestupov. V aplikácii bolo potrebné počítať s tým aby mal pasažier nejaký minimálny čas na prestup (napr. 2h), nejaký maximálny čas prestupu (nech nestrávi na letisku celú mladosť) a zároveň aby bolo možné nájsť spojenia aj s prestupom v rámci rôznych letísk v jednom meste. A aby toho nebolo málo, bolo potrebné ešte zoradiť vyhľadané spojenia od najlacnejšieho po najdrahšie. :D Problém to bol teda dosť komplexný. Počet dát bol tiež dosť veľký, milióny letov a desiatky miliónov spojení. Aj tak si s tým ale Neo4J vedel poradiť veľmi dobre a pri menšom počte prestupov (napr. 3) bolo možné nájsť výsledky v časovom horizonte desiatok milisekúnd.
Danú štruktúru sme ani len neskúšali spojazdniť v SQL databáze ale viem si predstaviť, že by dané vyhľadanie nebolo možné realizovať v rozumnom časovom horizonte.
Sandbox
Ak si chcete vyskúšať prácu s Neo4J ale nechce sa vám nič inštalovať, tak môžete využiť sandbox. Na stránke https://sandbox.neo4j.com/ si viete na pár klikov vytvoriť vlastnú databázu a začať skúmať grafové databázy na vlastnú päsť. V prípade, že sa vám nechce vymýšľať dáta, môžete využiť niektorú z predvyplnených databáz, ktoré sú k dispozícii. Tieto databázy už priamo obsahujú uzly a hrany a teda nie j e potrebné strácať čas ich vytváraním. Ukážka zo sandboxu:
Záver
Ako sme si ukázali, grafové databázy určite majú svoje opodstatnenie a využitie. Pravdepodobne ich nevyužijete hneď na najbližšom projekte, ale minimálne je dobré vedieť, že niečo také existuje. A možno v budúcnosti natrafíte na situáciu, kde budú práve grafové databázy dávať najväčší zmysel.
