Efficient Indexing for Regular Path Queries

Thumbnail Image

Files

Glorioso_Olli_2025.pdf (476.52 KB)

URL

Journal Title

Journal ISSN

Volume Title

Perustieteiden korkeakoulu | Bachelor's thesis
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.

Authors

Date

2025-03-08

Department

Major/Subject

Tietotekniikka

Mcode

SCI3027

Degree programme

Teknistieteellinen kandidaattiohjelma

Language

en

Pages

25

Series

Abstract

Graph databases are non-relative databases that store the vertices, edges, and labels of a graph. An essential question related to labeled graphs is the following: is there a path between a given source vertex and a given target vertex, where the sequence of edge labels of the path form a string belonging to a regular language defined by a given regular expression? The problem is known as the regular path query (RPQ). This bachelor’s thesis thoroughly presents and analyzes the most common method for solving the RPQ. First, the given regular expression is converted into a Glushkov’s finite automaton. Then, the automaton and the NFA representation of the original graph are combined into a product graph. Finally, the paths between the initial and final states in the product graph satisfy the given regular expression. If such paths exist between the given source and target vertices, the RPQ results in a value “true”. Following this definition, the thesis analyzes literature proposals for indexing segmenting and indexing these paths. Firstly, the indexing approach called PAIRPQ is examined. It creates tables for each node pair and for both directions of paths, which are ultimately used to solve the RPQ. The second method is path indexing, which creates index tables of subpaths of different lengths, and introduces an algorithm for segmenting the given regular expression. The third examined method stores the adjacency matrices for each unique edge label as optimized k^2-trees. It then transforms the given regular expression into a series of operations with these boolean adjacency matrices. This method is proven to be significantly more storage-efficient but not as fast as the first two methods.

Verkkotietokannat ovat ei-relatiivisia tietokantoja, jotka tallentavat verkkojen solmuja, kaaria, ja niihin liitettyjä attribuutteja. Eräs tärkeä kysymys liittyen otsikoituihin verkkotietokantoihin on seuraava: onko annetussa verkossa reittiä, jossa sen kaarien otsikkojen muodostama merkkijono kuuluu annetun säännöllisen lausekkeen määrittämään säännölliseen kieleen (engl. regular path query, RPQ)? Tämä kandidaatintyö perusteellisesti esittelee ja analysoi suosituimman keinon ratkaista määritelty kysely, jossa ensin säännöllinen lauseke muutetaan Glushkovin äärelliseksi automaatiksi, minkä jälkeen rakennetaan verkon automaattiesityksen ja Glushkovin automaatin välinen tuloautomaatti. Tämän jälkeen tulo automaatin alku- ja lopputilojen väliset reitit toteuttavat annetun kyselyn. Tämän määrittelyn jälkeen kandidaatintyö pureutuu analysoimaan kirjallisuuden ehdotuksia näiden reittien pilkkomiseen ja indeksoimiseen. Ensimmäisenä tarkastellaan indeksointia PAIRPQ-mekanismilla, joka luo kaksi taulukkoa kullekin halutulle solmuparille - taulukko kuhunkin suuntaan olevalle yleiselle reitille, joita käytetään lopulta RPQ:n ratkaisevassa algoritmissa. Toinen tarkasteltava menetelmä on reitti-indeksointi, joka on samankaltainen kuin PAIRPQ, joka luo taulukoita riippuen reittien pituudesta. Reitti-indeksointi esittelee myös menetelmän, kuinka näitä indeksejä voidaan hyödyntää suurien kyselyiden ratkaisemiseen yhdistelemällä pilkottuja reittejä. Kolmas tarkasteltava indeksointimenetelmä säilöö naapurimatriisin optimoidussa k^2-puumuodossa alkuperäisen verkon jokaiselle uniikille attribuutille. Sitten se hajottaa RPQ:n sarjaksi operaatioita, jonka tekijät ovat näitä attribuuttimatriiseja. Tämä menetelmä on huomattavasti tehokkaampi muistinkäytössään mutta ei ole niin nopea RPQ:iden ratkaisemisessa.

Description

Supervisor

Savioja, Lauri

Thesis advisor

Zhao, Bo

Keywords

regular path query, path, graph, matrix, regular expression

Other note

Citation

Permanent link to this item

https://urn.fi/URN:NBN:fi:aalto-202505274045

Collections

[kand] Perustieteiden korkeakoulu / SCI