On the Optimization of Recursive Relational Queries: Application to Graph Queries

Summary: µ-RA: a relational-algebra with a fixpoint for recursive graph queries, enabling unions of conjunctive regular path queries. New rewrite rules exploit the fixpoint to produce execution plans unreachable by prior work; experiments show significant speedups for recursive graph evaluation. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5781
Venue: SIGMOD
Year: 2020
Pagerank: 5.5930569e-05
Overall Rank: 5,267 | 63.40%
DOI: 10.1145/3318464.3380567

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,781	SQL Nulls and Two-Valued Logic	2023	PODS	4.9227317e-05
9,483	MWP: Multi-Window Parallel Evaluation of Regular Path Queries on Streaming Graphs	2024	SIGMOD	4.3300131e-05
9,672	AvantGraph Query Processing Engine	2022	VLDB	4.3021461e-05
9,676	Schema-Based Query Optimisation for Graph Databases	2025	SIGMOD	4.3006524e-05
10,070	DRPQ: Distributed Evaluation of Regular Path Queries On Streaming Graphs	2026	SIGMOD	4.1905499e-05
10,415	Dynamic Pruning for Recursive Joins	2025	SIGMOD	4.1905499e-05
11,017	Efficient Regular Simple Path Queries under Transitive Restricted Expressions	2024	VLDB	4.1905499e-05
11,056	Efficient Enumeration of Recursive Plans in Transformation-based Query Optimizers	2024	VLDB	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 17 of 17 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
1	Access Path Selection in a Relational Database Management System	1979	SIGMOD	0.0040465394
16	MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)	1986	PODS	0.00099936325
79	An Amateur's Introduction to Recursive Query Processing Strategies	1986	SIGMOD	0.00056010993
115	A Query Language and Optimization Techniques for Unstructured Data	1996	SIGMOD	0.00046301137
256	GraphLog: a Visual Formalism for Real Life Recursion	1990	PODS	0.00030241337
299	On the Implementation of a Simple Class of Logic Queries for Databases	1986	PODS	0.00028555103
364	A Graphical Query Language Supporting Recursion	1987	SIGMOD	0.00025657601
610	Design and Implementation of the LogicBlox System	2015	SIGMOD	0.00019204048
657	An Analytical Study of Large SPARQL Query Logs	2018	VLDB	0.00018581389
787	Cypher: An Evolving Query Language for Property Graphs	2018	SIGMOD	0.00016624372
964	G-CORE: A Core for Future Graph Query Languages	2018	SIGMOD	0.00014967208
1,552	Evaluation Of Database Recursive Logic Programs As Recurrent Function Series	1986	SIGMOD	0.00011393892
1,812	Expressive Languages for Path Queries over Graph-Structured Data	2010	PODS	0.00010458164
2,048	Efficient Evaluation of Right-, Left-, and Multi-Linear Rules	1989	SIGMOD	9.689916e-05
3,207	Big Data Analytics with Datalog Queries on Spark	2016	SIGMOD	7.3847098e-05
4,276	Query Planning for Evaluating SPARQL Property Paths	2016	SIGMOD	6.2884651e-05
6,253	More Efficient Datalog Queries: Subsumptive Tabling Beats Magic Sets	2011	SIGMOD	5.1318715e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
12,914	Structural Query Optimization — A Uniform Framework For Semantic Query Optimization In Deductive Databases	1991	PODS	4.1905499e-05
1,552	Evaluation Of Database Recursive Logic Programs As Recurrent Function Series	1986	SIGMOD	0.00011393892
1,040	Querying Graph Databases	2013	PODS	0.00014483577
3,990	EFFICIENT EVALUATION FOR A SUBSET OF RECURSIVE QUERIES (Extended Abstract)	1987	PODS	6.5536618e-05
9,110	Optimizing Recursive Queries in SQL	2005	SIGMOD	4.3900304e-05
12,972	Classification Of Recursive Formulas In Deductive Databases	1988	SIGMOD	4.1905499e-05
144	Optimization of Nonrecursive Queries	1986	VLDB	0.00041430126
364	A Graphical Query Language Supporting Recursion	1987	SIGMOD	0.00025657601
9,676	Schema-Based Query Optimisation for Graph Databases	2025	SIGMOD	4.3006524e-05
2,109	A Recursive Algebra and Query Optimization for Nested Relations	1989	SIGMOD	9.5283567e-05