Magiczne sztuczki – grafowe bazy danych

Grafowe bazy danych nowym „hype” genialnego IT marketingu?

Praktycznie każda aplikacja której używamy wykorzystuje bazę danych. Wszyscy, a przynajmniej tak być powinno, słyszeliśmy o relacyjnych bazach danych i najczęściej obsługujących je uniwersalnym języku SQL. "Bazy relacyjne" gdyż dane są przechowywane w uporządkowanych ciągach wartości (inaczej „krotek”). Opisane tworzą rekordy i tabele z występującymi między nimi relacjami. Relacyjne bazy danych istnieją na rynku od lat 80tych i są bezwzględnie najczęściej używanym typem baz danych.

Jednak w latach dwutysięcznych pojawiły się nowe typy baz danych NoSQL z których z kolei wyrosły grafowe bazy danych (nie „graficzne” jak to często błędnie jest tłumaczone).

Większość baz danych NoSQL przechowuje zestawy luźnych agregatów (w postaci dokumentów lub par klucz-wartość) – brak relacji między danymi, co ma pozytywny wpływ na prędkość ich działania. Utrudnia to jednak łączenie danych. Jedną ze strategii dodawania relacji do takich danych jest osadzenie identyfikatora jednego dokumenty wewnątrz innego dokumentu. Wymaga to jednak połączenia agregatów/danych na poziomie aplikacji (skomplikowana obsługa).

Grafowe bazy danych odróżnia od baz NoSQL to że przechowują relacje wraz z danymi. Ponieważ dane są fizycznie połączone w bazie danych, dostęp do tych relacji jest tak szybki jak dostęp do samych danych. Innymi słowy zamiast obliczać relację jak w relacyjnych bazach danych, grafowe bazy danych po prostu odczytują relacje z pamięci.

Produktem który zdominował rynek grafowych baz danych jest teraz Neo4j - zobacz jak łatwo zacząć korzystać z tej bazy [kurs który wprowadzi Cię w świat grafów]. Jeśli chcesz dowiedzieć się więcej o współczesnych możliwościach grafowych baz danych a, co ważniejsze, szukasz inspiracji co Ty możesz uzyskać dzięki nim - przeczytaj nasze przykłady użycia. Napisaliśmy tam co do czego możesz użyć grafowej bazy w swoim biznesie. W firmie która nie jest drugim Google, Facebookiemy czy Microsoftem.

Czym są grafy?

W matematyce graf jest modelem struktury obiektów i relacji między nimi. Wykres składa się z wierzchołków (z angielskiego "vertex") zwanych również węzłami lub punktami, które są połączone krawędziami (z angielskiego "edges").

Rozróżnia się grafy nieukierunkowane, gdzie krawędzie łączą dwa wierzchołki symetrycznie i grafy skierowane, gdzie krawędzie łączą dwa wierzchołki asymetrycznie.

W praktyce większość baz grafowych używa tylko krawędzi ukierunkowanych – z wierzchołka A do B, tylko w jednym kierunku. Bazy grafowe mogą przemierzać relacje w obu kierunkach. Co ważniejsze, prędkość przejścia nie zależy od kierunku pokonywanych relacji.

Grafowe bazy danych to nie tylko piłeczki na ekranie

Osoby dla których temat grafów jest nowy mają często błędne wyobrażenie że grafowe bazy danych wyświetlają dane w postaci piłeczek i powiązań między nimi na ekranie. Taka wizualizacja danych jest rzeczywiście często stosowana ale (wtedy kiedy odbiorcą informacji jest człowiek nie inne oprogramowanie) ale nie jest jedyną. Dane mogą być prezentowane w postaci tabelarycznej - tak jak to się dzieje w relacyjnych bazach danych. Jeśli np. chcemy dowiedzieć się z jakimi klientami współpracujemy, możemy tę informację wyświetlić w postaci grafu ale możemy również uzyskać listę klientów (zapytanie w języku Cypher do bazy Neo4j):

Do czego mogę użyć grafowej bazy danych?

Zawsze rozpoczynaj swoje projekty od zadania sobie pytania "czego szukam w danych?". Nie ma na rynku produktów które by w magiczny sposób dostarczyły Ci informacje choć nie wiesz czego szukasz. I te pytania musisz zadać zarówno relacyjnej bazie danych jak i grafowej. Zarówno relacyjną jak i grafową bazę danych możesz wykorzystać praktycznie do wszystkiego - oba produkty przeznaczono do przechowywania danych i analiz. Ale tak jak wszystkie narzędzia, są takie które są dobre do wykonania jednej rzeczy i gorsze do zrobienia innej - młotek jest dobry do wbijania gwoździ ale wkręty lepiej wkręcić wkrętarką (choć młotkiem możesz to także zrobić).

