title: Evaluation and Enumeration of Regular Simple Path and Trail Queries
Creators: name: Popp, Tina
Publisher: name: University of Bayreuth
Year: 2022
Subjects: subject: Graph databases
subject: regular path queries
subject: regular languages
subject: enumeration
subject: query lan-guages
subject: 000
subject: 004

description: 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 paths without repeated nodes or edges which are called simple paths or trails, respectively. Whereas arbitrary paths can be dealt with efficiently, simple paths and trails become computationally difficult already for very small RPQs. In this dissertation we investigate decision and enumeration problems concerning simple path and trail semantics. Evaluation Problem on Directed Graphs: Bagan, Bonifati, and Groz gave a trichotomy for the evaluation problem for simple paths when the RPQ is fixed. We complement their work by giving a similar trichotomy for the evaluation problem for trails and studying various characteristics of this class. We also study RPQs used in query logs and define a class of simple transitive expressions that is prominent in practice and for which we can prove dichotomies for the evaluation problem when the input language is not fixed, but used as a parameter. We observe that, even though simple path and trail semantics are intractable for RPQs in general, they are feasible for the vast majority of RPQs that are used in practice. At the heart of this study is a result of independent interest: the two disjoint paths problem in directed graphs is W[1]-hard if parameterized by the length of one of the two paths. Evaluation Problem on Undirected Graphs: While graph databases focus on directed graphs, there are edges which are naturally bidirectional, such as “sibling” or “married”. Furthermore, database systems often allow to navigate an edge in its inverse direction (2RPQ), thus the study of the undirected setting gives us a better idea of what is possible. We are able to identify several tractable and intractable subclasses of regular languages when the input language is fixed. In particular, we establish that trail evaluation for simple chain regular expressions, which are common in practice, is tractable, whereas simple path evaluation is tractable for a large subclass. The problem of fully classifying all regular languages on undirected graphs is quite non-trivial, since it subsumes an intriguing problem that has been open for 30 years. Interestingly, the class of languages that are tractable under simple path semantics on undirected graphs is larger than on directed graphs, while under trail semantics the tractable classes are incomparable (assuming P != NP). We again complement our work using the input language as a parameter. We can show that the tractable subclass of simple transitive expressions on directed graphs is also tractable on undirected graphs, both under simple path and trail semantics. Under trail semantics, the tractable subclass of simple transitive expressions on undirected graphs is a strict superset of the one on directed graphs (under standard complexity assumptions, namely FPT != W[1]). Enumeration: We conclude our work by studying the enumeration setting. In this setting, the goal is to not only decide if a path with certain properties exists, but to output all such paths. Based on Yen’s algorithm for enumerating simple paths in directed and undirected graphs, we show that polynomial time algorithms for RPQ evaluation problems give rise to enumeration algorithms with polynomial delay between consecutive answers.