Logo des Repositoriums
 
Konferenzbeitrag

Auswertung von regulären Pfadabfragen ohne Knoten- oder Kantenwiederholung

Vorschaubild nicht verfügbar

Volltext URI

Dokumententyp

Text/Conference Paper

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.

Beschreibung

Popp, Tina (2023): Auswertung von regulären Pfadabfragen ohne Knoten- oder Kantenwiederholung. Ausgezeichnete Informatikdissertationen 2022 (Band D23). Bonn: Gesellschaft für Informatik e.V.. ISBN: 978-3-88579-981-8. pp. 231-240. Schloss Dagstuhl, Deutschland. 14.-17.05.2023

Schlagwörter

Zitierform

DOI

Tags