K-vertex: a novel model for the cardinality constraints enforcement in graph databases

doctoral dissertation

Martina Šestak (Avtor), Muhamed Turkanović (Mentor), Kornelije Rabuzin (Komentor)

Povzetek

The increasing number of network-shaped domains calls for the use of graph database technology, where there are continuous efforts to develop mechanisms to address domain challenges. Relationships as 'first-class citizens' in graph databases can play an important role in studying the structural and behavioural characteristics of the domain. In this dissertation, we focus on studying the cardinality constraints mechanism, which also exploits the edges of the underlying property graph. The results of our literature review indicate an obvious research gap when it comes to concepts and approaches for specifying and representing complex cardinality constraints for graph databases validated in practice. To address this gap, we present a novel and comprehensive approach called the k-vertex cardinality constraints model for enforcing higher-order cardinality constraints rules on edges, which capture domain-related business rules of varying complexity. In our formal k-vertex cardinality constraint concept definition, we go beyond simple patterns formed between two nodes and employ more complex structures such as hypernodes, which consist of nodes connected by edges. We formally introduce the concept of k-vertex cardinality constraints and their properties as well as the property graph-based model used for their representation. Our k-vertex model includes the k-vertex cardinality constraint specification by following a pre-defined syntax followed by a visual representation through a property graph-based data model and a set of algorithms for the implementation of basic operations relevant for working with k-vertex cardinality constraints. In the practical part of the dissertation, we evaluate the applicability of the k-vertex model on use cases by carrying two separate case studies where we present how the model can be implemented on fraud detection and data classification use cases. We build a set of relevant k-vertex cardinality constraints based on real data and explain how each step of our approach is to be done. The results obtained from the case studies prove that the k-vertex model is entirely suitable to represent complex business rules as cardinality constraints and can be used to enforce these cardinality constraints in real-world business scenarios. Next, we analyze the performance efficiency of our model on inserting new edges into graph databases with varying number of edges and outgoing node degree and compare it against the case when there is no cardinality constraints checking. The results of the statistical analysis confirm a stable performance of the k-vertex model on varying datasets when compared against a case with no cardinality constraints checking. The k-vertex model shows no significant performance effect on property graphs with varying complexity and it is able to serve as a cardinality constraints enforcement mechanism without large effects on the database performance.

Ključne besede

graph database;K-vertex cardinality constraint;cardinality;business rule;property graph data model;property graph schema;hypernode;performance analysis;fraud detection;data classification;

Podatki

