Konačni automati kao model evaluacije za upite na grafovima

diplomski rad

• Naslov (engleski): Finite automata as an evaluation model for graph queries
• Autor: Mateo Dujić
• Mentor: Domagoj Vrgoč (mentor)
• Član povjerenstva: Domagoj Vrgoč (predsjednik povjerenstva)
• Član povjerenstva: Mladen Vuković (član povjerenstva)
• Član povjerenstva: Rudi Mrazović (član povjerenstva)
• Član povjerenstva: Pavle Goldstein (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Prirodoslovno-matematički fakultet; (Matematički odsjek); Zagreb
• Datum i država obrane: 2023-07-19, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

U ovom diplomskom radu istražuje se primjena grafovskih baza podataka u kontekstu regularnih upita na putove. Prvo su dane osnovne definicije vezane uz grafovske baze podataka, kao i pregled različitih modela tih baza te potom simuliranje između različitih modela baza Nadalje, rad se fokusira na algoritme za izračunavanje regularnih upita na putove i pruža pregled u glavne važne vrste putova (šetnja, staza, jednostavan i acikličan), kao i slučajeve kada su odabrani svi najkraći, neki ili neki najkraći putevi. Izvedene su složenosti algoritama te dokazan rezultat o NP-potpunosti jezika NEKI JEDNOSTAVNI PUT. Algoritmi su implementirani u programskom jeziku Python i ona je javno dostupna na https://github.com/mdujic/diplomski. U sklopu implementacije primjenjen je Glushkovovov algoritma i opisan postupak izgradnje nedeterminističkog konačnog automata s jedinstvenim završnim stanjem. Osim toga, prikazana je i implementacija grafovske baze poodataka sa strukturom podataka Trie u svojoj jezgri. U sklopu eksperimenata, izvršeni su testovi na umjetnim primjerima s eksponencijalnim brojem slučajeva, kao i na primjerima iz stvarnog svijeta. Ovi testovi služe za provjeru efektivnosti i skalabilnosti razvijenih algoritama. U zaključku, ovaj rad pruža pregled primjene grafovskih baza podataka i algoritama za izračunavanje regularnih upita na putove. Istraženi su različiti modeli baza, implementacija, kao i izvedeni eksperimenti koji su pokazali uspješnost razvijenih algoritama. Ovaj rad doprinosi razumijevanju i razvoju grafovskih baza podataka u kontekstu regularnih upita na putove.

Sažetak (engleski)

This thesis explores the application of graph databases in the context of regular path queries. First, the basic definitions related to graph databases are given, as well as an overview of different models of these databases, followed by simulation between different database models. Furthermore, the thesis focuses on algorithms for calculating regular path queries and provides an overview of the main important types of paths (walk, trail, simple, and acyclic), as well as cases when all shortest, any, or any shortest paths are selected. The complexities of the algorithms are derived, and a result of the NP-completeness of the language ANY SIMPLE PATH is proven. The algorithms were implemented in the Python programming language and the code is publicly available at https://github.com/mdujic/diplomski. As part of the implementation, Glushkov’s algorithm was applied, and the process of constructing a nondeterministic finite automaton with a unique final state was described. Additionally, an implementation of a graph database using a Trie data structure is presented. In the experiments, tests were performed on artificial examples with an exponential number of cases, as well as on real-world examples. These tests serve to verify the effectiveness and scalability of the developed algorithms. In conclusion, this thesis provides an overview of the application of graph databases and algorithms for calculating regular path queries. Different database models, implementations, and conducted experiments that demonstrated the success of the developed algorithms were explored. This work contributes to the understanding and development of graph databases in the context of regular path queries

• Ključne riječi: grafovske baze podataka; NP-potpunost jezika; programski jezik Python; Glushkovovov algoritam
• Ključne riječi (engleski): graph databases; NP-completeness of the language; Python programming language; Glushkov’s algorithm
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:315108
• Studijski program: Naziv: Računarstvo i matematika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: sveučilišni magistar računarstva i matematike (univ. mag. inf. et math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2024-02-08 13:30:26