Finding Regular Simple Paths in Graph Databases
Alberto O. Mendelzon, Peter T. Wood · SIAM Journal on Computing · 1995
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, $\textbf{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.
Cited by 399 works. doi:10.1137/s009753979122370x
Authors
References
- The Design and Analysis of Computer Algorithms
- Introduction to automata theory, languages and computation
- Word problems requiring exponential time(Preliminary Report)
- Universality of data retrieval languages
- Implementation of logical query languages for databases
- Neptune: a hypertext system for CAD applications
- The directed subgraph homeomorphism problem
- Graphs and networks
- GraphLog
- Fast Algorithms for Solving Path Problems