Fine-Grained Complexity of Regular Path Queries

DOI10.46298/LMCS-19(4:15)2023arXiv2101.01945MaRDI QIDQ6137832FDOQ6137832

Markus L. Schmid, Katrin Casel

Publication date: 16 January 2024

Published in: Logical Methods in Computer Science (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/2101.01945

zbMATH Keywords

enumerationgraph databasesregular path queriesfine-grained complexity

Mathematics Subject Classification ID

Logic in computer science (03B70) Computer science (68-XX)

Cites Work

• Powers of tensors and fast matrix multiplication
• Depth-First Search and Linear Graph Algorithms
• Efficient determination of the transitive closure of a directed graph
• Multiplying matrices faster than coppersmith-winograd
• A new algorithm for optimal 2-constraint satisfaction and its implications
• On Acyclic Conjunctive Queries and Constant Delay Enumeration
• Finding Regular Simple Paths in Graph Databases
• Expressiveness and static analysis of extended conjunctive regular path queries
• Fast sparse matrix multiplication
• Subcubic Equivalences Between Path, Matrix, and Triangle Problems
• Automata, Languages and Programming
• Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
• Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails
• Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
• If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser
• Querying Graphs with Data
• A trichotomy for regular simple path queries on graphs
• The complexity of regular expressions and property paths in SPARQL
• Evaluation and Enumeration Problems for Regular Path Queries
• Regular queries on graph databases
• Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
• Fine-Grained Complexity Theory (Tutorial)
• Regular Path Queries in Lightweight Description Logics: Complexity and Algorithms
• On the Complexity of Evaluating Regular Path Queries over Linear Existential Rules
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (2)

• Shortest distances as enumeration problem
• The NFA acceptance hypothesis: non-combinatorial and dynamic lower bounds

This page was built for publication: Fine-Grained Complexity of Regular Path Queries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6137832)