Relacyjne bazy danych obsługują powiązania między danymi znajdującymi się w różnych tabelach co odpowiada relacjom w grafowych bazach danych. W obu bazach danych możemy uzyskać takie same informacje. Problem zaczyna się gdy tych powiązań jest zbyt dużo (JOINy). Relacyjne bazy danych źle radzą sobie ze zbyt dużą ilością JOINów. Z kolei grafowe bazy nie mają z tym żadnego problemu i liczba połączeń między danymi może być praktycznie nieograniczona.

W większości przypadków Twoja aplikacja, Twoje analizy opierają się na ustalonej strukturze danych, liczba atrybutów opisujących dane jest stała a liczba powiązań jest ograniczona. I to jest miejsce dla relacyjnej bazy danych. Choć grafowa baza danych obsłuży te potrzeby równie dobrze, jest ograniczony sens wprowadzania nowego systemu do otoczenia - choćby ze względu na koszty poznania nowego środowiska.

Gdzie jest miejsce na grafową bazę danych? Wszędzie tam gdzie występują potrzeby biznesowe lub techniczne, w których użytkownicy chcą zrozumieć relacje w swoich danych (ukryte i oczywiste) lub jeśli powiązań między danymi jest tak dużo że ich obsługa jest niemożliwa w tradycyjnej, relacyjnej bazie danych. Grafowe bazy danych są idealne do obsługi modelu danych który ciągle się zmienia, powstają nowe powiązania między danymi. W takim przypadku w relacyjnej bazie danych trzeba najczęściej zmienić strukturę tabel, utworzyć nowe klucze, indeksy. W grafowej bazie danych po prostu tworzymy nowe węzły i dodajemy kolejne relacje.

Grafowa baza danych może być też dobrym wyborem jeśli po prostu chcesz ułatwić sobie życie i otrzymać informacje łatwiej niż mógłbyś je uzyskać z relacyjnej bazy danych (mediany, znalezienie podobnych danych). Np. Neo4j oferuje opcjonalne biblioteki które rozszerzają możliwości bazy - przeczytaj o bibliotece APOC tutaj. Kod CYPHER (zobacz wstęp do tego języka) jest bardziej zwięzły i bardziej przejrzysty niż SQL.

Przykłady zastosowania grafowych baz danych

Poniżej znajdziesz najczęściej wymieniane zastosowania grafowych baz danych. Przykłady te są dobre do zrozumienia zastosowania produktu ale w wielu firmach budowanie drugiego Linkedin czy analiza oszustw prawdopodobnie nigdy nie będzie mieć miejsca. Dlatego przeczytaj artykuł jak jeszcze inaczej możesz wykorzystać grafowe bazy danych.

Przykład pierwszy – aplikacje społecznościowe

Aplikacje społecznościowe używają wyszukiwania grafowego by sugerować użytkownikom nowe kontakty. Poniższy wykres pokazuje grupę kontaktów. Basia ma bezpośrednich przyjaciół; Jerzego i Zenobię. Nie jest natomiast w bezpośrednim kontakcie z Karolem (Karol jest przyjacielem Zenobi i odwrotnie). Aplikacja znajduje znajomych przyjaciół Basi i rekomenduje ich jako „dodaj przyjaciela”.

Poniższe zapytanie zwróci jako rezultat imię „Karol”

MATCH 
{class: Customer, as: profile, where: (Name = 'Basia')}-Friend-{as: friendE},
{as: friendE}-Friend-{as: friendOfFriend, where: ($matched.profile not in $currentMatch.both('Friend') and $matched.profile != $currentMatch)} 
RETURN DISTINCT friendOfFriend.Name

Przykład drugi – rekomendacje produktów

Basia zakupiła w sklepie internetowym komputer (notebook). Sklep znając jej zakupy rekomenduje jej zakup artykułow innych osób które także kupiły komputer.

Poniższe zapytanie zwróci listę produktów osób które tak jak Basia kupiły notebook. W tym przypadku będzie to papier i toner (Zenobia kupiła notebook oraz papier i toner).

Rezultatów sklep używa w sekcji „inni klienci kupili również…” lub w kampaniach marketingowych sugerując Basi zakup produktów które zakupili inni klienci kupujący notebooki.

MATCH
{class:Product, as:product, where:(Name='Notebook')} <-Bought- {as:customer, class:Customer} -Bought-> {as:rekomendacja, where:($matched.product != $currentMatch)}
RETURN customer.Name, rekomendacja.Name 

Jeśli chcesz dowiedzieć się więcej jak możesz wykorzystać grafową bazę danych do rekomendacji produktów, up-selling'u, e-mailingu i targetowanych ofert - przeczytaj o tym więcej tutaj.

Przykład trzeci - obliczanie odległości między punktami

Grafowe bazy danych nadają się doskonale do obliczania odległości między punktami. Lokalizacje miejscowości na mapie to matematyczny model grafu a dane w grafowych bazach danych są właśnie zorganizowane w grafy.

