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: 8089
Venue: VLDB
Year: 1989
Pagerank: 0.00010092304
Overall Rank: 1,658 | 88.63%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Alberto O. Mendelzon (University of Toronto)
2. Peter T. Wood (University of Cape Town; University of Toronto)

BibTeX Citation

@article{mendelzon_vldb89,
        title = {{Finding Regular Simple Paths in Graph Databases}},
        author = {Mendelzon, Alberto O. and Wood, Peter T.},
        journal = {PVLDB},
        series = {{VLDB} '89},
        pages = {185--193},
        year = {1989}
}

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
300	GraphLog: a Visual Formalism for Real Life Recursion	1990	PODS	0.00022046803
444	Stack-based Algorithms for Pattern Matching on DAGs	2005	VLDB	0.00018350865
1,836	Graph Pattern Matching in GQL and SQL/PGQ	2022	SIGMOD	9.6489549e-05
2,446	Querying Semantic Web Data with SPARQL	2011	PODS	8.5728114e-05
2,763	Inductive Pebble Games And The Expressive Power Of Datalog	1989	PODS	8.1537086e-05
2,957	Graph-Theoretic Methods In Database Theory	1990	PODS	7.9200375e-05
5,029	Performance Guarantees for Distributed Reachability Queries	2012	VLDB	6.3960846e-05
5,482	The G+/GraphLog Visual Query System	1990	SIGMOD	6.202193e-05
9,815	PCSP: Efficiently Answering Label-Constrained Shortest Path Queries in Road Networks	2024	VLDB	5.214913e-05
10,756	Dangers of List Processing in Querying Property Graphs	2025	SIGMOD	5.093636e-05
10,789	Efficient Indexing for Flexible Label-Constrained Shortest Path Queries in Road Networks	2025	SIGMOD	5.093636e-05
13,123	Indexing in a Hypertext Database	1990	VLDB	5.093636e-05
13,124	Factoring Augmented Regular Chain Programs	1990	VLDB	5.093636e-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
217	Traversal Recursion: A Practical Approach to Supporting Recursive Applications	1986	SIGMOD	0.00024458594
312	A Graphical Query Language Supporting Recursion	1987	SIGMOD	0.00021733819
1,330	Efficient Transitive Closure Algorithms	1988	VLDB	0.00011140171
3,739	Neptune: a Hypertext System for CAD Applications	1986	SIGMOD	7.1594837e-05
4,425	EFFICIENT EVALUATION FOR A SUBSET OF RECURSIVE QUERIES (Extended Abstract)	1987	PODS	6.7101609e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,066	Rewriting of Regular Expressions and Regular Path Queries	1999	PODS
2	3,452	The Complexity of Evaluating Path Expressions in SPARQL	2012	PODS
3	294	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD
4	5,146	Query Containment and Rewriting Using Views for Regular Path Queries Under Constraints	2003	PODS
5	4,986	Querying Graph Patterns	2011	PODS
6	747	Querying Graph Databases	2013	PODS
7	1,575	Expressive Languages for Path Queries over Graph-Structured Data	2010	PODS
8	11,225	Efficient Regular Simple Path Queries under Transitive Restricted Expressions	2024	VLDB
9	4,981	A Trichotomy for Regular Simple Path Queries on Graphs	2013	PODS
10	7,658	The Complexity of Regular Trail and Simple Path Queries on Undirected Graphs	2022	PODS