Auflistung nach Autor:in "Popp, Tina"
1 - 1 von 1
Treffer pro Seite
Sortieroptionen
- KonferenzbeitragAuswertung von regulären Pfadabfragen ohne Knoten- oder Kantenwiederholung(Ausgezeichnete Informatikdissertationen 2022 (Band D23), 2023) Popp, TinaRegulä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.