Nabídka práce od 2nddegreeleads.com

David Booth Founder and CEO projektu http://www.2nddegreeleads.com/, hledá šikovné programátory do svého týmu. Po diskuzi nad projektem vypadá, že noví členové se opravdu nudit nebudou! Základní dovednosti, které se pro vstup do projektu požadují:
  • Java -+ level developer (Komunikace s DB, design patterny a testy)
  • Neo4j DB
  • REST (API)
  • Chuť se učit a zápal do programování

Pokud Vás projekt zaujal, napište mně na jaroslav@ramba.cz nebo přímo Davidovi na booth.david@gmail.com. Good Luck!

První oficiální Neo4j Meetup v Praze

Srdečně zveme všechny zájemce o NoSQL, grafové databáze a Neo4j na první oficiální setkání v ČR, které se koná v rámci informatického večera na Fakultě informačních technologií ČVUT 11. listopadu 2013 v 18h. Vstup je zdarma.

Místo a čas

Pondělí 11. listopadu 2013, 18:00 – 19:30
ČVUT, posluchárna T9:107
Thákurova 9
160 00 Praha 6

Mapa

Program

90% všech dat na světě bylo vytvořeno v posledních dvou letech. Značně se také změnila struktura a zvýšila propojenost dat, které lidstvo generuje, zpracovává a ukládá. Důsledkem toho se zrodilo mnoho alternativ k relačním databázím, které se často souhrnně označují termínem NoSQL. Jednou ze čtyř kategorií NoSQL databází jsou tzv. grafové databáze, jejichž popularita v posledních měsících a letech rapidně vzrůstá.

Co jsou to grafové databáze a jaké problémy řeší? Jak se liší od relačních a ostatních NoSQL databází? V čem spočívají jejich výhody a nevýhody? Jaké je jejich reálné využití? Na tyto a další otázky odpoví trojice přednášejících.

V úvodu večera představí Michal Bachman populární open-source grafovou databázi Neo4j v kontextu NoSQL, její vlastnosti, výhody a slabiny, datový model a dotazovací jazyk Cypher.

Aleš Kropáč se poté podělí o svoje zkušenosti s jejím nasazením při zpracování dat získaných z NLP analýzy textů (propojení klíčových slov, entit a jejich vztahů), analýzy emailové komunikace, základní analýzy sociálních sítí a propojení různých SQL databází.

Jan Mittner na závěr pohovoří o tom, jak využívá grafovou databázi nejpopulárnější český web se spolujízdami, Jízdomat.cz, k posilování důvěry mezi uživateli.

Přednášející

Michal Bachman vystudoval Computing na Imperial College London, pracoval jako softwarový vývojář a konzultant v několika společnostech a nedávno založil v Anglii firmu GraphAware, která se zabývá poradenstvím v oblasti grafových databází.

Aleš Kropáč vystudoval učitelství matematiky a fyziky pro SŠ na MFF UK. Nyní pracuje ve společnosti Menier v Brně jako projektový manažer. Zabývá se projekty zaměřenými na zpracování textů a multimediálních dat.

Jan Mittner vystudoval informatiku na VŠE, kde v současné době působí jako lektor a doktorand. Je spolumajitelem společnosti Vergilio a zakladatelem projektu Jízdomat.cz, který se pyšní 70 tisíci uživateli a 160 tisíci zprostředkovaných spolujízd.

Metodika modelování grafové databáze

V následujících několika příspěvcích si ukážeme návrh, implementaci a testování grafové databáze Neo4j na projektu BestPartyToday (jedná se celosvětový pártylist, který nabízí detailní statistiky k akcím). V současné době se v projektu používá databáze MySQL, která obsahuje desítky milionů záznamů, takže nás také čeká přesunutí dat z relačního databázového úložiště do grafového. Ovšem v dnešním příspěvku si pouze namodelujeme podobu grafové databáze z vybraných tabulek a atributů současné struktury MySQL databáze.

O konceptuálním návrhu grafové databáze se pojednává jako o tzv. whiteboard friendliness (EIFREM, 2012). Pro rychlé promítnutí všech myšlenek a postřehů, které byly vzneseny během návrhového brainstormingu, postačí pouze flipchart. Výsledný nákres je velmi jednoduché následně prezentovat ostatním projektovým skupinám (retail department, accound managers, sales managers atd.), které nemají technické vzdělání. Pochopení návrhu pro ně už není překážkou, jelikož nákres je možné jednoduše přizpůsobit do podoby reálného života.

 

whiteboard graph model

Realizace konceptuálního modelu

Na fotografii finálního návrhu grafové databáze pro projekt BestPartyToday je využito pěti nejvýznamnějších tabulek současné relační databáze, které jsou reprezentovány ikonami znázorňující nodes a směrovými šipkami pro relationships. Skrze entity (nodes a relationships) budeme procházet graf a získávat požadovaná data, která budou zpracována a zobrazena uživateli aplikace. Jejich význam je popsán níže v tabulce Přehled entit grafového modelu.

Přehled entit grafového modelu

Tabulka relační databáze Entita grafové databáze Význam
users node člověk uživatel
friends relationship KNOWS vztah vyjadřující přátelství
events node budova akce
events_of_users relationship INVITED ztah vyjadřující typ účasti na akci
likes node stránka se znakem P stránka na Facebooku
likes relationship LIKES vztah vyjadřující like stránky

Zdroje:

EIFREM, E. (2012). Introduction to Neo4j [video]. Retrieved from http://www.youtube.com/watch?v=tyNWT85Z0mc

Přehled grafových databází

Sones GraphDB

