Auswertung von regulären Pfadabfragen ohne Knoten- oder Kantenwiederholung

dc.contributor.author	Popp, Tina
dc.contributor.editor	Reischuk, Rüdiger
dc.date.accessioned	2023-11-09T13:38:07Z
dc.date.available	2023-11-09T13:38:07Z
dc.date.issued	2023
dc.description.abstract	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.	de
dc.identifier.isbn	978-3-88579-981-8
dc.identifier.uri	https://dl.gi.de/handle/20.500.12116/42600
dc.language.iso	de
dc.publisher	Gesellschaft für Informatik e.V.
dc.relation.ispartof	Ausgezeichnete Informatikdissertationen 2022 (Band D23)
dc.title	Auswertung von regulären Pfadabfragen ohne Knoten- oder Kantenwiederholung	de
dc.type	Text/Conference Paper
gi.citation.endPage	240
gi.citation.publisherPlace	Bonn
gi.citation.startPage	231
gi.conference.date	14.-17.05.2023
gi.conference.location	Schloss Dagstuhl, Deutschland

Dateien

1 - 1 von 1