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: h9e578e077ffa0470
Venue: SIGMOD
Year: 2020
Pagerank: 6.2946294e-05
Overall Rank: 5,054 | 66.04%
DOI: 10.1145/3318464.3380567

Incoming Non-self Citations Over Time

Authors

1. Louis Jachiet (Télécom Paris)
2. Pierre Genevès (Grenoble Institute of Technology; INRIA; National Centre for Scientific Research; University of Grenoble)
3. Nils Gesbert (Grenoble Institute of Technology; INRIA; National Centre for Scientific Research; University of Grenoble)
4. Nabil Layaïda (Grenoble Institute of Technology; INRIA; National Centre for Scientific Research; University of Grenoble)

BibTeX Citation

@inproceedings{jachiet_sigmod20,
        title = {{On the Optimization of Recursive Relational Queries: Application to Graph Queries}},
        author = {Jachiet, Louis and Genevès, Pierre and Gesbert, Nils and Layaïda, Nabil},
        series = {{SIGMOD} '20},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3318464.3380567},
        url = {https://dl.acm.org/doi/10.1145/3318464.3380567},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,013	SQL Nulls and Two-Valued Logic	2023	PODS	5.911397e-05
8,677	MWP: Multi-Window Parallel Evaluation of Regular Path Queries on Streaming Graphs	2024	SIGMOD	5.2892731e-05
9,945	AvantGraph Query Processing Engine	2022	VLDB	5.1042556e-05
9,989	Schema-Based Query Optimisation for Graph Databases	2025	SIGMOD	5.0989764e-05
10,341	Efficient Enumeration of Recursive Plans in Transformation-based Query Optimizers	2024	VLDB	5.0230745e-05
10,572	DRPQ: Distributed Evaluation of Regular Path Queries On Streaming Graphs	2026	SIGMOD	4.9769913e-05
11,135	Dynamic Pruning for Recursive Joins	2025	SIGMOD	4.9769913e-05
11,567	Efficient Regular Simple Path Queries under Transitive Restricted Expressions	2024	VLDB	4.9769913e-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.0023943337
18	MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)	1986	PODS	0.00058997063
67	An Amateur's Introduction to Recursive Query Processing Strategies	1986	SIGMOD	0.00037991902
130	A Query Language and Optimization Techniques for Unstructured Data	1996	SIGMOD	0.00030306096
298	GraphLog: a Visual Formalism for Real Life Recursion	1990	PODS	0.00021830158
305	A Graphical Query Language Supporting Recursion	1987	SIGMOD	0.00021580917
419	Cypher: An Evolving Query Language for Property Graphs	2018	SIGMOD	0.00018537915
440	On the Implementation of a Simple Class of Logic Queries for Databases	1986	PODS	0.00018219394
466	Design and Implementation of the LogicBlox System	2015	SIGMOD	0.00017765702
540	An Analytical Study of Large SPARQL Query Logs	2018	VLDB	0.0001671863
860	G-CORE: A Core for Future Graph Query Languages	2018	SIGMOD	0.00013401414
1,468	Expressive Languages for Path Queries over Graph-Structured Data	2010	PODS	0.00010561507
1,981	Efficient Evaluation of Right-, Left-, and Multi-Linear Rules	1989	SIGMOD	9.267247e-05
2,100	Evaluation Of Database Recursive Logic Programs As Recurrent Function Series	1986	SIGMOD	9.0473405e-05
2,636	Big Data Analytics with Datalog Queries on Spark	2016	SIGMOD	8.1926426e-05
3,422	Query Planning for Evaluating SPARQL Property Paths	2016	SIGMOD	7.3112898e-05
6,133	More Efficient Datalog Queries: Subsumptive Tabling Beats Magic Sets	2011	SIGMOD	5.8751686e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	13,395	Structural Query Optimization — A Uniform Framework For Semantic Query Optimization In Deductive Databases	1991	PODS
2	2,100	Evaluation Of Database Recursive Logic Programs As Recurrent Function Series	1986	SIGMOD
3	720	Querying Graph Databases	2013	PODS
4	4,483	EFFICIENT EVALUATION FOR A SUBSET OF RECURSIVE QUERIES (Extended Abstract)	1987	PODS
5	9,356	Optimizing Recursive Queries in SQL	2005	SIGMOD
6	13,454	Classification Of Recursive Formulas In Deductive Databases	1988	SIGMOD
7	143	Optimization of Nonrecursive Queries	1986	VLDB
8	305	A Graphical Query Language Supporting Recursion	1987	SIGMOD
9	9,989	Schema-Based Query Optimisation for Graph Databases	2025	SIGMOD
10	2,156	A Recursive Algebra and Query Optimization for Nested Relations	1989	SIGMOD