Finding Regular Simple Paths in Graph Databases

Summary: Find node pairs connected by a simple path in a labeled digraph with path labels in L(R). General problem intractable; polynomial-time for conflict-free G/R; defines a syntactically characterized language class solvable in poly-time data+expression. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 7899
Venue: VLDB
Year: 1989
Pagerank: 0.00011937596
Overall Rank: 1,445 | 89.96%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Alberto O. Mendelzon
2. Peter T. Wood

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
256	GraphLog: a Visual Formalism for Real Life Recursion	1990	PODS	0.00030241337
425	Stack-based Algorithms for Pattern Matching on DAGs	2005	VLDB	0.00023592024
2,302	Querying Semantic Web Data with SPARQL	2011	PODS	9.0662698e-05
2,317	Inductive Pebble Games And The Expressive Power Of Datalog	1989	PODS	9.049333e-05
2,473	Graph-Theoretic Methods In Database Theory	1990	PODS	8.7048914e-05
2,504	Graph Pattern Matching in GQL and SQL/PGQ	2022	SIGMOD	8.629969e-05
4,858	The G+/GraphLog Visual Query System	1990	SIGMOD	5.868056e-05
5,051	Performance Guarantees for Distributed Reachability Queries	2012	VLDB	5.7267112e-05
9,680	PCSP: Efficiently Answering Label-Constrained Shortest Path Queries in Road Networks	2024	VLDB	4.3006524e-05
10,487	Dangers of List Processing in Querying Property Graphs	2025	SIGMOD	4.1905499e-05
10,525	Efficient Indexing for Flexible Label-Constrained Shortest Path Queries in Road Networks	2025	SIGMOD	4.1905499e-05
12,938	Indexing in a Hypertext Database	1990	VLDB	4.1905499e-05
12,939	Factoring Augmented Regular Chain Programs	1990	VLDB	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
157	Traversal Recursion: A Practical Approach to Supporting Recursive Applications	1986	SIGMOD	0.0004048407
364	A Graphical Query Language Supporting Recursion	1987	SIGMOD	0.00025657601
885	Efficient Transitive Closure Algorithms	1988	VLDB	0.00015565543
2,961	Neptune: a Hypertext System for CAD Applications	1986	SIGMOD	7.8083539e-05
3,990	EFFICIENT EVALUATION FOR A SUBSET OF RECURSIVE QUERIES (Extended Abstract)	1987	PODS	6.5536618e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,345	Rewriting of Regular Expressions and Regular Path Queries	1999	PODS	8.9933611e-05
3,659	The Complexity of Evaluating Path Expressions in SPARQL	2012	PODS	6.8684407e-05
460	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD	0.00022679846
5,415	Query Containment and Rewriting Using Views for Regular Path Queries Under Constraints	2003	PODS	5.5188622e-05
4,949	Querying Graph Patterns	2011	PODS	5.8090034e-05
1,040	Querying Graph Databases	2013	PODS	0.00014483577
1,812	Expressive Languages for Path Queries over Graph-Structured Data	2010	PODS	0.00010458164
11,017	Efficient Regular Simple Path Queries under Transitive Restricted Expressions	2024	VLDB	4.1905499e-05
5,435	A Trichotomy for Regular Simple Path Queries on Graphs	2013	PODS	5.5074113e-05
8,827	The Complexity of Regular Trail and Simple Path Queries on Undirected Graphs	2022	PODS	4.4369334e-05