A Trichotomy for Regular Trail Queries

DOI10.46298/LMCS-19(4:20)2023MaRDI QIDQ6178699zbMATH OpenOpenAlexFDO

Authors Wim Martens, Matthias Niewerth

Publication date 16 January 2024

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

complexitydatabasesgraph databasespath queriesquery languagesregular languagessimple pathstrails

Mathematics Subject Classification ID

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

Abstract: Regular path queries (RPQs) are an essential component of graph query languages. Such queries consider a regular expression r and a directed edge-labeled graph G and search for paths in G for which the sequence of labels is in the language of r. In order to avoid having to consider infinitely many paths, some database engines restrict such paths to be trails, that is, they only consider paths without repeated edges. In this paper we consider the evaluation problem for RPQs under trail semantics, in the case where the expression is fixed. We show that, in this setting, there exists a trichotomy. More precisely, the complexity of RPQ evaluation divides the regular languages into the finite languages, the class Ttract (for which the problem is tractable), and the rest. Interestingly, the tractable class in the trichotomy is larger than for the trichotomy for simple paths, discovered by Bagan, Bonifati, and Groz [JCSS 2020]. In addition to this trichotomy result, we also study characterizations of the tractable class, its expressivity, the recognition problem, closure properties, and show how the decision problem can be extended to the enumeration problem, which is relevant to practice.

Recommendations

• scientific article; zbMATH DE number 7650892
• A trichotomy for regular simple path queries on graphs
• Evaluation and enumeration problems for regular path queries
• Fine-Grained Complexity of Regular Path Queries
• Finding Regular Simple Paths in Graph Databases

Cites work

• A generalization of the Schützenberger product of finite monoids
• A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem
• A trichotomy for regular simple path queries on graphs
• Classification of finite monoids: the language approach
• Classifying regular events in symbolic logic
• Dot-depth of star-free events
• Finding Regular Simple Paths in Graph Databases
• Finding Two Disjoint Paths Between Two Pairs of Vertices in a Graph
• scientific article; zbMATH DE number 1775408 (Why is no real title available?)
• scientific article; zbMATH DE number 7650892 (Why is no real title available?)
• Modularity of cycles and paths in graphs
• Nondeterministic Space is Closed under Complementation
• On finite monoids having only trivial subgroups
• On free monoids partially ordered by embedding
• Regular expressions with counting: weak versus strong determinism
• Some results onC-varieties
• The complexity of regular expressions and property paths in SPARQL
• The directed subgraph homeomorphism problem
• The dot-depth hierarchy, 45 years later
• The even-path problem for graphs and digraphs
• The method of forced enumeration for nondeterministic automata
• The subgraph homeomorphism problem
• THE WREATH PRODUCT PRINCIPLE FOR ORDERED SEMIGROUPS
• Using forward reachability analysis for verification of lossy channel systems

Cited in

(1)

• Fine-Grained Complexity of Regular Path Queries

This page was built for publication: A Trichotomy for Regular Trail Queries

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