Evaluating Regular Path Queries in GQL Using Classical Algorithms

In the upcoming presentation, we address the challenge of answering regular path queries in graph databases while also providing the paths that witness our answers. We explore this problem within various semantics, including arbitrary, all-shortest, trail, and simple-path. We will demonstrate how to use the classical product construction from graph querying theory for path retrieval. Additionally, we will discuss the practical implementation of this approach, both for data stored in a traditional B+ tree structure and when it's assumed to be in main memory using a compressed sparse row representation. Our presentation will conclude with an analysis of the trade-offs and performance compared to existing methods using real-world queries.