Předtím, než se pustíme do jakékoliv studie grafové databáze Neo4j, seznámíme se s několika dostupnými technologiemi a metodikami. Nejprve si představíme databázový systém spolu s jeho vlastnostmi a také si popíšeme základní grafové pojmy. V neposlední řadě si pohovoříme o moderních termínech pro interpretaci grafů a také o základech pro optimalizaci databázové části serveru.

NoSQL

Termín NoSQL vznikl jako pojmenování pro rodinu nerelačních datových úložišť, kde se velmi dlouho říkalo, že SQL (Structured Query Language) nepotřebujeme a nebudeme ho používat. Další konotací je NOSQL = Not Only SQL, kde se naopak nepojednává o alternativě, ale o dostupnosti dalších možností.

Na první pohled je rozdílem dotazovací jazyk, jak nám již prozradila rozprava nad názvem. Nadále oproti relačním databázím umožňují s příchodem nových trendů efektivněji zpracovávat data, jejichž vlastnosti neodpovídají tradičnímu relačnímu modelu.

Právě ACID neboli atomicita, konzistence, izolovanost a trvalost jsou hlavními principy relačního databázového modelu, avšak pro NoSQL systémy nejsou závazné, neboť výkon pro NoSQL databázi je podstatně důležitější než její konzistence. Jinak řečeno, mají jednodušší datový model než relační databáze, aby mohly garantovat škálovatelnost, dostupnost apod. Škálování typicky probíhá na horizontální úrovni v podobě přidání dalších serverů, což mimo jiné přináší výhodu odolnosti vůči chybám.

NoSQL vzniklo kvůli trendům

• vzrůstající objem dat
• rostoucí propojenost dat
• ztráta předvídatelné struktury
• současná architektura aplikací (aplikace mají více databází jako Cloud)

Graf

Obecný graf jako datová struktura nemá začátek ani konec. Je definován v podobě dvojice množin vrcholů (Vertices) a hran (Edges). Rozlišujeme grafy orientované a neorientované. Orientaci rozpoznáváme pomocí hran, které nám v grafu určují směr z daného vrcholu do dalšího.

• Vertices – neprázdná množina vrcholů (disjunktní s množinou Edges)
• Edges – množina hran (disjunktní s množinou Vertices)

Vrchol (Vertex)

Vrchol (někdy také uzel) je část grafové struktury, která nám zastupuje objekty nebo jejich referenci.

Hrana (Edge)

Hrana (někdy také vztah) znázorňuje konexe mezi jednotlivými vrcholy.

Základní typy hran

• neorientovaná hrana – neuspořádaná dvojice vrcholů, která nemá určený směr průchodu a hranou lze procházet oběma směry
• orientovaná hrana – uspořádaná dvojice vrcholů, která má určený směr průchodu a hranou lze procházet pouze vyznačeným směrem
• násobné hrany – více hran spojujících stejné vrcholy
• smyčka – hrana vedoucí z vrcholu do téhož vrcholu, tedy do sebe samotné

Strom

Stromem se nazývají souvislé grafy, které neobsahují kružnice. Po odebrání jedné z hran je porušena souvislost a přidáním vzniká kružnice. Hierarchickou strukturou je v teorii grafů přirovnáván k acyklickému grafu s jedním kořenem.

Kořen

Kořen stromu je nejvyšší uzel, který nemá žádného rodiče a je v grafu ojedinělý.

Grafová databáze

Grafové databáze jsou jednou z kategorií NoSQL, jak již bylo představeno v úvodu kapitoly. Z obecné definice lze označit za grafovou databázi jakýkoliv systém, který poskytuje tzv. bezindexovou sousednost, neboli každý vrchol obsahuje přímé odkazy na své sousedy a tím nám odpadá nutnost používání indexů.

Nativně ukládají grafové struktury, přičemž se eliminují všechny nepříjemné problémy s pokusy uložit graf (strom) do relační databáze, která je pro tyto účely nepřirozená, poněvadž se neobejde bez výpočetně drahých operací JOIN. Nadále jsou ideální pro mapování na objektovou strukturu aplikací bez rigidního modelu, což zaručuje volnost schéma libovolně rozvíjet. Naopak v porovnání relační databáze velmi dobře pracují s tabulárními daty, nad kterými jsou prováděny agregační a často se opakující úlohy.

Díky progresivitě sociálních projektů, kde nám velmi záleží na propojenosti mezi daty a následného data miningu, se stávají budoucností úložišť. Vesměs jsou vhodným řešením pro grafové úlohy, jako například hledání nejkratších cest či hledání komunit v sociální síti.

Traverzování

Traverzování neboli průchod nám umožňuje navštívit všechny vrcholy grafu. Celý proces si můžeme představit jako systematické putování grafem po jednotlivých vrcholech a hranách. Způsob, jakým je průchod realizován, určují zvolené algoritmy, jakými jsou například průchod do hloubky či do šířky .

Sociogram

V internetovém kontextu se jedná o social graph, což je grafické znázornění sociálních vztahů. Podle využití můžeme znázorňovat vztahy na základě různých kriterií, mezi ně lze zařadit sympatie, případně i antipatie nebo také vztahy vlivu, komunikace aj. Zpracování vlastností sociogramu bude jednou z částí výsledné grafové databáze, kde půjde o přátelství mezi uživateli.

Interest graph

Hlavní rozdíl oproti sociogramu spočívá v tom, že není požadovaná známost mezi uživateli, ale důležité je, jestli spolu sdílí nějaké zájmy. Výsledkem práce získáme graf, který bude obohacen o prvky zmíněného Interest graphu v podobě navštívených akcí nebo like stránek.

V dalším článku uvedeme přehled grafových databází.

Zdroje

• HOLÝ, J. (2012). Grafové databáze a neo4j.
• MAŠEK, J. (2012). Aplikace pro zpracování a ukládání sociálních vztahů (Diplomová práce). Fakulta informačních technologií ČVUT v Praze.
• HORDĚJČUK, V. (n.d.). Teorie grafů.
• LTD, W. I. S. I. P. (2012). Data Structures.
• ADAMCHIK, V. (2005). Graph Theory. Carnegie Mellon University.
• JIROVSKÝ, L. (n.d.). Stromy.
• ENCYCLOPEDIA. Graph database.
• TECHNOLOGY, N. (2013). Intro to Neo4j.
• ENCYCLOPEDIA. Social graph.
• ENCYCLOPEDIA. Sociogram.
• ENCYCLOPEDIA. Interest Graph.
• JIROVSKÝ, L. (2013). Orientované grafy.
• JIROVSKÝ, L. (2013). Stromy.