Sones GraphDB je vyvíjena v jazyku C# německou společností Sones. Navrženou strukturou se přirovnává k váženému grafu. Jinými slovy se jedná o graf s hranami ohodnocenými reálnými čísly.

Databázi lze provozovat jak na platformě běžící pod Microsoft .NET frameworkem, tak Mono, která zajistí její multiplatformnost. Nadále i jako SaaS (Software as a Service) na cloudové platformě Microsoft Azure nebo Amazon S3, což přináší mnohonásobně větší výkon. Pro přístup k datům je možné využít jedno z mnoha rozhraní (např. Java, C#, WebShell, WebDAV), k nimž se řadí i REST API (Representational State Transfer Application Programming Interface), které nám zaručí nekomplikovaný přístup vzhledem ke zvoleným technologiím aplikace.

Při výběru máme možnost volby ze dvou licencí, pod kterými je GraphDB dostupná. První z nich je open source AGPLv3 (Affero General Public License, version 3) komunitní verze, která nemá tak širokou škálu nabízené funkčnosti jako enterprise verze.

AllegroGraph

AllegroGraph je proprietární produkt tvořený vývojáři Franz, Inc. Návrh databáze je uzpůsoben tak, aby splňoval standardy W3C (World Wide Web Consortium) pro Resource Description Framework, neboli je určen pro manipulaci s propojenými daty a sémantickým webem.

Nabízí početný seznam knihoven pro komunikaci přes REST API s aplikacemi psanými např. v C#, Perl, Ruby a Scala.

Licenční politika popisuje tři verze — Free, Developer a Enterprise, kde první dvě jsou omezeny počtem záznamů v databázi. Mezi širokou klientelu se řadí velikáni jako Ford, Kodak a NASA (National Aeronautics and Space Administration).

Neo4j

Neo4j je jedna z nejpopulárnějších grafových databází ve své kategorii, což implikuje open source řešení, které je implementované v Javě. Pochází z dílny společnosti Neo Technology, kde byla první verze vydána v roce 2007 a od té doby získala celkem velké zastoupení ve vývojářské komunitě, která se nejenom zapojuje do běžných diskuzí https://groups.google.com/group/neo4j, ale i do samotného vývoje https://github.com/neo4j.

Ukládání grafové struktury je v podobě vrcholů, hran a vlastností, pro něž platí limity v řádech desítek miliard. Properties jsou další přidanou hodnotou, kterou může obsahovat každý vrchol nebo hrana v podobě klíč–hodnota. Mluvíme o tzv. property graph database.

Neo4j může být použita buď jako embedded mode (Java, JAR) (Java Archive), nebo jako standalone mode, pomocí kterého můžeme k databázi plnohodnotně přistupovat skrze REST API rozhraní.

FlockDB

FlockDB je tvořena Twitterem pod licencí Apache License, Version 2.0 pro účely analytiky souvisejících vztahů, přičemž doposavad nebyl vyvinut stabilní release. Michael Marr shrnul hlavní rysy FlockDB ve svém článku pro portál DevWebPro:

The biggest difference between FlockDB and other graph databases like Neo4j and OrientDB is graph traversal. Twitter’s model has no need for traversing the social graph. Instead, Twitter is only concerned about the direct edges (relationships) on a given node (account). For example, Twitter doesn’t want to know who follows a person you follow. Instead, it is only interested in the people you follow. By trimming off graph traversal functions, FlockDB is able to allocate resources elsewhere.

Načež mu hned bylo oponováno, že bez traverzovaní se nejedná o grafovou databázi, ale pouze o tzv. persisted graph.

Ať už se podle definic jedná o cokoliv, od FlockDB můžeme čekat velké věci. Mimo zmiňované cíle se profiluje dalšími, jako je maximální podpora pro operace add/update/remove. Nadále také obsažnost množiny aritmetických funkcí je další atypičností v prostředí grafových databází. Kromě toho dokáže stránkovat výsledky dotazů, které obsahují miliony záznamů. A v neposlední řadě podporuje horizontální škálování s replikací či online migrací dat.

InfiniteGraph

Grafová databáze je implementovaná v jazyce Java (mimo jádro v C++) od Objectivity, kde samotný název společnosti koreluje se strukturou databáze, která je objektově orientovaná. Skládá se z objektů (v grafové terminologii považován za vrchol) a hran pro jejich vzájemné propojení. Prozatím bohužel není možné přistupovat k databázi skrze REST API a je nám nabízeno pouze rozhraní v Javě.

Licence pro použití databáze jsou nabízeny ve dvou variantách. Bezplatná s sebou nese značné limity, jako omezení počtu hran a vrcholů po uplynutí 60denní zkušební verze. Nicméně mezi jedny z hlavních klientů patří vláda Spojených států amerických a poradenská společnost Deloitte.

Shrnutí

Výběr se může zdát “uměle zkreslený” při pohledu na název seriálu, ale přeci jen svými vlastnostmi nejvíce vyhovuje Neo4j, která mimo jiné přesvědčila i značnou komunitou v pozadí a jejím agilním vývojem. Také podpora REST API, které nám umožní snadnou integraci do projektu vyvíjeného v PHP, se jeví jako ideální řešení.

Zdroje:

Grafová terminologie a dostupné technologie

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

Hello world NoSQL Style!

Jmenuji se Jaroslav Ramb(a)o. Bohužel nejsem tím slavným akční hrdinou, kterému jsem pyšným jmenovcem. Ovšem vydal jsem profesí velmi blízkou a tím je IT. Mám rád zábavu, společnost a zajímám se o vývoj, databáze a algoritmy. Na tomto blogu se můžete těšit na palbu článků o databázi Neo4j a mnoho dalšího, co s tím souvisí.