Grafy w SQL czyli OQGRAPH

GrafySQL pracuje na tabelach. Gorzej, gdy dane są ułożone w drzewo lub graf. Dlatego ciekawym rozwiązaniem jest OQGRAPH – silnik dla MariaDB, który pozwala poruszać się po danych grafowych.

Co to są grafy?

Najprościej mówiąc graf to węzły (nodes) połączone relacjami (zwanymi też krawędziami grafu). Każda relacja ma węzeł źródłowy i docelowy. Mówimy, że relacja jest skierowana.

Można wyobrazić sobie mapę. Węzły to miasta a relacje to drogi między nimi. Drogi są jednokierunkowe. Na dodatek drogi mają swoje stopnie trudności, czas przejazdu. Np. trasa Wrocław-Katowice jest szybsza gdy jedziemy autostradą a ta sama trasa zwykłą drogą międzymiastową zajmuje dłużej. W grafach mówimy, że każda relacja ma swoją wagę.

Grafem więc może być mapa miasta, mapa relacji między ludźmi (znajomości). Wszyscy ludzie na facebooku poprzez połączenie znajomościami również tworzą graf. Cały internet jest jednym wielkim grafem, gdzie strony (węzły) linkują (mają relacje) do innych stron.

Problem z szukaniem w grafach

Znalezienie konkretnych węzłów lub konkretnych relacji jest łatwe. Jakkolwiek byśmy nie zapisali grafu, znalezienie np. wszystkich moich sąsiadów (węzłów, z którymi jestem połączony) też jest proste.

Zabawa zaczyna się, gdy chcemy zadać ciekawsze pytania. Np. „znajdź mi najkrótszą drogę od A do B” albo „znajdź wszystkie miejsca, do których mogę dojechać z X”.

Jeśli mamy zwykłą listę węzłów lub połączeń to odpowiedź na powyższe pytania jest trudna. Trzeba przejrzeć wszystkie możliwe ścieżki aby znaleźć tą najkrótszą. Trzeba przejrzeć kierunek wszystkich połączeń aby znaleźć miejsca, gdzie można dotrzeć. W zwykłych tabelach SQL nie zrobimy tego łatwo. Z pomocą przychodzi OQGRAPH.

Grafowa baza SQL

OQGRAPH to silnik bazodanowy, tak samo jak MyISAM czy INNODB. Dostępny jest w bazie MariaDB czyli młodszym bracie MySQL. W ramach tego silnika tworzymy „tabele” w jednym, ustalonym formacie:

CREATE TABLE graf (
    latch   VARCHAR(32) UNSIGNED NULL,
    origid  BIGINT      UNSIGNED NULL,
    destid  BIGINT      UNSIGNED NULL,
    weight  DOUBLE      NULL,
    seq     BIGINT      UNSIGNED NULL,
    linkid  BIGINT      UNSIGNED NULL,
    KEY (latch, origid, destid) USING HASH,
    KEY (latch, destid, origid) USING HASH
  ) ENGINE=OQGRAPH;

Tak naprawdę wewnętrznie silink nie przechowuje danych w formie tabeli. Jedynie do komunikacji z SQL dane wyglądają jak tabela. Trzy pogrubione wyżej parametry opisują nam cały graf:

  • orgid i destid – identyfikatory węzłów, żródłowego i docelowego
  • weight – waga relacji

Pozostałe pola służą do celów technicznych. Same węzły trzymamy w innej tabeli. Nasz silnik służy jedynie do obsługi połączeń między nimi.

Trzy powyższe pola są jedynymi, które możemy zapisywać:

INSERT INTO graf (orgid, destid, weight) VALUES (1, 2, 3.1415);

Szukanie w grafach

Możemy oczywiście wylistować wszystkie połączenia pasujące do źródła, celu lub wagi za pomocą zwykłego SELECT … WHERE. Ale najciekawsze rzeczy dzieją się gdy spróbujemy wyszukać powiązania.

Najkrótszą ścieżkę między odległymi węzłami możemy znaleźć używając magicznego parametru latch. Służy on do powiedzenia silnikowi jakiego algorytmu ma użyć przy szukaniu. Możemy szukać za pomocą algorytmu Dijkstry:

SELECT * FROM graf WHERE latch = 'dijkstras' AND origid = 1 AND destid = 6;

W tym przykładzie wyszukaliśmy najkrótszą ścieżkę prowadzącą z węzła 1 do 6. W odpowiedzi dostaniemy listę kolejnych węzłów do pokonania:

+----------+--------+--------+--------+------+--------+
| latch    | origid | destid | weight | seq  | linkid |
+----------+--------+--------+--------+------+--------+
| dijkstras|      1 |      6 |   NULL |    0 |      1 |
| dijkstras|      1 |      6 |      1 |    1 |      2 |
| dijkstras|      1 |      6 |      1 |    2 |      6 |
+----------+--------+--------+--------+------+--------+

Jak to przeczytać? Po kolei:

  • orgid i destid zawsze mówią o całej ścieżce
  • linkid to identyfikator węzła w każdym kroku
  • seq to numer kolejnego kroku na ścieżce
  • weight to waga połączenia w każdym z kroków

Jeśli zechcemy znaleźć np. wszystkie ścieżki do węzła, możemy użyć algorytmu wyszukiwania w głąb podając jedynie węzeł docelowy:

SELECT * FROM graf WHERE latch = 'breadth_first' AND destid = 6

Znów dostaniemy dane w postaci tabelki. Tym razem parametr linkid będzie zawierał węzeł źródłowy a weight liczbę kroków na ścieżce do naszego węzła.

W podobny sposób możemy zadawać inne zapytania – szukać gdzie możemy dość z naszego węzła (podając tylko origid oraz latch) lub znaleźć ścieżkę między dwoma węzłami z najmniejszą liczbą kroków (origid i destid oraz latch równe breadth_first)

Zalety i wady

OQGRAPH ma kilka zalet. Przede wszystkim relacje opisujemy w znanym nam SQL. Silnik jest dość szybki, wyszukiwanie w dużej liczbie relacji jest efektywne. Możemy też trzymać nasze dane w zwykłych tabelach SQL a jedynie w OQGRAPH relacje między węzłami. Można używać zapytań JOIN aby pobrać relacje od razu z danymi.

Największą wadą silnika jest brak „kolorowania krawędzi” czyli nadawania relacjom typów. Nie możemy więc rozróżnić relacji np. sąsiad od przyjaciel. Nie możemy też wyszukiwać np. węzłów oddalonych od nas o X połączeń.

Opisany silnik nadaje się więc do prostych grafów, które mogą zawierać dużo danych.

Co dalej

Warto poczytać dokumentację OQGRAPH oraz dokumentację na stronie MariaDB gdzie poznamy sposoby instalacji silnika. Jest tam też więcej przykładów uzycia bazy. Dostępna jest też ciekawa prezentacja na temat OQGRAPH.

Istnieją również inne grafowe (relacyjne) bazy danych. Jedną z nich opiszę w przyszłych wpisach.

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *