Úvod do grafových databází - rychlé porovnání relačních a grafových databází

Úvod

Tradiční relační databáze jsou založeny na relačním modelu, kde jsou data reprezentována n-ticemi (řádky) a shlukují se do relací (tabulek). Každý řádek může mít primární klíč, což je množina atributů (sloupců), které jednoznačně identifikují n-tici. Často je to jediný sloupec s identifikátorem.

Pro modelování vztahů mezi daty je pak nutné použít tzv. přechodové tabulky, které specifikují vztah "kdo s kým" za pomocí řádků s cizími klíči, což jsou odkazy na primární klíče jiných tabulek. Jedná se tedy o "nepřímé" modelování.

Grafové databáze nabízejí alternativu, kde je modelování vztahů přímočaré, neboť jsou založeny na grafovém modelu, tedy na uzlech ("n-tice") a hranách (vztahy). Zde se od začátku počítá s prací se vztahy a dotazovací jazyk tomu bývá uzpůsoben a poskytuje vyjadřovací prostředky pro pohodlnou definici sebesložitějších vztahů.

Příklad: adresářová struktura

Pojďme si nyní ukázat příklad implementace adresářové struktury v relační a v grafové databázi. Kromě adresářů a souborů budeme také pracovat s jejich vlastníky.

Jako vstupní data použijeme tento malý vzorek:

/home/alice/myfile.txt <-- vlastní alice
/home/bob/myfile.txt   <-- vlastní bob
/tmp/alice.txt         <-- vlastní alice
/tmp/bob.txt           <-- vlastní bob

V naší implementaci bude nutné rozeznávat, co je adresář a co je soubor.

Vytvoření relační databáze

Nejprve si ukážeme implementaci v relační databázi, zde konkrétně v MySQL.

MySQL vyžaduje, abychom nejprve definovali schema jejích tabulek. "Čistý" přístup by vyžadoval 7 tabulek: vlastníci, soubory, adresáře, vztah vlastník-soubor, vztah vlastník-adresář, vztah adresář-adresář a vztah adresář-soubor. My si ale dovolíme jednu optimalizaci, a to shluknutí adresářů a souborů do jediné tabulky; adresáře od souborů rozeznáme příznakem folder. Vlastník by ze své jednoatributové povahy mohl být rovněž přítomen v tabulce souborů, pro tento příklad ale vlastníky oddělíme.

Navrhneme tedy 4 tabulky - vlastníci, soubory, vztah vlastník-soubor, vztah soubor-soubor (zanoření adresářového stromu).

/* files and folders */
CREATE TABLE IF NOT EXISTS fs_entries (
    absolute_path VARCHAR(255) PRIMARY KEY,
    basename VARCHAR(255),
    folder BOOLEAN
);

/* owners */
CREATE TABLE IF NOT EXISTS owners (
    name VARCHAR(255) PRIMARY KEY
);

/* fs_entries:owners relationship */
CREATE TABLE IF NOT EXISTS fs_entry_owners (
    owner varchar(255),
    entry varchar(255),
    FOREIGN KEY (owner) REFERENCES owners(name),
    FOREIGN KEY (entry) REFERENCES fs_entries(absolute_path)
);

/* fs_entries:fs_entries relationship */
CREATE TABLE IF NOT EXISTS fs_entry_nesting (
    parent varchar(255),
    child varchar(255),
    FOREIGN KEY (parent) REFERENCES fs_entries(absolute_path),
    FOREIGN KEY (child) REFERENCES fs_entries(absolute_path)
);

/* owners data */
INSERT INTO owners (name) VALUES ('alice');
INSERT INTO owners (name) VALUES ('bob');

/* fs_entries data - top level */
INSERT INTO fs_entries (absolute_path, basename, folder) 
VALUES ('/', '/', 1);
INSERT INTO fs_entries (absolute_path, basename, folder) 
VALUES ('/home', 'home', 1);
INSERT INTO fs_entries (absolute_path, basename, folder) 
VALUES ('/tmp', 'tmp', 1);

/* fs_entries data - home files */
INSERT INTO fs_entries (absolute_path, basename, folder) 
VALUES ('/home/alice', 'alice', 1);
INSERT INTO fs_entries (absolute_path, basename, folder) 
VALUES ('/home/bob', 'bob', 1);
INSERT INTO fs_entries (absolute_path, basename, folder) 
VALUES ('/home/alice/myfile.txt', 'myfile.txt', 0);
INSERT INTO fs_entries (absolute_path, basename, folder) 
VALUES ('/home/bob/myfile.txt', 'myfile.txt', 0);

/* fs_entries data - tmp files */
INSERT INTO fs_entries (absolute_path, basename, folder) 
VALUES ('/tmp/alice.txt', 'alice.txt', 0);
INSERT INTO fs_entries (absolute_path, basename, folder) 
VALUES ('/tmp/bob.txt', 'bob.txt', 0);

