openCypher gráflekérdezések kiértékelése lokális keresés alapú algoritmussal

OData támogatás
Konzulens:
Szárnyas Gábor
Méréstechnika és Információs Rendszerek Tanszék

Az 1970-es évektől az elmúlt évtizedig az adatbázis-kezelés szinte kizárólag relációs

technológiák alkalmazását jelentette. Az elmúlt évtizedben azonban több tucat olyan rendszer

jelent meg és terjedt el, amelyek nemrelációs adatmodellt használnak. Ezek az ún. NoSQL

rendszerek egyik csoportja a gráfadatbázis-kezelők, amelyek a tulajdonsággráf (property

graph) adatmodellt támogatják. Napjaink egyik legnépszerűbb gráfadatbázis-kezelő rendszere,

a Neo4j, a Cypher lekérdezőnyelvet hozta létre arra, hogy a felhasználók és fejlesztők

gráfmintákat definiálhassanak. Az openCypher kezdeményezés 2015. végén indult azzal a

küldetéssel, hogy – a relációs adatbáziskezelés világának SQL nyelvéhez hasonlóan – egy

szabványos nyelvet definiáljon gráflekérdezések megvalósítására. Ennek célja, hogy a

felhasználók szabványos lekérdezéseket fogalmazhassanak meg, amelyek különböző

gráfadatbázis rendszereken kiértékelhetők, így csökkentve azt a kockázatot, hogy csak egy

adott adatbázis rendszer képes a lekérdezéseik kiértékelésére (vendor lock-in).

A tanszéken fejlesztett ingraph rendszer célja, hogy openCypher nyelven definiált

gráflekérdezések hatékony kiértékelését tegye lehetővé. Az ingraph rendszerben jelenleg már

működik egy inkrementális lekérdezőmotor, amely képes arra, hogy az előre

megadott, folyamatosan kiértékelt lekérdezések eredményhalmazát

hatékonyan karbantartasa. Ez a megközelítés azonban rendkívül

pazarlóan bánik a memóriával, így nem hatékony komplex, egyszer lefuttatott lekérdezések

kiértékelésére. Erre a problémára a lokális keresést alkalmazó algoritmusok

használata célravezetőbbnek bizonyulhat. Munkám során egy meglévő ilyen, a

keresést kényszerkielégítési problémára visszavezető algoritmust módosítottam és

illesztettem az ingraph rendszerhez. A motor az openCypher nyelvben fellelhető minták nagy részét

támogatja, az egyszerű csomópont-, útvonal- és típuskritériumokon túl képes negatív

kondíciók kiértékelésére is, valamint kiterjeszthető további kényszerekkel,

mintákkal. A kiértékelés hatékonyságát és skálázhatóságát teljesítménymérésekkel igazoltam.

Letölthető fájlok

A témához tartozó fájlokat csak bejelentkezett felhasználók tölthetik le.