Katrin Casel ; Markus L. Schmid - Fine-Grained Complexity of Regular Path Queries

lmcs:8625 - Logical Methods in Computer Science, November 27, 2023, Volume 19, Issue 4 - https://doi.org/10.46298/lmcs-19(4:15)2023
Fine-Grained Complexity of Regular Path QueriesArticle

Authors: Katrin Casel ; Markus L. Schmid

    A regular path query (RPQ) is a regular expression q that returns all node pairs (u, v) from a graph database that are connected by an arbitrary path labelled with a word from L(q). The obvious algorithmic approach to RPQ-evaluation (called PG-approach), i.e., constructing the product graph between an NFA for q and the graph database, is appealing due to its simplicity and also leads to efficient algorithms. However, it is unclear whether the PG-approach is optimal. We address this question by thoroughly investigating which upper complexity bounds can be achieved by the PG-approach, and we complement these with conditional lower bounds (in the sense of the fine-grained complexity framework). A special focus is put on enumeration and delay bounds, as well as the data complexity perspective. A main insight is that we can achieve optimal (or near optimal) algorithms with the PG-approach, but the delay for enumeration is rather high (linear in the database). We explore three successful approaches towards enumeration with sub-linear delay: super-linear preprocessing, approximations of the solution sets, and restricted classes of RPQs.

    Volume: Volume 19, Issue 4
    Published on: November 27, 2023
    Accepted on: August 11, 2023
    Submitted on: October 29, 2021
    Keywords: Computer Science - Data Structures and Algorithms,Computer Science - Computational Complexity,Computer Science - Databases,Computer Science - Formal Languages and Automata Theory

    Consultation statistics

    This page has been seen 502 times.
    This article's PDF has been downloaded 154 times.