Sémantické technologie: Grafové databáze

Grafové databáze

Graf je datová struktura skládající se z vrcholů a hran. Grafová databáze je systém na ukládání a zpracování dat v podobě grafu. V mnoha případech je modelování domény grafem velmi přirozené – mezi takové domény patří vztahy mezi lidmi, mezi geny a proteiny, mobilní sítě, distribuční sítě různého druhu, neuronové sítě nebo třeba ekologické sítě zachycující interakce organismů.

Mezi grafové databáze se často řadí různé systémy, které spravují data v podobě grafů. Na základě takovéto definice by bylo teoreticky možné pohlížet i na relační databáze, resp. na jejich nadstavby jako na grafové databáze. Relační databáze ovšem neumožňují efektivní uložení a dotazování grafových dat.

Relační databáze

Průchod grafem v relační databázi vyžaduje joiny, a je tedy neefektivní pro průchod do hloubky. Jeden join za použití indexu vyžaduje logaritmický čas O(log n), bez použití indexu je to O(n log n).

Například vztahy mezi lidmi můžeme modelovat pomocí dvou tabulek: Člověk a Vztah. Pro každý průchod vztahem mezi dvěma lidmi obecně potřebujeme jeden join. Tradiční relační databáze jsou optimalizovány pro jednotky joinů. Jakmile počet joinů přejde do desítek, dostávají se relační databáze do potíží i přes použití indexů.

Opravdové grafové databáze

Opravdovými grafovými databázemi nazveme pro účel tohoto článku takové databáze, které vyžadují pouze konstantní čas O(1) pro průchod hranou grafu.

Opravdové grafové databáze, podobně jako jiné NoSQL databáze, ukládají data v denormalizované (již „zjoinované“) podobě. U opravdové grafové databáze se tedy platí především u zápisu, zatímco dotazování (čtení) je levnější.

Příkladem opravdové grafové databáze je systém Neo4j, který je ve vývoji již více než deset let a je dostatečně vyspělý pro produkční nasazení, nebo například novější systém OrientDB.

Příkladem databází, které jsou schopné ukládat a dotazovat data v podobě grafů, ale ne nutně efektivně procházet grafy, je většina triplestorů (Sesame, Jena, Virtuoso) nebo FlockDB (projekt Twitteru).

Podobně jako je tomu u většiny NoSQL databází, ani pro grafové databáze neexistuje jednotný dotazovací jazyk. Nicméně mnoho grafových databází implementuje jazyk na procházení grafů Gremlin vytvořený ve spolupráci s autory Neo4j.

Neo4j

Grafová databáze Neo4j původně vznikla jako školní projekt několika studentů ve Švédsku a od té doby se rozrostla do vyspělého produktu, který používají společnosti jako Lufthansa, Adobe nebo Cisco.

Fulltextové vyhledávání ve vrcholech a hranách je usnadněno integrací Lucene indexů, které lze využívat přímo přes Neo4j API. Lucene index je možné s výhodou použít také pro zrychlení práce s tzv. supernodes, což jsou vrcholy, které mají více než například 100 000 hran.

Pro high-availability řešení je v současné verzi (1.8) používán model multiple master single slave. Pro verzi 2.0 je v plánu lepší podpora shardování grafu. Shardování je způsob, jak rozdělit databázi mezi více strojů. V případě grafu je to obzvláště náročný úkol, protože většinou není předem jasné, jakou strukturu bude graf mít, a tedy jak ho co nejefektivněji rozdělit.

Některé jiné grafové databáze jsou od začátku navrženy pro distribuované nasazení. Například FlockDB Twitteru je distribuovaná grafová databáze, která ovšem funguje jako úložiště matice sousednosti grafu, a tedy nepodporuje efektivní procházení grafem, jež by vyžadovalo nějakou obdobu joinu z relačních databází.

Škálování

Přestože grafové databáze nemají díky problematickému shardování škálování snadné, existuje už několik systémů, které se zaměřují na big data grafy. Jedním takovým systémem je například poměrně nový Titan, který podporuje několik různých back-endů a implementuje jazyk Gremlin, nebo systém Pregel, který Google oznámil už v roce 2009.

O grafové databázi je dobré přemýšlet jako o užitečném indexu, který zprostředkovává přístup k datům za pomoci průchodu grafem.

Každopádně grafová databáze stojí za vyzkoušení a při aplikování na správný problém může být velkou úlevou. Neo4j je open-source  a zdarma pro nekomerční použití (AGPL). V Česku Neo4j používá například startup Proactify.

Autor je research engineer v Deri Galway a SindiceTech