Konferenzbeitrag
Auswertung von regulären Pfadabfragen ohne Knoten- oder Kantenwiederholung
Lade...
Volltext URI
Dokumententyp
Text/Conference Paper
Dateien
Zusatzinformation
Datum
2023
Autor:innen
Zeitschriftentitel
ISSN der Zeitschrift
Bandtitel
Verlag
Gesellschaft für Informatik e.V.
Zusammenfassung
Reguläre Pfadabfragen 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 Datenbank-Systeme auf Pfade ohne Wiederholungen von Knoten oder ohne Wiederholungen von Kanten. Während beliebige Pfade effizient ausgewertet und aufgezählt werden können, werden diese Probleme ohne Wiederholungen von Knoten oder Kanten schon bei sehr kleinen RPQs rechnerisch schwierig (NP-schwer). In dieser Dissertation untersuchen wir Auswertungs- und Aufzählungsprobleme unter diesen Semantiken.