/* file hierarchy relationship data */
INSERT INTO fs_entry_nesting (parent, child) 
VALUES ('/', '/home');
INSERT INTO fs_entry_nesting (parent, child) 
VALUES ('/', '/tmp');
INSERT INTO fs_entry_nesting (parent, child) 
VALUES ('/home', '/home/alice');
INSERT INTO fs_entry_nesting (parent, child) 
VALUES ('/home', '/home/bob');
INSERT INTO fs_entry_nesting (parent, child) 
VALUES ('/home/alice', '/home/alice/myfile.txt');
INSERT INTO fs_entry_nesting (parent, child) 
VALUES ('/home/bob', '/home/bob/myfile.txt');
INSERT INTO fs_entry_nesting (parent, child) 
VALUES ('/tmp', '/tmp/alice.txt');
INSERT INTO fs_entry_nesting (parent, child) 
VALUES ('/tmp', '/tmp/bob.txt');

/* owners to entries relationship data */
INSERT INTO fs_entry_owners (owner, entry) 
VALUES ('alice', '/tmp/alice.txt');
INSERT INTO fs_entry_owners (owner, entry) 
VALUES ('alice', '/home/alice');
INSERT INTO fs_entry_owners (owner, entry) 
VALUES ('alice', '/home/alice/myfile.txt');
INSERT INTO fs_entry_owners (owner, entry) 
VALUES ('bob', '/tmp/bob.txt');
INSERT INTO fs_entry_owners (owner, entry) 
VALUES ('bob', '/home/bob');
INSERT INTO fs_entry_owners (owner, entry) 
VALUES ('bob', '/home/bob/myfile.txt');

Vytvoření grafové databáze

Nyní si toto implementujeme v grafové databázi, konkrétně v Neo4j.

V grafové databázi můžeme reprezentovat adresáře a soubory uzly, jejich zanoření hranami. Vlastníci budou opět uzly a hranami budeme určovat jejich majetek. V Neo4j mohou jak uzly, tak hrany obsahovat atributy; pro tento příklad si však vystačíme s atributy v uzlech.

V Neo4j není třeba dopředu definovat žádné schema, data lze tedy zadat rovnou. Můžeme však dopředu definovat indexy, které zefektivní operace prováděné nad daty. Lze také definovat omezení (constraints), která zajistí unikátnost atributů pro uzly stejného označení (labelu). Tato omezení vytvoří implicitní indexy se všemi jejich výhodami.

Jazyk Cypher byl navržen tak, aby jeho syntaxe připomínala ASCII-art kdykoliv se zadávají cesty v grafu. Uzly se tedy značí kulatými závorkami, do kterých můžeme vepsat popis uzlu ve formě názvu, označení a atributů s hodnotami ((název:Označení { atribut1: hodnota1, ...})) a hrany ASCII šipkami (-->), které mohou volitelně nést obdobný popis (-[název:OZNAČENÍ { atribut1: hodnota1, ...}]->). Název lze vynechat úplně u obou dvou prvků - jedná se o označení proměnné, pokud ji chceme využít později.

Adresáře budeme od souborů rozeznávat označením uzlu.

Definice naší adresářové struktury by mohla vypadat takto:

// constraints are optional, but significantly enhance performance
CREATE CONSTRAINT folderConstraint IF NOT EXISTS 
FOR (f:Folder) REQUIRE f.absolutePath IS UNIQUE;
CREATE CONSTRAINT fileConstraint IF NOT EXISTS FOR 
(f:File) REQUIRE f.absolutePath IS UNIQUE;
CREATE CONSTRAINT ownerConstraint IF NOT EXISTS 
FOR (o:Owner) REQUIRE o.name IS UNIQUE;

// owners
CREATE (aliceOwner:Owner { name: 'alice' })
CREATE (bobOwner:Owner { name: 'bob' })

// top level folders
CREATE (root:Folder { absolutePath: '/', basename: '/' })
CREATE (root)-[:CONTAINS]->
(
    home:Folder { absolutePath: '/home', basename: 'home' }
)
CREATE (root)-[:CONTAINS]->
(
    tmp:Folder { absolutePath: '/tmp', basename: 'tmp' }
)

// tmp files with owners
CREATE (tmp)-[:CONTAINS]->
(
    atf:File { absolutePath: '/tmp/alice.txt', basename: 'alice.txt' }
)
<-[:OWNS]-(aliceOwner)
CREATE (tmp)-[:CONTAINS]->
(
    btf:File { absolutePath: '/tmp/bob.txt', basename: 'bob.txt' }
)
<-[:OWNS]-(bobOwner)

// home files with owners
CREATE (home)-[:CONTAINS]->
(
    aliceHome:Folder { absolutePath: '/home/alice', basename: 'alice' }
)
-[:CONTAINS]->
(
    amf:File { absolutePath: '/home/alice/myfile.txt', basename: 'myfile.txt' }
)
<-[:OWNS]-(aliceOwner)
CREATE (home)-[:CONTAINS]->
(
    bobHome:Folder { absolutePath: '/home/bob', basename: 'bob' }
)
-[:CONTAINS]->
(
    bmf:File { absolutePath: '/home/bob/myfile.txt', basename: 'myfile.txt' }
)
<-[:OWNS]-(bobOwner)

