Grafowe bazy danych

- autor: tsissput

Relacyjne bazy danych przyzwyczaiły nas do myślenia o danych, ich reprezentacji i utrwalaniu w bardzo ograniczony sposób. Kluczowe jest określenie sztywnego podziału danych na kategorie oraz określenie ścisłych relacji między nimi. Takie podejście ma szereg zalet, takich jak łatwy sposób reprezentacji ujętych w ten sposób danych w pamięci komputera czy ich późniejsze filtrowanie przy wykonywaniu zapytań. Często jednak taki sposób reprezentacji informacji okazuje się sztuczny, gdyż na poziomie aplikacji wygodniej jest stosować ogólniejsze struktury danych. Grafy na przykład pozwalają łatwo modelować m.in. rekurencję, ścieżki, hierarchie, etc. Za przykład usług wymagających modelowania danych w ten sposób mogą służyć sieci społecznościowe, systemy zarządzania treścią czy choćby systemy stron wiki. Oczywiście możliwe jest reprezentowanie grafów w relacyjnych bazach danych, jednak jak pokazują badania (patrz niżej), takie rozwiązania nie skalują się, są trudne w użyciu oraz uniemożliwiają stosowanie optymalizacji specyficznych dla grafów. Ogromnym wyzwaniem jest przechowywanie grafów dużych rozmiarów, a także ich efektywne przeszukiwanie. Stąd wysiłki naukowców mające na celu zaproponowanie  nowych modeli danych i języków zapytań, które pozwoliłyby na upowszechnienie się tzw grafowych baz danych.

GraphDB [1] stanowi rozszerzenie obiektowych baz danych pozwalające na bezpośrednie modelowanie i operowanie na grafach. W tym celu zdefiniowane są trzy nowe klasy obiektów: klasy proste (simple classes), połączenia (link classes) i ścieżki (path classes). Obiekty klas prostych reprezentują węzły grafu, połączenia odpowiadają łukom grafu i zawierają referencje do dwóch obiektów klas prostych. Natomiast obiekty klasy ścieżek przechowują informację na temat wszystkich węzłów i krawędzi grafu, które dana ścieżka odwiedza.

Z uwagi na to, że opisywane rozwiązanie stanowi rozszerzenie obiektowej bazy danych, możliwe jest określanie hierarchi klas obiektów składowych grafów. Wymaga to dodatkowego, złożonego mechanizmu zapewniającego spójność bazy. Ciekawym pomysłem jest określanie klas ścieżek jako wyrażeń regularnych na zbiorze klas połączeń.

W artykule przedstawiony jest jedynie szkic języka zapytań dla grafowych baz danych. Podstawą języka jest wyrażenie derive (derive statement), które może być używane podobnie jak wyrażenie select … from … where … w relacyjnych bazach danych. Prosty przykład znajdujący tytuły książek napisanych przez Grahama Greene’a w 1943 roku podany jest poniżej:

on person wrote book
where person.name = "Green" and
      book.year = 1943
derive book.title

gdzie person i book są klasami prostymi, wrote natomiast jest klasą połączeń. W powyższym przykładzie wynikiem będzie sekwencja (zawierająca 0, 1 lub więcej) elementów typu String. Wynikiem działania wyrażenia derive mogą być również sekwencje dowolnych typów, w tym obiektów klas prostych, połączeń i innych. Sekwencje nie muszą zawierać wyłącznie obiektów tego samego typu, mogą być sekwencjami heterogenicznymi. Do ich przetwarzania służy wyrażenie rewrite, dzięki któremu możliwe jest zastąpienie obiektów lub podsekwencji przez inne (nowe) obiekty. Autor planuje wprowadzenie do języka zapytań dodatkowych operacji pozwalających na m.in. sortowanie, grupowanie, pozyskiwanie najkrótszej ścieżki, etc.

GraphDB był pierwszym krokiem w kierunku projektowania grafowego modelu danych, który łatwo integrowałby się z obiektowym modelem danych. Przedstawione w artykule idee zostały zaimplementowane jako element platformy SECONDO, która została opisana dopiero 7 lat poźniej, w 2000 roku [1*].

Autorzy [2] wykorzystali model danych zbliżony do tego z [1]. Zdefiniowane zatem są typy węzłów (node types), krawędzi (edge types), ścieżek (path types) i dodatkowo typy grafowe (graph types) zawierające m.in. kolekcje węzłów i ścieżek należących do danego grafu. Odpytywanie grafowej bazy danych odbywa się przy wykorzystaniu zaproponowanego w artykule języka GOQL. Bazuje on na języku OQL [2*], ale dodatkowo definuje nowe operatory, które pozwalają na przetwarzanie ścieżek i sekwencji. Przykładowym nowym operatorem jest connected, przyjmujący jako argumenty dwa węzły (ścieżki) a i b. Wyrażenie a connected b jest prawdziwe, jeśli istnieje ścieżka p między węzłem a (ostatnim węzłem ścieżki a) i węzłem b (pierwszym węzłem ścieżki b). Przykładowe zapytanie w GOQL znajdujące połączenia autobusowe między Oxfordem a Londynem wygląda następująco:

select path(p)
from g in Connections,
     s1, s2 in g.Nodes,
     p in paths(g, s1, s2)
where g.name ="BusConnections",
      s1.name="Oxford",
      s2.name="London",
      p : s1 connected s2

W celu ewaluacji zapytań w GOQL, zapytania tłumaczone są z algebry bazującej na O-Algebrze, wykorzystanej wcześniej do przetwarzania zapytań języka OQL. Oprócz znanych z algebry relacyjnej i obecnych w O-Algebrze operatorów takich jak operator selekcji, produktu kartezjańskiego czy unii, znajdują się nowe, związane z nowymi operatorami zdefiniowanymi w GOQL. Autorzy na szeregu przykładów pokazują jak przy ich pomocy możliwa jest ewaluacja zapytań GOQL.

Jak słusznie zauważają autorzy, przetwarzanie grafów wymaga wykonywania trawersali, które często są bardzo kosztowne. Dlatego proponują optymalizację opartą o tzw nodecode’y, unikalne liczby przyporządkowywane wszystkim węzłom (jeden węzeł może mieć przyporządkowanych wiele nodecode’ów). Przydzielanie nodecode’ów poszczególnym węzłom odbywa się poprzez przeszukanie grafu w głąb. Dysponując zbiorami nodecode’ów dwóch dowolnych węzłów, możliwe jest stwierdzenie czy istnieje ścieżka między nimi. Jeśli taka ścieżka istnieje, wszystkie możliwe ścieżki między tymi węzłami mogą zostać wywiedzione bez wykonywania trawersali. Autorzy przyznają, że ta optymalizacja sprawdzać się będzie jedynie dla małych, rzadkich grafów (liczących do 50 węzłów). Nie mówią jednak co sie dzieje, gdy graf ulega modyfikacji. Wydaje się być to problematyczne z uwagi na algorytm  wykorzystujący przeszukiwanie grafu w głąb.

Artykuł zawiera jedynie wstępne porównanie algorytmów używających i nieużywających systemu nodecode’ów. Autorzy przedstawiaja wyłącznie dyskusje na temat złożoności każdego z nich, zostawiając ewaluację zaimplementowanych rozwiązań na przyszłość. Z pobieżnych poszukiwań wynika jednakże, że próżno jej
szukać w kolejnych artykułach autorów.

Autorzy [3] proponują zupełnie odmienne podejście do grafowych baz danych niż prezentowane w [1] czy [2]. Wychodzą bowiem z założenia, że w grafowej bazie danych podstawową jednostką informacji powinien być graf, a nie jego składowe, takie jak wierzchołek czy krawędź. Rozważany model danych dopuszcza grafy, węzły, krawędzie o dowolnej liczbie atrybutów. Podstawą prezentowanego rozwiązania jest formalny język dla grafów, który służy jako baza dla GraphQL, grafowego języka zapytań. W wypadku gramatyki dla grafów symbolami terminalnymi i nieterminalnymi nie są ciągi znaków, a struktury grafowe zwane motywami grafowymi (graph motifs). Motywem grafowym może być zwykły graf lub też graf zbudowany z innych motywów grafowych poprzez ich łączenie, branie ich alternatywy czy też powtarzanie. Tak jak w zwykłej gramatyce językiem jest zbiór wszystkich ciągów znaków, które można  uzyskać wskutek wykorzystania zdefiniowanej gramatyki i podstawowych symboli nieterminalnych, tu język stanowi zbiór wszystkich grafów, które można wygenerować poprzez wykonywanie operacji łączenia, alternatywy czy powtarzania na motywach grafowych.

Podstawą języka GraphQL są wzorce używane do przeszukiwania grafowej bazy danych. Wzorcem jest motyw grafowy wraz z predykatem na argumentach motywu grafowego. Wynikiem zapytania jest lista grafów pasujących do wzorca, niekoniecznie o tej samej strukturze czy atrybutach. Dopasowanie grafu do wzorca powoduje stworzenie powiązania między grafem a wzorcem, dzięki czemu możliwe jest operowanie na otrzymanej liście grafów w jednolity, zdefiniowany przez wzorzec sposób. GraphQL zawiera dodatkowo operator kompozycji (composition operator) pozwalający na przetwarzanie listy wynikowych grafów, podobnie jak to było w przypadku GraphDB. Poniżej znajduje się przykładowe zapytanie w formie FLWR (for, let, where, return) znanej z XQuery [3*] przeszukujące baze artykułów naukowych o nazwie DBLP generujące graf, w którym dowolna para współautorów artykułu ma wystąpić w postaci krawędzi między węzłami reprezentującymi autorów, jeśli artykuł powstał po roku 2000.

