Grafová terminologie a dostupné technologie

Tento seriál vás seznámí s grafovou databází Neo4j. V první řadě si představíme databázový systém spolu s jeho vlastnostmi, poté si popíšeme základní grafové pojmy a moderní termíny pro interpretaci grafů a také základy pro optimalizaci databázové části serveru.

Seriál: Grafová databáze Neo4j (4 díly)

  1. Grafová terminologie a dostupné technologie 21.10.2013
  2. Přehled grafových databází 8.11.2013
  3. Modelování dat v Neo4j – Metodika a obousměrné hrany 8.1.2014
  4. Webové rozhraní Neo4j 7.3.2014

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é
Příklad orientovaného grafu

Příklad orientovaného grafu

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

Příklady grafových stromů

Příklady grafových stromů

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.

Cache

Cache je označení pro vyrovnávací paměť, se kterou se v informatice můžeme setkat na mnoha místech, ať už jde o funkci webového prohlížeče, který využívá cache pro dočasné ukládání načtených stránek a jejich částí, tak i v problematice databází. Vždy s každou přijatou odpovědí dochází k rozhodnutí, zda budou data uložena, či nikoliv. Snažíme se tím předejít situacím, ve kterých by se pracovalo zastaralými nebo jinak nevhodnými daty. Zprovoznění cache spolu s její rozhodovací politikou omezí do značné míry komunikaci mezi klientem a serverem, což v důsledku posílí výkonu serveru.

Log

Log soubor zaznamenává informace o chování běhu programu. Typicky se jedná o obyčejný textový soubor s příponou .log. Úroveň obsáhlosti, tzv. jak a kolik detailních informací se bude ukládat, je povětšinou možné nastavit či úplně vypnout.

Pokračování příště

V dalším dílu uvedeme přehled grafových databází.

Zdroje

Článek původně vyšel na webu neo4j.cz.

Lidé se bojí monster a monstra se bojí Jaroslava Ramby. On je muž mála slov, ale když jde o činy, v jeho oboru se mu nikdo nevyrovná!

Věděli jste, že nám můžete zasílat zprávičky? (Jen pro přihlášené.)

Komentáře: 18

Přehled komentářů

diverman ok
Jaroslav Ramba Re: ok
KubajzHK super
bazinder chvalim vyber temy
Jaroslav Ramba Re: chvalim vyber temy
bazinder Re: chvalim vyber temy
Jaroslav Ramba Re: chvalim vyber temy
Michal Bachman Re: chvalim vyber temy
bazinder Re: chvalim vyber temy
Jaroslav Ramba Re: chvalim vyber temy
. Grafy jsou vhodným řešením pro grafové úlohy
Jaroslav Ramba Re: Grafy jsou vhodným řešením pro grafové úlohy
Radek Miček Chybějící definice
Jaroslav Ramba Re: Chybějící definice
Ladislav Thon
Jaroslav Ramba Re:
MilanLempera
Jaroslav Ramba Re:
Zdroj: https://www.zdrojak.cz/?p=10050