Grafowa baza danych może użyć algorytmu Dijkstry lub A* (astar) by znaleźć najkrótszą drogę miedzy dwoma punktami. Google Maps używa wielu algorytmów do wytyczania trasy między dwiema miejscowościami ale stosują także te algorytmy. Algorytmy te mogą być używane w biznesie np. do zarządzania przesyłkami w logistyce.

Poniżej przedstawiony jest uproszczony model połączeń miedzy Warszawą a Radomiem.

Poniższe zapytania demonstrują jak grafowa baza danych znajduje najkrótszą drogę między tymi miejscowościami (miedzy wierzchołkiem oznaczonym #37:0 a wierzchołkiem #40:0):

SELECT DISTINCT dijkstra(#37:0, #40:0,'distance') FROM V

lub algorytm A*

SELECT DISTINCT astar(#37:0, #40:0,'distance') FROM V

Zapytanie zwróci listę miejscowości przez które trzeba przejechać by udać się najkrótszą drogą z Warszawy do Radomia.

Przykład czwarty - wyszukiwanie anomalii

Grafowe bazy danych dzięki prezentowaniu wyników w postaci graficznej (obiektów i powiązań między nimi) doskonale nadają się do wykrywania anomalii. Przykładami takich anomalii mogą być naruszenia bezpieczeństwa, awarie, oszustwa ubezpieczeniowe, oszustwa bankowe czy oszustwa w handlu elektronicznym. Wykrywanie takich zdarzeń to analizowanie logów lub mapy powiązań i szukanie wzorów wśród danych. Tutaj bardzo przydają się "piłeczki" na ekranie - wzrok analityka szybko wychwyci anomalie.

Trudno przedstawić konkretne zapytanie do grafowej bazy danych które pokaże np. wszystkie potencjalne fraudy. Zazwyczaj jest ich wiele, które kolejno zawężają obszar poszukiwań ale ich wspólną cechą jest poszukiwanie wzorców które odstają od standardowego modelu.

Np. wspólne dane kontaktowe dla różnych klientów czy posiadaczy konta, duża liczba kupujących ma transakcje pochodzące z tego samego adresu IP, wiele przesyłek do różnych adresów może korzystać z tej samej karty kredytowej lub duża liczba kart kredytowych może korzystać z tego samego adresu.

Im więcej jest wzajemnych połączeń między węzłami, tym większy powód do obaw. Duże zagęszczenia węzłów i połączeń są bardzo silnymi wskaźnikami, że w tych miejscach dochodzi do oszustw.

Grafowe bazy danych dobre na wszystko?

Grafowe bazy danych najlepiej radzą sobie w środowisku w którym występują relacje. Zatem tam gdzie dane są luźno powiązane, inny rodzaj technologii może być bardziej odpowiedni.

Największa zaleta grafowych baz danych to przechodzenie przez połączone dane i odczytywanie tych informacji w ciągu milisekund. Jeśli zatem w Twojej bazie danych nie używasz intensywnie JOINów – grafowa baza danych nie wykaże swych zalet.

Podobnie jak bazy NoSQL, grafowe bazy danych wykazują swoją przewagę nad relacyjnymi bazami danych wszędzie tam gdzie dane nie są ustrukturyzowane i/lub ich format i powiązania często się zmieniają. Jeśli zatem nie masz potrzeby częstego dodawania do bazy nowych tabel, pól, powiązań – grafowa baza danych nie będzie najlepszym wyborem.

Grafowe bazy danych nie są zoptymalizowane dla zapytań analitycznych o dużej objętości typowych dla hurtowni danych. Na przykład nie byłbyś w stanie odpowiedzieć na proste, ale wieloaspektowe pytanie, takie jak: „Kim byli wszyscy klienci z dochodami powyżej 100 000 USD w wieku od 35 do 50 lat?”.

Grafowe bazy nie tworzą lepszych relacji niż relacyjne bazy danych. Po prostu zapewniają szybkie pobieranie danych dla podłączonych danych. Bazy grafowe pozwalają szybko przeszukiwać dane związane z indywidualnym rekordem (osoba, produkt, miejsce itp.).

Relacyjne bazy danych pozwalają na przechowywanie danych w różnych tabelach i ich łączenie JOINami w zależności od potrzeb (uwzględniając koszty wydajnościowe takich połączeń). W Grafowej bazie danych wszystkie analizowane dane i połączenia między nimi musisz mieć w jednej bazie danych - nie można dołączyć dynamicznie innej tabeli (bazy danych w nomenklaturze grafów).

Jest co najmniej jeden przypadek z którym grafowe bazy danych nie poradzą sobie na pewno. Jest nim Problem komiwojażera. Choć problem został zamodelowany jako graf (gdzie miasta są wierzchołkami a drogi krawędziami).

W artykule użyte zostały składnie zapytań do grafowej bazy danych OrientDB oraz Neo4j