graph P {
   node v1 <author>;
   node v2 <author>;
   node a <year>;
} where a.year > 2000;
C:= graph {};
for P exhaustive in doc("DBLP")
   let C:= graph {
      graph C;
      node P.v1, P.v2;
      edge e1 (P.v1, P.v2);
      unify P.v1, C.v1 where P.v1.name=C.v1.name;
      unify P.v2, C.v2 where P.v2.name=C.v2.name;
   }

Wyrażenie for dopasowuje zdefiniowany wcześniej wzorzec P do grafów w bazie danych, let natomiast przetwarza wyniki dopasowań tworząc nowe grafy zawierające łuk między węzłami reprezentującymi współautorów.

Algebra grafowa, którą wykorzystuje GraphQL, to algebra relacyjna ale zaadoptowana do świata grafów. Zatem znane z algebry relacyjnej operatory takie jak operator selekcji czy iloczynu kartezjańskiego jako argumenty przyjmuje grafy a nie sekwencję krotek. Autorzy dowodzą, że nierekursywna wersja użytej algebry grafowej jest równoważna algebrze relacyjnej.

Problem dopasowywania wzorców w grafach jest problemem NP-zupełnym. Autorzy argumentują, iż brak łamania struktury grafów na poszczególne relacje (węzły, łuki, ścieżki) pozwala na stosowanie szeregu optymalizacji specyficznych dla grafów, np. ograniczających przestrzeń przeszukiwań. Autorzy opisują szczegółowo trzy  optymalizacje i demonstrują wyniki ewaluacji dla dwóch benchmarków: rzeczywistego i syntetycznego. Uzyskane wyniki pokazują, że przyjęte podejście i użyte optymalizacje pozwalają na osiągnięcie wydajności do dwóch rzędów wielkości większej niż w przypadku użycia bazy SQL do modelowania grafów.

Opisane krótko w tej notce rozwiązania, różniące się między sobą co do przyjętego podejścia, rozważanych aspektów, dyskusji strony implementacyjnej, stanowią przyczynek do tworzenia dojrzałych systemów grafowych baz danych. Dobrym dowodem na to, że istnieje zapotrzebowanie na rozwiązania tego typu jest uzyskanie we wrześniu zeszłego roku finansowania w wysokości 10.6 miliona dolarów dla otwartoźródłowego projektu grafowej bazy danych Neo4j [4*].

[1] Ralf Hartmut Guting (1994). GraphDB: Modeling and Querying Graphs in Databases 20th International Conference on Very Large Data Bases

Stefan Dieker, & Ralf Hartmut Guting (2000). Plug and Play with Query Algebras: SECONDO-A Generic DBMS Development Environment 2000 International Symposium on Database Engineering & Applications (IDEAS ’00)

[2] L. Sheng, Z. M. Ozsoyoglu, & G. Ozsoyoglu (1999). A Graph Query Language and Its Query Processing 15th International Conference on Data Engineering (ICDE ’99)

[2*] The Object Data Standard: ODMG 3.0. Edited by R.G.G. Cattell and Douglas K. Barry, with contributions by Mark Berler, Jeff Eastman, David Jordan, Craig L. Russell, Olaf Schadow, Torsten Stanienda, and Fernando Velez. Morgan Kaufmann Publishers, Inc., 2000. ISBN 1-55860-647-5.

[3] Huahai He, & Ambuj K. Singh (2008). Graphs-at-a-time: query language and access methods for graph databases ACM SIGMOD international conference on Management of data (SIGMOD ’08)

[3*] XQuery 1.0: An XML Query Language (Second Edition), http://www.w3.org/TR/2010/REC-xquery-20101214/

[4*] http://www.neotechnology.com/2011/09/neo-technology-closes-10-6-million-series-a
-funding-to-accelerate-adoption-of-nosql-in-the-enterprise/

Reklamy

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Log Out / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Log Out / Zmień )

Facebook photo

Komentujesz korzystając z konta Facebook. Log Out / Zmień )

Google+ photo

Komentujesz korzystając z konta Google+. Log Out / Zmień )

Connecting to %s

%d blogerów lubi to: