Finden von regelmäßigen einfachen Pfaden in Graphdatenbanken

Wir betrachten folgendes Problem: Gegeben ist ein beschrifteter gerichteter Graph G und ein regulärer Ausdruck R, finde alle Paare von Knoten, die durch einen einfachen Pfad verbunden sind, sodass die Verkettung der Beschriftungen entlang des Pfades R erfüllt. Das Problem wird durch die Beobachtung motiviert, dass viele rekursive Anfragen in relationalen Datenbanken in dieser Form ausgedrückt werden können, und durch die Implementierung einer Abfragesprache, G^+, die auf dieser Beobachtung basiert. Wir zeigen, dass das Problem im Allgemeinen unlösbar ist, präsentieren jedoch einen Algorithmus, der in polynomialer Zeit in der Größe des Graphen läuft, wenn der reguläre Ausdruck und der Graph konfliktfrei sind. Wir präsentieren auch eine Klasse von Sprachen, deren Ausdrücke immer in polynomialer Zeit in der Größe sowohl des Graphen als auch des Ausdrucks ausgewertet werden können, und charakterisieren syntaktisch die Ausdrücke für solche Sprachen.