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: 5780
Venue: SIGMOD
Year: 2020
Pagerank: 5.5984356e-05
Overall Rank: 5,259 | 63.42%
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.927459e-05
9,481	MWP: Multi-Window Parallel Evaluation of Regular Path Queries on Streaming Graphs	2024	SIGMOD	4.3341665e-05
9,672	AvantGraph Query Processing Engine	2022	VLDB	4.3062725e-05
9,676	Schema-Based Query Optimisation for Graph Databases	2025	SIGMOD	4.3047774e-05
10,070	DRPQ: Distributed Evaluation of Regular Path Queries On Streaming Graphs	2026	SIGMOD	4.1945683e-05
10,404	Dynamic Pruning for Recursive Joins	2025	SIGMOD	4.1945683e-05
11,014	Efficient Regular Simple Path Queries under Transitive Restricted Expressions	2024	VLDB	4.1945683e-05
11,053	Efficient Enumeration of Recursive Plans in Transformation-based Query Optimizers	2024	VLDB	4.1945683e-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.0040449103
16	MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)	1986	PODS	0.0010066783
77	An Amateur's Introduction to Recursive Query Processing Strategies	1986	SIGMOD	0.00057043861
114	A Query Language and Optimization Techniques for Unstructured Data	1996	SIGMOD	0.00046339735
256	GraphLog: a Visual Formalism for Real Life Recursion	1990	PODS	0.00030259041
296	On the Implementation of a Simple Class of Logic Queries for Databases	1986	PODS	0.00028644922
363	A Graphical Query Language Supporting Recursion	1987	SIGMOD	0.00025715157
613	Design and Implementation of the LogicBlox System	2015	SIGMOD	0.00019181325
690	An Analytical Study of Large SPARQL Query Logs	2018	VLDB	0.00018099792
789	Cypher: An Evolving Query Language for Property Graphs	2018	SIGMOD	0.00016634256
964	G-CORE: A Core for Future Graph Query Languages	2018	SIGMOD	0.0001497475
1,529	Evaluation Of Database Recursive Logic Programs As Recurrent Function Series	1986	SIGMOD	0.00011496686
1,812	Expressive Languages for Path Queries over Graph-Structured Data	2010	PODS	0.00010467069
2,042	Efficient Evaluation of Right-, Left-, and Multi-Linear Rules	1989	SIGMOD	9.699257e-05
3,200	Big Data Analytics with Datalog Queries on Spark	2016	SIGMOD	7.3912411e-05
4,280	Query Planning for Evaluating SPARQL Property Paths	2016	SIGMOD	6.2948356e-05
6,254	More Efficient Datalog Queries: Subsumptive Tabling Beats Magic Sets	2011	SIGMOD	5.1368042e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
12,904	Structural Query Optimization — A Uniform Framework For Semantic Query Optimization In Deductive Databases	1991	PODS	4.1945683e-05
1,529	Evaluation Of Database Recursive Logic Programs As Recurrent Function Series	1986	SIGMOD	0.00011496686
3,999	EFFICIENT EVALUATION FOR A SUBSET OF RECURSIVE QUERIES (Extended Abstract)	1987	PODS	6.5469939e-05
1,037	Querying Graph Databases	2013	PODS	0.00014502493
9,112	Optimizing Recursive Queries in SQL	2005	SIGMOD	4.3942347e-05
12,962	Classification Of Recursive Formulas In Deductive Databases	1988	SIGMOD	4.1945683e-05
143	Optimization of Nonrecursive Queries	1986	VLDB	0.00041510555
363	A Graphical Query Language Supporting Recursion	1987	SIGMOD	0.00025715157
9,676	Schema-Based Query Optimisation for Graph Databases	2025	SIGMOD	4.3047774e-05
2,110	A Recursive Algebra and Query Optimization for Nested Relations	1989	SIGMOD	9.5315487e-05