Konačni automati kao model evaluacije za upite na grafovima

master's thesis

• Title (english): Finite automata as an evaluation model for graph queries
• Author: Mateo Dujić
• Mentor: Domagoj Vrgoč (mentor)
• Committee member: Domagoj Vrgoč (predsjednik povjerenstva)
• Committee member: Mladen Vuković (član povjerenstva)
• Committee member: Rudi Mrazović (član povjerenstva)
• Committee member: Pavle Goldstein (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2023-07-19, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

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.

Abstract (english)

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

• Keywords: grafovske baze podataka; NP-potpunost jezika; programski jezik Python; Glushkovovov algoritam
• Keywords (english): graph databases; NP-completeness of the language; Python programming language; Glushkov’s algorithm
• Language: croatian
• URN:NBN: urn:nbn:hr:217:315108
• Study programme: Title: Computer Science and Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: sveučilišni magistar računarstva i matematike (sveučilišni magistar računarstva i matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2024-02-08 13:30:26