Finding regular paths in acyclic graphs

Abstract

Increasing the expressive power of relational query languages by providing some form of recursion is currently a topic of much research. For many recursive queries in relational databases, a relation can be represented as labelled directed graph G, while the query can be viewed as finding simple paths in G that satisfy a given regular expression. Based on such a query language, it has been shown recently that, in this context, the general query evaluation problem on cyclic graphs is intractable. In this paper, we present an efficient algorithm for the case in which the graphs are acyclic.