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.2976106e-05
Overall Rank: 5,050 | 66.05%
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.9141967e-05
8,669	MWP: Multi-Window Parallel Evaluation of Regular Path Queries on Streaming Graphs	2024	SIGMOD	5.2917782e-05
9,938	AvantGraph Query Processing Engine	2022	VLDB	5.106673e-05
9,980	Schema-Based Query Optimisation for Graph Databases	2025	SIGMOD	5.1013913e-05
10,334	Efficient Enumeration of Recursive Plans in Transformation-based Query Optimizers	2024	VLDB	5.0254535e-05
10,561	DRPQ: Distributed Evaluation of Regular Path Queries On Streaming Graphs	2026	SIGMOD	4.9793485e-05
11,126	Dynamic Pruning for Recursive Joins	2025	SIGMOD	4.9793485e-05
11,561	Efficient Regular Simple Path Queries under Transitive Restricted Expressions	2024	VLDB	4.9793485e-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.0023947656
18	MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)	1986	PODS	0.00059023577
67	An Amateur's Introduction to Recursive Query Processing Strategies	1986	SIGMOD	0.00038009523
130	A Query Language and Optimization Techniques for Unstructured Data	1996	SIGMOD	0.00030320165
297	GraphLog: a Visual Formalism for Real Life Recursion	1990	PODS	0.00021840374
305	A Graphical Query Language Supporting Recursion	1987	SIGMOD	0.0002159111
419	Cypher: An Evolving Query Language for Property Graphs	2018	SIGMOD	0.0001854669
440	On the Implementation of a Simple Class of Logic Queries for Databases	1986	PODS	0.00018227953
466	Design and Implementation of the LogicBlox System	2015	SIGMOD	0.00017773029
540	An Analytical Study of Large SPARQL Query Logs	2018	VLDB	0.00016726545
860	G-CORE: A Core for Future Graph Query Languages	2018	SIGMOD	0.00013406849
1,468	Expressive Languages for Path Queries over Graph-Structured Data	2010	PODS	0.00010566509
1,979	Efficient Evaluation of Right-, Left-, and Multi-Linear Rules	1989	SIGMOD	9.2716242e-05
2,099	Evaluation Of Database Recursive Logic Programs As Recurrent Function Series	1986	SIGMOD	9.0515975e-05
2,635	Big Data Analytics with Datalog Queries on Spark	2016	SIGMOD	8.1965216e-05
3,420	Query Planning for Evaluating SPARQL Property Paths	2016	SIGMOD	7.3147525e-05
6,131	More Efficient Datalog Queries: Subsumptive Tabling Beats Magic Sets	2011	SIGMOD	5.8779512e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	13,389	Structural Query Optimization — A Uniform Framework For Semantic Query Optimization In Deductive Databases	1991	PODS
2	2,099	Evaluation Of Database Recursive Logic Programs As Recurrent Function Series	1986	SIGMOD
3	4,479	EFFICIENT EVALUATION FOR A SUBSET OF RECURSIVE QUERIES (Extended Abstract)	1987	PODS
4	719	Querying Graph Databases	2013	PODS
5	9,347	Optimizing Recursive Queries in SQL	2005	SIGMOD
6	13,448	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,980	Schema-Based Query Optimisation for Graph Databases	2025	SIGMOD
10	2,154	A Recursive Algebra and Query Optimization for Nested Relations	1989	SIGMOD