Abstract. We consider the following problem: given a labelled directed graph G and a regular expression R, find all pairs of nodes connected by a simple path such that the concatenation of the labels along the path satisfies R. The problem is motivated by the observation that many recursive queries in relational databases can be expressed in this form, and by the implementation of a query language, G + , based on this observation. We show that the problem is in general intractable, but present an algorithm than runs in polynomial time in the size of the graph when the regular expression and the graph are free of conflicts. We also present a class of languages whose expressions can always be evaluated in time polynomial in the size of both the graph and the expression, and characterize syntactically the expressions for such languages. Key words. Labelled directed graphs, NP-completeness, polynomial-time algorithms, regular expressions, simple paths AMS(MOS) subject classifications. 68P, 68Q, 68R 1. Introduction. Much of the success of the relational model of data can be attributed to its simplicity, which makes it both amenable to mathematical analysis and easy for users to comprehend. In this latter respect, the availability of non-procedural query languages has been a great asset. However, the fact that queries which are especially useful in new application domains are not expressible in traditional query languages has led to proposals for more powerful query languages, such as the logic-based language Datalog [23] and our query language G + [9, 10]. The original proposal for the relational model included two query languages of equivalent expressive power: the relational calculus and the relational algebra [7] . These languages have been used as the yardstick by which other query languages are classified; a query language is said to be relationally complete if it has (at least) the expressive power of the relational calculus. However, this notion of completeness has been questioned since it was shown that certain reasonable queries, such as finding the transitive closure of a binary relation, cannot be expressed in the calculus [3, 4] . This particular limitation is overcome in the languages G + and Datalog through their ability to express recursive queries. The design of G + is based on the observation that many of the recursive queries that arise in practice-and in the literature-amount to graph traversals (for example, [1, 12, 19] ). In G + , we view the database as a directed, labelled graph, and pose queries which are graph patterns; the answer to a query is the set of subgraphs of the database that match the given pattern. Useful applications for such a language can be found in systems representing transportation networks, communication networks, hypertext documents, and so on. In our prototype implementation, queries are drawn on a workstation screen and the database and query results are also displayed pictorially.
Mendelson and Wood show that finding all simple paths in a (deterministic) graph matching a regular expression is NP-hard REF .
Finding Regular Simple Paths In Graph Databases
VLDB
Mathematics Computer Science