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: 7898
Venue: VLDB
Year: 1989
Pagerank: 0.00011946075
Overall Rank: 1,444 | 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.00030259041
425	Stack-based Algorithms for Pattern Matching on DAGs	2005	VLDB	0.00023598882
2,304	Querying Semantic Web Data with SPARQL	2011	PODS	9.0648775e-05
2,310	Inductive Pebble Games And The Expressive Power Of Datalog	1989	PODS	9.0580784e-05
2,474	Graph-Theoretic Methods In Database Theory	1990	PODS	8.7135761e-05
2,505	Graph Pattern Matching in GQL and SQL/PGQ	2022	SIGMOD	8.634551e-05
4,856	The G+/GraphLog Visual Query System	1990	SIGMOD	5.8737498e-05
5,054	Performance Guarantees for Distributed Reachability Queries	2012	VLDB	5.7321997e-05
9,680	PCSP: Efficiently Answering Label-Constrained Shortest Path Queries in Road Networks	2024	VLDB	4.3047774e-05
10,477	Dangers of List Processing in Querying Property Graphs	2025	SIGMOD	4.1945683e-05
10,516	Efficient Indexing for Flexible Label-Constrained Shortest Path Queries in Road Networks	2025	SIGMOD	4.1945683e-05
12,928	Indexing in a Hypertext Database	1990	VLDB	4.1945683e-05
12,929	Factoring Augmented Regular Chain Programs	1990	VLDB	4.1945683e-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
175	Traversal Recursion: A Practical Approach to Supporting Recursive Applications	1986	SIGMOD	0.00038338694
363	A Graphical Query Language Supporting Recursion	1987	SIGMOD	0.00025715157
880	Efficient Transitive Closure Algorithms	1988	VLDB	0.00015667998
2,959	Neptune: a Hypertext System for CAD Applications	1986	SIGMOD	7.8149418e-05
3,999	EFFICIENT EVALUATION FOR A SUBSET OF RECURSIVE QUERIES (Extended Abstract)	1987	PODS	6.5469939e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,342	Rewriting of Regular Expressions and Regular Path Queries	1999	PODS	9.0015589e-05
3,652	The Complexity of Evaluating Path Expressions in SPARQL	2012	PODS	6.875313e-05
461	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD	0.00022499343
5,406	Query Containment and Rewriting Using Views for Regular Path Queries Under Constraints	2003	PODS	5.5243825e-05
4,946	Querying Graph Patterns	2011	PODS	5.8149362e-05
1,037	Querying Graph Databases	2013	PODS	0.00014502493
1,812	Expressive Languages for Path Queries over Graph-Structured Data	2010	PODS	0.00010467069
11,014	Efficient Regular Simple Path Queries under Transitive Restricted Expressions	2024	VLDB	4.1945683e-05
5,424	A Trichotomy for Regular Simple Path Queries on Graphs	2013	PODS	5.5126983e-05
8,827	The Complexity of Regular Trail and Simple Path Queries on Undirected Graphs	2022	PODS	4.4411907e-05