Evaluation and Enumeration of Regular Simple Path and Trail Queries

Titelangaben

Popp, Tina:
Evaluation and Enumeration of Regular Simple Path and Trail Queries.
Bayreuth , 2022 . - x, 209 S.
( Dissertation, 2022 , Universität Bayreuth, Fakultät für Mathematik, Physik und Informatik)
DOI: https://doi.org/10.15495/EPub_UBT_00006606

Volltext

Link zum Volltext (externe URL):

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

Abstract in weiterer Sprache

Reguläre Pfadabfragen (RPQs) sind ein wesentlicher Bestandteil von Graphabfragesprachen. Solche Abfragen betrachten einen regulären Ausdruck r und einen gerichteten kantenbeschrifteten Graphen G und suchen nach Pfaden in G, deren Abfolge von Kantenbeschriftungen ein Wort in der Sprache von r ergibt. Um zu vermeiden, dass unendlich viele Pfade berücksichtigt werden müssen, beschränken sich einige Datenbank-Systeme auf Pfade ohne Wiederholungen von Knoten oder ohne Wiederholungen von Kanten, sogenannte einfache Pfade oder Trails. Während beliebige Pfade effizient behandelt werden können, werden einfache Pfade und Trails schon bei sehr kleinen RPQs rechnerisch schwierig.
In dieser Dissertation untersuchen wir Entscheidungs- und Aufzählungsprobleme bezüglich der Semantik von einfachen Pfaden und Trails.
Evaluationsproblem auf Gerichteten Graphen: Bagan, Bonifati und Groz fanden eine Trichotomie für das Evaluationsproblem für einfache Pfade, wenn der RPQ fest ist. Wir ergänzen ihre Arbeit, indem wir eine ähnliche Trichotomie für das Evaluierungsproblem für Trails angeben und verschiedene Eigenschaften dieser Klasse untersuchen. Desweiteren untersuchen wir RPQs, die in Abfrageprotokollen (englisch: query logs) vorkommen, und definieren eine Klasse einfacher transitiver Ausdrücke, die in der Praxis häufig vorkommt und für die wir Dichotomien für das Evaluationsproblem beweisen können, wenn die Eingabesprache nicht fest ist, sondern als Parameter verwendet wird. Wir stellen fest, dass, obwohl einfache Pfad- und Trailsemantiken für RPQs im Allgemeinen schwer sind, die zugehörigen Evaluationsprobleme für die große Mehrheit der in der Praxis verwendeten RPQs effizient lösbar sind. Im Mittelpunkt dieser Studie steht ein Ergebnis von unabhängigem Interesse: Das Problem zwei disjunkte Pfade in einem gerichteten Graphen zu finden ist W[1]-schwer, wenn es durch die Länge eines der beiden Pfade parametrisiert wird.
Evaluationsproblem auf Ungerichteten Graphen: Während sich Graphendatenbanken auf gerichtete Graphen konzentrieren, gibt es Kanten, die von Natur aus bidirektional sind, wie “Geschwister” oder “verheiratet” Relationen. Außerdem erlauben Datenbanksysteme oft eine Kante in ihrer umgekehrten Richtung zu navigieren (2RPQ), so dass die Untersuchung der ungerichteten Umgebung uns eine bessere Vorstellung davon vermittelt, was möglich ist. Wir sind in der Lage, mehrere effizient und nicht effizient lösbare Unterklassen der regulären Sprachen zu identifizieren, wenn der RPQ fest ist. Insbesondere stellen wir fest, dass das Evaluationsproblem für Trails für eine Teilklasse regulärer Ausdrücke, die in der Praxis häufig vorkommen, effizient lösbar ist, während das Evaluationsproblem einfacher Pfade für eine große Unterklasse davon effizient lösbar ist. Das Problem der vollständigen Klassifizierung aller regulären Sprachen auf ungerichteten Graphen ist nicht trivial, da es ein faszinierendes Problem umfasst, das seit 30 Jahren offen ist. Interessanterweise ist die Klasse der Sprachen, die unter einfacher Pfadsemantik auf ungerichteten Graphen effizient lösbar sind, größer als auf gerichteten Graphen, während unter Trailsemantik die effizient lösbaren Klassen (unter der Annahme P != NP) nicht vergleichbar sind. Wir ergänzen unsere Arbeit erneut, indem wir die Eingabesprache als Parameter verwenden. Wir können zeigen, dass die effizient lösbare Unterklasse der einfachen transitiven Ausdrücke auf gerichteten Graphen auch auf ungerichteten Graphen effizient lösbar ist, sowohl unter einfacher Pfad- als auch unter Trailsemantik. Desweiteren können wir zeigen, dass unter Trailsemantik die effizient lösbare Unterklasse der STEs auf ungerichteten Graphen eine strikte Obermenge der entsprechenden Klasse auf gerichteten Graphen ist (unter der komplexitätstheoretischen Annahme FPT != W[1]).
Aufzählung: Wir schließen unsere Arbeit ab, indem wir das Aufzählungsproblem untersuchen. Hier geht es nicht nur darum zu entscheiden, ob ein Pfad mit bestimmten Eigenschaften existiert, sondern auch darum, alle solchen Pfade auszugeben. Basierend auf Yens Algorithmus zur Aufzählung einfacher Pfade in gerichteten und ungerichteten Graphen zeigen wir, dass Polynomialzeitalgorithmen für die vorher betrachteten Evaluationsprobleme zu Aufzählungsalgorithmen mit polynomieller Zeit zwischen aufeinanderfolgenden Ausgaben führen.