// home owners
CREATE (aliceHome)<-[:OWNS]-(aliceOwner)
CREATE (bobHome)<-[:OWNS]-(bobOwner)

Dotazy

Pojďme si nyní zkusit pár dotazů nad našimi malými daty.

Které soubory vlastní alice?

V relační databázi je třeba vyhledat alice v přechodové tabulce a napojit (join) výsledné řádky na tabulku se soubory.

Relační databáze:

SELECT fs_entries.* FROM fs_entries
JOIN fs_entry_owners ON fs_entry_owners.entry = fs_entries.absolute_path
WHERE fs_entry_owners.owner = 'alice' AND fs_entries.folder = 0;

V grafové databázi Neo4j jsou vztahy z uzlu alice dostupné přímo jako seznam, stačí tedy pouze následovat hranu do jejího cíle. Jazyk Cypher navíc nabízí notaci formou ASCII-artu.

Grafová databáze:

MATCH (:Owner { name: 'alice' })-[:OWNS]->(f:File) RETURN f

Jaké potomky má /home?

Zde je to podobné jako u předchozího dotazu.

Relační databáze:

SELECT fs_entries.* FROM fs_entries
JOIN fs_entry_nesting ON fs_entry_nesting.child = fs_entries.absolute_path
WHERE fs_entry_nesting.parent = '/home';

Grafová databáze:

MATCH (:Folder { absolutePath: '/home' })-[:CONTAINS]->(f:File|Folder) RETURN f

Jaké soubory v /tmp vlastní bob?

Zde je to opět podobné jako u předchozího dotazu, ale musíme provést více napojení. Ve větších datových sadách toto povede ke snížení výkonu.

Relační databáze:

SELECT fs_entries.* FROM fs_entries
JOIN fs_entry_nesting ON fs_entry_nesting.child = fs_entries.absolute_path
JOIN fs_entry_owners ON fs_entry_owners.entry = fs_entries.absolute_path
WHERE fs_entry_nesting.parent = '/tmp' AND fs_entry_owners.owner = 'bob';

V Neo4j plánovač vypočítá uzel, ze kterého se bude vycházet, a jednoduše profiltruje uzly, které jsou na něj navázané. ASCII-art umožňuje tento dotaz intuitivně napsat.

Grafová databáze:

MATCH (:Folder { absolutePath: '/tmp' })
-[:CONTAINS]->
(f:File)
<-[:OWNS]-
(:Owner { name: 'bob' })
RETURN f

Jaké potomky má /home (do hloubky)?

Hledání do hloubky vyžaduje rekurzivní sestup. V případě relační databáze je třeba pospojovat přechodovou tabulku opakovaně, dokud se nachází potomci potomků adresáře, který nás zajímá. Pro větší sady dat má toto nepříjemný výkonnostní dopad.

Relační databáze:

WITH RECURSIVE nesting_tree AS (
    SELECT * FROM fs_entry_nesting
    WHERE fs_entry_nesting.parent = '/home'
    UNION ALL
    SELECT e.*
    FROM fs_entry_nesting e
    JOIN nesting_tree ntree ON ntree.child = e.parent
)
SELECT fs_entries.* FROM fs_entries
JOIN nesting_tree ON fs_entries.absolute_path = nesting_tree.child;

V Neo4j má každý uzel veškeré vazby dostupné v konstantním čase, rekurzivní sestup je tedy mnohem rychlejší. Cypher opět poskytuje příjemný vyjadřovací prostředek, a to variabilní délku podgrafu, psanou jako hvězdičku * v hraně.

Grafová databáze:

MATCH (:Folder { absolutePath: '/home' })-[:CONTAINS*]->(f:File|Folder) RETURN f

Jaké potomky má /home (do hloubky, optimalizováno)?

A nakonec optimalizace, která obě řešení postaví na stejnou úroveň. Z povahy dat je zřejmé, že hierarchie je zakódována přímo v atributu absolutní cesty. Stačí mít tedy prefixový index na této absolutní cestě, a pak se pouze dotázat na její začátek. Toto řešení je velmi výkonné i na velkých sadách dat v obou databázích.

Relační databáze:

SELECT * FROM fs_entries WHERE fs_entries.absolute_path LIKE '/home/%';

Grafová databáze:

MATCH (f:File|Folder) WHERE f.absolutePath STARTS WITH '/home/' RETURN f

Nutno poznamenat, že toto elegantní řešení není univerzální a vyplynulo pouze z povahy absolutních cest v adresářových strukturách.

Závěr

Tradiční relační databáze neumožňují intuitivní definici vztahů a vyhledávání složitých vztahů vede ke složitým dotazům v dotazovacím jazyce, které navíc nemají optimální výkon.

Grafové databáze pohlíží na vztahy jako na stavební jednotku databáze a umožňují pohodlné vyhledání složitých vztahů, které lze jednoduše zapsat v intuitivním dotazovacím jazyce, a navíc jsou velmi výkonné.