Jezik:	Angleški jezik
Leto izida:	2022
Tipologija:	2.08 - Doktorska disertacija
Organizacija:	UM FERI - Fakulteta za elektrotehniko, računalništvo in informatiko
Založnik:	[M. Šestak]
UDK:	004.725:[004.65:519.17](043.3)
COBISS:	117895939
Št. ogledov:	224
Št. prenosov:	38
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Slovenski jezik
Sekundarni naslov:	K-vozlišče: nov model za uveljavljanje omejitev kardinalnosti v podatkovnih bazah grafov
Sekundarni povzetek:	Naraščajoče število poslovnih domen, ki se lahko izrazijo v obliki omrežij, zahteva uporabo tehnologije podatkovnih baz grafov, pri čemer to področje nenehno razvija nove mehanizme za reševanje domenskih izzivov. V disertaciji se osredotočamo na preučevanje mehanizma omejitev kardinalnosti, ki izkorišča povezave osnovnega grafa z lastnostmi. Potreba po nadzoru števila povezav, ki se lahko ustvarijo med vozlišči v podatkovni bazi grafov, obstaja predvsem v domenah z močno povezanimi podatki, kot so družbena omrežja, bančne transakcije, recenzije izdelkov, senzorska omrežja v zasnovi interneta stvari (angl. Internet of Things), itn. Kot naš prispevek k reševanju teh izzivov v disertaciji formalno predstavimo abstraktni model k-vozlišče, ki omogoča formalno definicijo omejitev kardinalnosti na povezavah med dvema ali več vozlišči z uporabo teorije grafov, njihovo predstavitev ter implementacijo v sodobnih sistemih za upravljanje podatkovnih baz grafov. V disertaciji smo najprej predstavili relevantne zasnove iz teorije grafov, na katerih temeljijo podatkovne baze grafov. Obstoječe definicije osnovnih zasnov podatkovnih baz grafov smo kasneje razširili in v definicijo sheme grafa z lastnostmi vključili omejitve kardinalnosti k-vozlišče. Razen teoretične snovi, na kateri temelji predlagani model k-vozlišče, smo opravili tudi sistematičen pregled obstoječih pristopov za uveljavljanje omejitev kardinalnosti v relacijskih ter podatkovnih bazah NoSQL in podrobneje podatkovnih bazah grafov. Rezultati pregleda literature so pokazali, da obstaja raziskovalna vrzel, ko gre za zasnove in pristope za opredelitev in predstavitev kompleksnih omejitev kardinalnosti za podatkovne baze grafov, ki so validirane v praksi. Z namenom naslavljanja omenjenega izziva, smo predstavili nov in izčrpen pristop imenovan model omejitev kardinalnosti k-vozlišče, ki vključuje specifikacijo omejitev kardinalnosti k-vozlišče nad povezavami med dvema ali več vozlišči, vizualni prikaz omejitev kardinalnosti na modelu grafa z lastnostmi ter implementacijo zagotavljanja omejitev kardinalnosti. Formalno smo predstavili abstraktno zasnovo omejitev kardinalnosti k-vozlišče in njihovih lastnosti ter sintakso za njihovo specifikacijo v podatkovni bazi grafov. Kot naslednji korak, model k-vozlišče podpira vizualni prikaz omejitev s pomočjo modela grafa z lastnostmi, kjer je možno prikazati vse elemente formalne definicije omejitev kardinalnosti k-vozlišče (vozlišča, hipervozlišča, povezave, lastnosti vozlišč/povezav ter minimalno in maksimalno kardinalnost). Kot zadnji korak smo predstavili tudi tri algoritma potrebna za implementacijo modela k-vozlišče v določeni podatkovni bazi grafov. V drugem delu disertacije ocenjujemo uporabnost modela na primerih uporabe z izvedbo dveh ločenih študij primerov, kjer predstavljamo, kako je mogoče model implementirati na primerih uporabe odkrivanja goljufij pri recenziji izdelkov in klasifikacije podatkov o deležu kaznivih dejanj v mestnih soseskah. Pri obeh primerih se model k-vozlišče iskazal kot primeren pristop za uporabo omejitev kardinalnosti v različnih domenah, ki se lahko prikažejo kot grafi z lastnostmi. Nato analiziramo učinkovitost delovanja modela k-vozlišče pri vstavljanju novih povezav v podatkovne baze grafov z različnim številom povezav in izhodno stopnjo vozlišč ter jo primerjamo s primerom, ko ni preverjanja omejitev kardinalnosti. Rezultati statistične analize potrjujejo stabilno delovanje modela k-vozlišče na različnih množicah podatkov v primerjavi s primerom brez preverjanja omejitev kardinalnosti. S povečanjem velikosti grafa učinkovitost modela k-vozlišče ostaja stabilna z majhnimi razlikami v primerjavi z manjšo velikostjo grafa. Na podlagi teh ugotovitev sklepamo, da model omejitev kardinalnosti k-vozlišče lahko služi kot mehanizem za uveljavljanje omejitev kardinalnosti brez signifikantnih vplivov na učinkovitost podatkovne baze.
Sekundarne ključne besede:	podatkovne baz grafov;omejitev kardinalnosti k-vozlišče;kardinalnost;podatkovni model grafa z lastnostmi;shema grafa z lastnostmi;hipervozlišče;analiza učinkovitosti;poslovno pravilo;odkrivanje goljufij;klasifikacija podatkov;doktorske disertacije;Univerzitetna in visokošolska dela;
Vrsta dela (COBISS):	Doktorsko delo/naloga
Komentar na gradivo:	Univ. v Mariboru, Fak. za elektrotehniko, računalništvo in informatiko
Strani:	VII, 151 str.
ID:	15026294