Given are a directed edge-labelled graph G with a distinguished node n0, and a regular expression P which may contain variables. We wish to compute all substitutions phi (of symbols for variables), together with all nodes n such that all paths n0 to n are in phi(P). We derive an algorithm for this problem using relational algebra, and show how it may be implemented in Prolog. The motivation for the problem derives from a declarative framework for specifying compiler optimisations.